연결 리스트의 종류와 특징

1. 단일 연결 리스트(Single Linked List)

   • 각 노드에 자료공간과, 한 개의 포인터공간이 있고 각 노드의 포인터는 다음 노드를 참조한다.

   • 포인터가 한개이기 때문에, 다음 값만을 가리키고 있으므로, 한 방향으로 진행되는 특징을 가진다.

     따라서 탐색 시, 순차 탐색이 필요하다.

     

2. 이중 연결 리스트(Doubly Linked List)

   • 각 노드에 자료공간과, 두 개의 포인터공간이 있고, 각각의 포인터는 앞,뒤의 노드를 가리킨다.
   • 두 개의 포인터를 가지고 있어 양방향으로 진행되어 탐색시 유리하지만, 두 개의 포인터를 갖고 있는 만큼 구현이 까다롭고, 노드 삭제 시 인접한 노드에 추가적인 수정이 필요하다.

3. 원형 연결 리스트(Circularly List)

   • 일반적인 연결 리스트의 구조를 갖고 있으며, 마지막 노드와 처음노드를 연결시켜, 원형으로 만든 구조.

   • 하나의 포인터에 마지막 노드의 정보도 갖고 있기 때문에 추가에 좀 더 용이하다는 장점이 있다. 다만, 구현이 이중 연결 리스트보다 더 까다롭고, 검색 시, 무한 루프에 빠질 가능성도 염두에 두어야한다.

     

4. 선형 리스트(Linear List)

   • 순차 리스트(Ordered List)라 부르기도 한다.

   • 크기가 정적으로 정해지기 때문에, 데이터의 개수도 제한되어있는 것이 특징이다.

   • 주로 고정되어있는 크기의 배열로 구현하기 때문에, 데이터 간에 순서가 있고, 요소에 인덱스를 사용할 수 있다.

   • 인덱스가 정해져 있어, 탐색시 유리하지만, 데이터의 추가와 삭제의 경우 위의 리스트 보다 더 많은 시간이 소요된다.