이중연결리스트

단방향 연결 리스트(single linked list)의 한계:

• 어떤 노드의 앞에 새로운 노드를 삽입하기 어렵다
• 삭제의 경우에 항상 삭제할 노드의 앞 노드가 필요하다
• 단방향의 순회만이 가능하다

이중 연결 리스트

• 각각의 노드가 다음(next) 노드와 이전(previous) 노드의 주소를 가지는 연결 리스트
• 양방향의 순회(traverse)가 가능하다

 

 

 

 

 

 

Node

 

struct node {
 	char *data;      /* 각 노드에 하나의 문자열이 저장된다고 가정함 */
 	struct node *next;
 	struct node *prev;
};

typedef struct node Node;

Node *head;
Node *tail;
int size = 0;

 

 

앞서 단방향 연결리스트(Single linked list)에서 ①search(검색), ②add, ③remove, ④traverse(순회) 의 경우를 다루었었는데, 이중연결리스트는 search과 traverse에서 단방향 연결리스트와 차이점이 없다.

 

<단방향 연결리스트에 대한 게시물>

2021.08.02 - [자료구조] - 연결리스트 - 삽입하기

2021.08.04 - [자료구조] - 연결리스트 - 삭제하기

2021.08.04 - [자료구조] - 연결리스트 - 순회하기

2021.08.04 - [자료구조] - 연결리스트 - 함수들 정리

 

add, remove 는 차이점이 존재할 수 있는데, 그 이유는 next 노드와 prev 노드가 존재하기 때문이다. 따라서 이중연결리스트의 add 와 remove에 대해서 정리해볼 것이다.

 

 

 

 

 

 

노드 삽입

 

Node *new_node = (Node *)malloc(sizeof(Node));
new_node->data = "Sharon";

new_node->next = p;
new_node->prev = p->prev;
p->prev->next = new_node;
p->prev = new_node;

 

앞 두 줄은 새로운 노드를 생성하는 코드문이다.  다음 네 줄은 새로운 노드를 삽입하는 과정인데 아래 그림과 같이 보면 이해하기 쉽다.

 

harry와 poter 사이에 sharon 을 삽입하는 과정

 

1번과 2번을 통해 새로운 노드를 먼저 연결시켜주어야 한다. 

 

3번과 4번의 순서가 바뀌면 안 되는 이유는 p→prev를 먼저 new_node로 바꿔버리면 이전 노드에 접근할 방법이 없어지기 때문이다.

 

 

하지만 이 경우는 두 노드 사이에 삽입하는 일반적인 경우이고 여러가지 경우에 따라 다르게 작성을 해줘야 한다. 4가지의 경우를 기억하자.

 

• 연결리스트가 empty 인 상태에서 삽입
• 맨 앞 삽입
• 맨 뒤 삽입
• 두 노드 사이에 삽입

 

 

 

 

 

노드 삭제

이중 연결리스트의 장점은 노드를 삭제할 때 "이전 노드의 주소가 필요 없다" 는 것이다.

예를 들어 p노드가 "harry" 와 "poter" 노드 사이에 있었고 p노드를 삭제하는 경우, 다음과 같다.

 

p 노드만 삭제하면 된다. 이전 노드의 주소가 필요 없다.

 

p->prev->next = p->next 
p->next->prev = p->prev

 

이 또한 head, tail 노드가 아닌 일반적인 경우이다. 삽입과 마찬가지로 여러가지 경우를 고려해야 한다.

 

• p가 유일한 노드일 경우
• p가 head인 경우
• p가 tail인 경우
• 그 밖의 일반적인 경우

 

 

 

 

 

여러가지 경우를 고려한 삽입

앞서 일반적인 경우에서 노드의 삽입, 삭제 하는 방법을 알아보았고, 이제 여러가지 경우(= 4가지)에 따라 삽입, 삭제 하는 방법을 알아보겠다. 먼저 삽입을 보자.

 

void add_after(Node *pre, char *item) {
	/* 새로운 노드 생성하고 초기화하기 */
	Node *new_node = (Node *)malloc(sizeof(Node));
	new_node->data = item;
	new_node->prev = NULL;
	new_node->next = NULL;

	if (pre == NULL && head == NULL) {       /* 1. 연결리스트가 empty 인 상태에서 삽입 */
		head = new_node;
		tail = new_node; 
	} 
    else if (pre == NULL) {       /* 2. 연결리스트의 맨 앞에(head 앞에) 삽입 */
		new_node->next = head;
		head->prev = new_node;
		head = new_node;
	} 
    else if (pre == tail) {        /* 3. 연결리스트의 맨 뒤에 삽입 */
		new_node->prev = tail;
		tail->next = new_node;
		tail = new_node;
	} 
    else {                         /* 4. 연결리스트의 중간에 삽입 */
		new_node->next = pre->next;
		new_node->prev = pre;
		pre->next->prev = new_node;
		pre->next = new_node; 
	/* 처음 두 줄 순서는 바뀌어도 OK */}

	size++;
}

 

add_after 함수의 매개변수는 이전 노드를 가리키는 pre 와 문자열이다. pre 노드의 다음에 삽입해야 한다.

 

 

 

 

 

 

 

 

 

 

 

여러가지 경우를 고려한 삭제

노드 삭제는 이중 연결리스트의 진가가 발휘되는 부분이라고 했다. (= 이전 노드의 주소가 필요 없음, p만 삭제)

다음과 같은 4가지 경우는 이렇게 생각해볼 수 있다.

 

• p가 유일한 노드일 경우 ▶ head와 tail을 NULL 로 변경
• p가 head인 경우 ▶ head 변경
• p가 tail인 경우 ▶ tail 변경
• 그 밖의 일반적인 경우 ▶ head와 tail은 고정

 

void remove(Node* p)
{
	if (p->prev == NULL && p->next == NULL)	// p가 유일한 노드
	{
		head = NULL;
		tail = NULL;
		free(p);
	}
	else if (p->prev == NULL)	// p가 head인 경우
	{
		head = p->next;
		free(p);
	}
	else if (p->next == NULL)	// p가 tail인 경우
	{
		tail = p->prev;
		free(p);
	}
	else	// p가 중간에 위치한 노드인 경우
	{
		p->prev->next = p->next;
		p->next->prev = p->prev;
		free(p);
	}
}