연결 리스트의 종류

최종 수정 : 24.12.27

연결 리스트의 종류

1. 환형 연결 리스트(Circular Linked List)

단순 연결 리스트의 마지막 노드의 포인터를 NULL이 아닌 첫 번째 노드의 주소를 가리키도록 한 형태를 원형 연결 리스트 또는 환형 연결 리스트라고 한다.

 

어떤 노드에서든 다른 노드를 검색할 수 있다는 장점이 있다. 단, 단순 연결 리스트에서는 첫 노드가 삭제되거나 삽입될 때 head가 변경이 되는데, 환형 연결 리스트는 마지막 노드의 link도 같이 변경되어야 한다.

 

1) 환형 연결 리스트의 첫 노드 또는 마지막 노드 삽입

환형 연결 리스트는 마지막 노드의 링크가 첫 번째 노드를 가리키는 리스트이다. 한 노드에서 임의의 다른 노드로의 접근이 가능하고, head가 첫 노드를 지시하도록 구성한다.

 

2) 환형 연결 리스트의 길이 계산

리스트에서 노드의 링키를 따라가면서 다음 노드가 존재하면 길이가 1씩 증가한다.

---

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

이중 연결 리스트는 각 노드에 link를 두 개를 두어 하나는 앞 노드를 지시하고, 다른 하나는 뒤를 지시하게 한 연결 리스트이다. 이중 연결 리스트는 순차 접근과 역순 접근이 가능하여 이를 복구할 수 있다는 장점이 있고, 링크의 조작이 단순하여 삽입 삭제 알고리즘이 단순하다.

---

3. 이중 환형 연결 리스트(Double Circular Linked List)

이중 환형 연결 리스트는 이중 연결 리스트와 환형 연결 리스트가 혼합된 구조이다. 이는 순방향 환형 구조와 역방향 환형 구조를 모두 갖고 있는 구조이다. 연결 리스트 중 구조가 가장 복잡하고, 많은 link로 인한 기억공간의 낭비를 가져오지만 가장 유연하다는 장점이 있다.

---

참고

독학사 교재