이중 연결 리스트

단순 연결 리스트에서 어떤 노드에서 후속 노드를 찾기는 쉽지만, 선행 노드를 찾으려면 구조상 아주 어렵다. 원형 연결 리스트라고 하더라도 거의 전체 노드를 거쳐서 돌아 와야 한다. 따라서 응용 프로그램에서 특정 노드에서 양방향으로 자유롭게 움직일 필요가 있다면 단순 연결 리스트 구조는 부적합하다. 이중 연결 리스트는 이러한 문제점들을 해결하기 위하여 만들어진 자료구조 이다.

 

이중 연결 리스트는 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트이다. 링크가 양방향이므로 양방향으로 검색이 가능해진다. 단점으로는 공간을 많이 차지하고 코드가 복잡해진다는 것이다. 그러나 그럼에도 불구하고 여러 가지 장점이 많기 때문에 널리 쓰인다. 

 

실제 응용에서는 이중 연결 리스트와 원형 연결 리스트를 혼합한 형태가 많이 사용된다. 또 헤드 노드(head node) 라는 특별한 노드를 추가하는 경우가 많다. 헤드 포인터와는 구별하여야 한다. 헤드 포인터는 리스트의 첫 번째 노드를 가리키는 포인터이고, 헤드 노드는 데이터를 가지고 있지 않은 특별한 노드를 추가하는 것이다. 헤드 노드가 존재하게 되면 삽입, 삭제 알고리즘이 간편해진다. 헤드 노드의 데이터 필드는 아무런 정보도 담고 있지 않다. 다만 삽입과 삭제 알고리즘을 간편하게 하기위해 존재한다.  이제 이중연결 리스트를 구현해보자. 먼저 노드의 구조를 확인해야 하는데 이중연결 리스트에서의 노드는 3개의 필드(왼쪽 링크 필드, 데이터 필드, 오른쪽 링크 필드) 로 이뤄져 있다. 링크 필드는 포인터로 이뤄져있다. 이중연결 리스트에서 임의의 노드를 가리키는 포인터를 p이라 하면 아래와 같은 관계가 항상 성립한다.

p = p->llink->rlink = p->rlink->llink

즉 앞뒤로 똑같이 이동할 수 있음을 나타낸다. 이러한 관계는 공백 리스트에서도 성립한다.

 

노드의 구조를 구조체를 이용하여 정의해보면 다음과 같다.

typedef int element;
typedef struct DListNode {
  element data;
  struct DListNode *llink;
  struct DListNode *rlink;
} DListNode;

 

• 삽입 연산

아래의 그림과 같이 그림의 순서대로 링크 필드의 값을 바꾸면 된다. 새로 만들어진 노드의 링크를 먼저 바꾸는 것을 알 수 있다. 새로 만들어진 노드의 링크는 아무런 정보도 가지고 있지 않기 때문에 변경하여도 안전하기 때문이다.

//새로운 데이터를 노드 before 의 오른쪽에 삽입한다
void dinsert(DListNode *before, element data)
{
  DListNode *newnode = (DListNode *)malloc(sizeof(DListNode));
  newnode -> data = data;
  newnode->llink = before;
  newnode->rlink = before->rlink;
  before->rlink->llink = newnode;
  before->rlink = newnode;
}

 

 

• 삭제연산

링크들의 값을 변화시키면 된다

//노드 removed 를 삭제한다
void ddelete(DListNode *head, DListNode *removed)
{
  if (removed == head) return;
  removed->llink->rlink = removed->rlink;
  removed->rlink->llink = removed->llink;
  free(removed);
}