[자료구조] 1-3. 이중 연결리스트, 원형 연결 리스트(Doubly Linked List, Circular Linked List)

이중 연결 리스트

이중 연결 리스트는 기존의 연결리스트와는 달리, 쌍방향으로 연결이 되어있다. 이미 한 노드를 지나쳐도, 돌아갈 수 있다.

장점

찾아야 하는 값이 tail쪽에 가까울 때, head부터 시작해서 탐색하는 번거로움 등을 없앨 수 있다.

위치를 모르는 상태에서 값을 찾을 때에도, 앞에서 절반, 뒤 끝에서 절반씩 탐색하면 훨씬 효율적이다.

 

단점

변수를 3개 사용한다.(이전 메모리주소, 내 엘리먼트, 다음 메모리주소) 이 과정에서 메모리를 더 사용하게된다.

구현이 복잡해진다.

그러나, 이런 단점들을 두고도, 얻게 되는 것이 많아서, 실제 연결리스트를 사용할 때, 이중 연결리스트를 많이 사용한다.

 

노드의 추가

노드 a↔b↔d에서 b↔d 사이에 c를 연결하고 싶으면, 

c의 다음 노드로 d를 연결해주고, d의 이전 노드로 c를 연결해준다.

b의 다음 노드로 c를 연결해주고, c의 이전 노드로 b를 연결해준다.

노드의 제거

노드 a↔x↔b에서 x노드를 빼고 싶으면, 

a노드의 다음 노드로 b노드를 향하게 하고, b노드의 이전 노드를 a노드로 향하게 한다.

x노드를 제거한다.

원형 연결 리스트

원형 연결 리스트는 기존의 연결 리스트에서 마지막 노드에서 첫 노드로 향하게 한 리스트이다. 그래서 연결 형태가 원형이다.

마지막 노드까지 다 탐색하여도, 다시 처음 노드로 돌아온다.

새로운 노드인 7을 맨 뒤에 추가하던, 노드 맨 앞에 추가하던, 다음 노드인 2로 향하기 때문에, 원형 연결 리스트는 사실상  head와 tail의 개념이 없다.

 

노드의 추가(삽입)

 

노드의 삽입은 맨 앞에 삽입하는경우, 중간에 삽입하는경우가 있다. 원형 연결 리스트에서 tail은 무의미하기때문에, 중간에 삽입하는것과 같다. 

 

맨 앞에 삽입하는경우

새로운 노드를 기존 첫 노드에 링크시키고, 마지막 노드에서 새로운 노드로 링크시킨다.

head의 포인터도 새로운 노드에 링크시킨다.

중간에 삽입하는경우

새로운 노드를 다음 노드에 링크해주고, 기존 다음 노드의 이전노드를 새로운 노드로 링크시킨다. 

기존 연결리스트에서 원형을 만들어주어야한다고 생각하면 편하다.

 

노드의 제거

 

노드의 제거 역시 기존 연결리스트에서 원형을 만들어준다고 생각하면 편하다.

삭제하려는 노드의 이전 노드에서 삭제하려는 노드의 다음 노드로 링크 후,

삭제하려는 노드를 삭제하면 된다.