[알고리즘] C# ArrayList와 LinkedList

참고 자료 - ArrayList와 LinkedList란 무엇인가? (tistory.com)

 

ArrayList(선형리스트) 

개념

선형 리스트는 배열과 같이 연속되는 기억장소에 저장되는 리스트를 말한다.

연접 리스트(Dense List) 또는 축차 구조(Sequential Structure)라고도 한다.

차이

배열은 고정된 크기의 연속된 배열요소들의 집합이므로 배열을 초기화 할 때 총 배열 요소의 수를 미리 지정해야 한다. 하지만 경우에 따라 배열요소가 몇 개나 필요한 지 미리 알 수 없는 경우가 있으며, 중간에 필요에 따라 배열을 확장해야 하는 경우도 있다..NET에는 이러한 동적 배열을 지원하는 클래스로 ArrayList와 List<T>이 있다. 이들 동적 배열 클래스들은 배열 확장이 필요한 경우, 내부적으로 배열 크기가 2배인 새로운 배열을 생성하고 모든 기존 배열 요소들을 새로운 배열에 복사한 후 기존 배열을 해제한다.

 

선형리스트의 특징

1. 가장 간단한 자료구조이다.

2. 접근속도가 빠르다.

3. 중간에 자료를 삽입하기 위해서는 연속된 빈 공간이 있어야 한다.

4. 기억장소를 연속적으로 배정받기 때문에 기억장소 이용 효율은 밀도가 1로서 가장 좋다.

5. 자료의 개수가 n개일 때 삽입 시의 평균 이동 횟수는 (n+1)/2이고, 삭제 시에는 (n-1)/2이다.

6. 삽입, 삭제 시 자료의 이동이 필요하기 때문에 작업이 번거롭다.

 

 

LinkedList(연결리스트) 

개념

링크드 리스트 (Linked List, 연결 리스트)는 데이타를 포함하는 노드들을 연결하여 컬렉션을 만든 자료 구조로서 각 노드는 데이타와 다음/이전 링크 포인터를 갖게 된다.단일 연결 리스트(Singly Linked List)는 노드를 다음 링크로만 연결한 리스트이고 이중 연결 리스트는 각 노드를 다음 링크와 이전 링크 모두 연결한 리스트이다. 만약 링크를 순환해서 마지막 노드의 다음 링크가 처음 노드를 가리키게 했을 경우 이를 순환 연결 리스트 (Circular Linked List)라 부른다.

차이

연결 리스트는 자료들을 반드시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조이다.

 

연결 리스트의 특징

1. 노드의 삽입, 삭제 작업이 용이하다.

2. 기억공간이 연속적으로 놓여 있지 않아도 저장이 가능하다.

3. 연결을 위한 링크(포인터) 부분이 필요하기 때문에 순차 리스트에 비해 기억공간 이용 효율이 좋지 않다.

4. 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근 속도가 느리다.

5. 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘들다.

6. 희소 행렬 을 링크드 리스트로 표현하면 기억장소가 절약된다.

7. 트리를 표현할 때 가장 적합한 자료 구조이다.

 

연결리스트의 종류