[C언어/자료구조] 이중 연결리스트(double linked list)

※ 인프런 무료강좌 C로 배우는 자료구조(권오흠 교수님)를 보고 개인적인 복습을 위해 정리한 내용입니다.

---

단방향 연결리스트(single linked list)

각 노드가 다음 노드의 주소만를 가지고 있음.

새로운 노드를 삽입하거나 삭제하려면 반드시 이전 노드의 주소가 필요함.

연결리스트의 첫번째 노드 주소를 담을 포인터(head)가 필요함

한쪽방향으로의 순회(traverse)만 가능하다.

 

이중/양방향 연결리스트(double linked list)

각 노드가 이전 노드의 주소(prev)와 다음 노드의 주소(next)를 모두 가지고 있음.

연결리스트의 첫번째 노드 주소를 담을 포인터(head)와 마지막 노드 주소를 담을 포인터(tail) 두 가지가 필요함.

양방향으로 순회(traverse)가 가능하다.

struct node {
	char *data;
	struct node next;
	struct node prev;
};

typedef struct node Node;

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

 

이중연결리스트에서 

검색(search), 순회(traverse)의 경우 단방향 연결리스트일 때와 크게 다르지 않다.

그러나 삽입(add)이나 삭제(remove)의 경우 차이가 있기 때문에 살펴볼 필요가 있다.

 

노드 삽입 (add)

어떤 노드(p) 앞에 새로운 노드를 삽입하는 경우

/* 새로운 노드 생성하고 데이터 저장 */
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;

1. new_node를 먼저 앞뒤 노드에 연결한 다음,

2. 이전 노드의 next 필드에 new_node를 연결하고

3. 다음 노드(p)의 prev 필드에 new_node를 연결한다.

 

2번과 3번의 순서가 바뀌면 안 되는 이유

이전 노드의 next 필드 : 다음 노드(p)의 prev필드를 통해 접근해야 하기 때문.

이전 노드의 next 필드를 바꾸기 전에 p→prev를 먼저 new_node로 바꿔버리면

이전 노드에 접근할 방법이 없어진다.

 

노드 삭제 (remove)

p가 가리키는 노드를 삭제하는 경우(노드 p가 head나 tail이 아닐 때)

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

 

 

이중 연결리스트를 다루는 함수 만들기

 

add_after() 함수

어떤 노드 에 새로운 노드 추가하기

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) { //비어있는 연결리스트에 삽입
		head = new_node;
		tail = new_node; 
	} else if (pre == NULL) { //연결리스트의 맨 앞에(head 앞에) 삽입
		new_node->next = head;
		head->prev = new_node;
		head = new_node;
	} else if (pre == tail) {
		new_node->prev = tail;
		tail->next = new_node;
		tail = new_node;
	} else { //연결리스트의 중간에 삽입
	new_node->next = pre->next;
	new_node->prev = pre;
	pre->next->prev = new_node;
	pre->next = new_node; 
	/* 처음 두 줄 순서는 바뀌어도 OK */}

	size++;
}

 

remove() 함수

p가 유일한 노드일 때 / p가 head일 때 / p가 tail일 때 / 그 밖의 일반적인 경우로 나눠서 생각한다.

Polynomial *remove(Polonomial *p) {
	
	if (p->prev == NULL && p->next == NULL) {
		head = NULL;
		tail = NULL;
	}	else if (p->prev == NULL) {
		head = p->next;
	} else if (p->next == NULL) {
		tail = p->prev;
	} else 
		p->next->prev = p->prev;
		p->prev->next = p->next;
		p->next = NULL;
		p->prev = NULL;
	}
	return p;
}

 

add_ordered_list() 함수

데이터의 알파벳 순서 정렬을 유지하면서 새로운 노드 추가하기

void add_ordered_list(char *item) {
	Node *p = tail;
	while (p!=NULL && strcmp(item, p->data) < 0) {
		p = p->prev;
	}
	add_after(p, item);
}

뒤에서부터 앞으로 순회하면서 d보다 작은 알파벳을 가진 노드를 발견하면, 그 노드 바로 뒤에 add_after함수 이용해 새로운 노드 삽입.

 

원형 연결리스트 (circular list)

원형 연결리스트 : 마지막 노드의 다음 노드가 첫번째 노드가 되는 단순 연결리스트

원형 이중연결리스트 : 마지막 노드의 다음 노드가 첫번째 노드가 되고, 첫 노드의 이전 노드가 마지막 노드가 됨.