이중 연결 리스트

이중 연결 리스트

단일 연결 리스트(single linked list)와 환형 연결 리스트(circular linked list)는 각 노드에 다음 노드를 가리키는 한 개의 링크 필드만을 사용하기 때문에 특정한 노드를 검색하거나, 삽입 또는 삭제를 할 경우 한 쪽 방향으로만 해당 노드의 위치를 찾을 수 있는 구조이다. 그러나 임의의 노드를 찾을 때 양쪽 방향으로 해당 노드를 검색하면 쉽게 찾을 수 있다. 그러므로 이중 연결 리스트(double linked list)는 노드의 선행 노드를 가리키는 좌링크(LLINK), 자료(DATA)필드, 후행 노드를 가리키는 우링크(RLINK)의 세 개 영역으로 각 노드를 구분하여 양방향으로 특정 노드를 검색할 수 있도록 한 구조이다

이중 연결 리스트 삽입

데이터 항목 B와 D사이에 새로운 데이터 항목 C를 삽입하는 과정은 다음과 같다.

새로운 노드를 생성한 후, 생성된 노드에 데이터 항목 C를 대입한다. 이 경우 데이터 항목 C를 저장한 노드를 가리키는 것은 Z이다.
• B노드의 RLINK 값을 Z의 RLINK에 저장한다. 여기서 B 노드의 주소를 X가 가지고 있으므로, B노드의 RLINK는 X의 RLINK가 될 수 있다.
• B노드의 주소, 즉 X의 값을 Z의 LLINK에 대입한다.
• X의 RLINK가 가리키는 노드인 D 노드의 LLINK에 Z의 값을 대입한다.
• X의 RLINK에 Z의 값을 저장한다.

이중 연결 리스트 삭제

이중 연결 리스트를 구성하는 임의의 노드 X를 삭제하는 알고리즘 DELETE는 다음과 같다.

• B노드의 RLINK에 C노드의 RLINK 값을 대입한다. 여기서 B 노드의 RLINK 값은 C노드를 가리키는 X의 LLINK가 가리키는 노드(B노드)의 RLINK 값이다.
• D노드의 LLINK에 C노드의 LLINK 값을 대입한다. 여기서 D노드의 LLINK 값은 C노드를 가리키는 X의 RLINK가 가리키는 노드(D노드)의 LLINK 값이다.
• X가 가리키고 있는 C노드를 가용 기억공간으로 되돌린다. 즉 C노드는 이중 연결 리스트에서 삭제된다.

이중 연결 리스트 장.단점

장    점	단    점
임의의 노드를 검색할 때 양 방향으로 접근할 수 있다.  임의의 노드의 연결이 파괴되었을 때 복구가 가능하다.	전위와 후위 연결을 위한 포인터 기억 공간이 필요하다.