[알고리즘] 이중 연결 리스트

이중 연결 리스트

• 하나의 노드가 선행 노드의 대한 링크와 후속 노드의 대한 링크를 가지고 있는 구조
• 장점
  • 링크가 양방향이므로 양방향 탐색이 가능하다
• 단점
  • 공간을 많이 차지하므로 코드가 복잡하고 구현이 어렵다.

 

실제로 사용되는 연결리스트의 구조는 아래와 같다.

• 헤드 노드 + 이중 연결리스트 + 원형 연결리스트

이중 연결 리스트 노드의 구조

• 3개의 필드로 구성되어 있다.
  • 왼쪽 링크 필드, 데이터 필드, 오른쪽 링크 필드

 

• 임의의 노드를 가리키는 포인터를 p라고 가정하면
  • p = p->llink -> rlink = p -> rlink -> llink 가 항상 성립한다.

 

• 단순, 원형 연결리스트와는 다르게 이중 연결 리스트는 헤드 노드를 가진다.
  • 헤드 포인터와는 다르다는 것을 명심해야 한다.
• 헤드노드란?
  • 데이터를 가지지 않고 단지 삽입, 삭제 코드를 간단하게 할 목적으로 만들어진 노드
  • 헤드 포인터와 구별해야 한다.
  • 공백 상태에서는 헤드 노드만 존재한다.

이중 연결 리스트 구조체 노드 정의

 

typedef int element;
typedef struct DlistNode {
	element data; // 데이터 필드
	struct DlistNode* llink; // 선행 노드를 가리키는 포인터
	struct DlistNode* rlink; // 후속 노드를 가리키는 포인터
} DlistNode;

typedef int element를 해준 이유는 추후 데이터 값이 int가 될 수도 있고, float가 될 수도 있기 때문에 코드 수정을 용이하게 하기 위해 element 타입을 생성해준 것이다.

 

이중 연결 리스트 삽입 연산

• 순서가 중요하다!
  • link를 마구잡이로 옮기면 선행 노드와 후속 노드에 대한 link를 잃게 될 수도 있기 때문이다.

void insert_node(DlistNode* before, DlistNode* new_node) {
	new_node->llink = before;
	new_node->rlink = before->rlink;
	before->rlink->llink = new_node;
	before->rlink = new_node
}

before노드의 앞에 삽입하는 것으로 기준을 삼는다.

 

순서

1. new_node의 llink가 before 노드를 가리키게 한다.
2. new_node 의 rlink가 후속 노드(before->rlink)를 가리키게 한다.
3. 후속노드(before->rlink)의 llink가 new_node를 가리키게 한다.
4. before 노드의 rlink가 new_node를 가리키게 한다.

3번을 자세히 보면 

'후속노드의 llink가 ~'라고 써있다. 하지만 후속 노드의 정보는 인자에서 주어지지 않았다. 하지만 후속 노드의 대한 위치는 before노드의 rlink가 가리키고 있다.

 

그리하여 후속 노드의 llink는 before->rlink->llink가 되는 것이다.

 

이중 연결 리스트 삭제 연산

• 삽입에 비해 간단하다.
• 하지만 삭제 연산에는 꼭 free()를 해주어 메모리를 초기화시켜야 한다.

void delete_node(DlistNode* phead_node, DlistNode* removed) {
	if (removed == phead_node) return;

	removed->llink->rlink = removed->rlink;
	removed->rlink->llik = removed->llink;
	free(removed);
}

delete_node의 인자는 헤드노드, 삭제할 노드이다.

순서

1. 삭제할 노드의 선행 노드(removed->llink)의 rlink를 후속 노드(removed->rlink)를 가리키게 한다.
2. 삭제할 노드의 후속 노드(removed->rlink)의 llink를 선행 노드(removed->llink)를 가리키게 한다.