원형 연결 리스트(circular linked list), 이중 연결 리스트(double linked list)

 

원형 연결 리스트(Circular Linked List)

 단일 연결 리스트(Single Linked List)는 마지막 노드가 null을 가리킨다. 이 마지막 노드가 첫 번째 노드를 가리키게 하면 원형 연결 리스트가 된다.

 인덱스 0의 위치에 새로운 노드를 삽입하려면 마지막 노드의 링크를 바꿔야 하므로 마지막 노드에 접근하기 위해 리스트의 제일 끝까지 순회해야 하는 문제가 생긴다. head node의 위치를 옮겨서 마지막 노드를 가리키게 하면 문제를 해결할 수 있다. 이를 변형된 원형 연결 리스트라고 한다.

 

 

✱제일 앞에 새로운 노드 추가하기

 autumn, dico, kyle, beemo 네 노드가 있고, head node는 마지막 노드인 beemo이다. 이 원형 연결 리스트에 eve라는 새로운 노드를 제일 앞에 추가하려고 한다.

  1) 새 노드의 next를 원래 head node의 next인 autumn을 가리키게 한다.

  2) head node의 next가 새 노드를 가리키게 한다.

 

 

✱제일 끝에 새로운 노드 추가하기

위의 원형 연결 리스트와 같고, 리스트의 맨 끝에 새로운 노드를 추가하려고 한다.

  1) 새 노드의 next를 원래 head node의 next인 autumn을 가리키게 한다.

  2) head node의 next가 새 노드를 가리키게 한다.

  3) head node를 새 노드로 바꿔준다.

 

 원형 연결 리스트의 특성상 끝에 추가하나 앞에 추가하나 노드의 순서는 같고, head node만 달라진다는 것을 알 수 있다.

 

 그리고 원형 연결 리스트는 특정 노드를 검색할 때 그 노드가 연결 리스트에 없는 노드라면 무한 루프에 빠질 가능성이 있다. 검색을 끝낼 수 있는 노드를 지정해 두는 것이 좋다.

 

---

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

 이중 연결 리스트는 각 노드에 2개의 링크가 있다는 점만 제외하면 연결 리스트와 비슷하다. 한 링크는 다음 노드(next)를 가리키고, 다른 한 링크는 앞 노드(prev)를 가리킨다. 그뿐만 아니라 처음(head)과 마지막 노드(tail)를 모두 기록한다.

 

✱head node ­­­⇢ next,   tail node ⇢ prev로 양방향 탐색 

 인덱스로 데이터를 읽어올 때 싱글 링크드 리스트일 경우에는 무조건 앞(head) 노드부터 시작해야 하지만, 더블 링크드 리스트일 경우에는 앞(head), 끝(tail) 모두 바로 접근 가능하기 때문에 찾으려는 인덱스가 어디에 더 가까운지에 따라 더 빠르게 검색할 수 있다. 빅 오 표기법에서 상수를 무시해 싱글, 더블 둘 다 시간 복잡도는 O(N)이지만, 싱글 링크드 리스트에서 최악의 단계 수가 N개라면, 더블 링크드 리스트에서는 N/2개라고 할 수 있다. 더블 링크드 리스트에서는 절반 나눠서 head부터 찾아갈지, tail부터 찾아갈지 선택하면 되기 때문!

 

 이중 연결 리스트는 항상 첫 노드와 마지막 노드를 모두 알고 있으므로 각각 한 단계 O(1)만에 접근할 수 있다. 또 리스트 앞과 끝 모두에 바로 접근할 수 있으므로 O(1)에 양 끝에 데이터를 삽입할 수 있을 뿐 아니라, O(1)에 양 끝에서 데이터를 삭제할 수 있다.  이러한 점에서 이중 연결 리스트는 큐(queue)를 위한 완벽한 내부 자료 구조이다.

 

 

 

---

참고

원형 연결 리스트 : 블로그 - 원형 연결 리스트 

이중 연결 리스트 : 책 - 제이 웬그로운 〔누구나 자료 구조와 알고리즘〕

 

학습 단계로 잘못된 정보가 있을 수 있습니다. 잘못된 부분에 대해 알려주시면 곧바로 정정하도록 하겠습니다🙂