[C언어] 이중 연결 리스트

이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;)

---

 

단방향 연결 리스트와 이중 연결 리스트

단방향 연결 리스트는 자신의 이전 노드의 주소는 알지 못하고 오직 다음 노드의 주소만 알 수 있다는 특징을 가지고 있습니다. 때문에 특정 노드를 삭제하기 위해서는 항상 삭제하려는 노드 바로 앞 노드의 주소를 알고 있어야 한다는 불편함을 가지고 있습니다.

이러한 불편함을 해결하기 위한 자료구조가 바로 이중 연결 리스트입니다.

---

next: 자신의 다음 노드의 주소

prev: 자신의 이전 노드의 주소

첫 번째 노드의 prev와 마지막 노드의 next는 NULL.

 

단방향에 노드에서 head 노드가 중요했듯이, 이중 연결 리스트에서는 head 노드와 tail 노드 모두 중요합니다. tail 노드를 통해서도 순회가 가능하기 때문입니다.

 

p->prev가 이전 노드로 향하는 유일한 주소. 때문에 이전 노드로 향하는 길을 잃지 않기 위해 가장 마지막에 변경해야 합니다.

 

이중 연결 리스트의 장점은 노드를 삭제할 때 부각됩니다. 위의 그림과 같이 p 노드를 삭제한다면, p의 이전 노드의 next 노드와 p의 다음 노드의 prev 노드만 변경해주면 되기 때문입니다. 단방향 연결 리스트에서 p 노드를 삭제하려면 p 노드 이전 순서의 노드 주소를 반드시 알아야 했던 점과 비교하면 엄청난 효용을 지니고 있다는 걸 알 수 있습니다.

---

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node
{
	char* data;
	struct node* next;	// 각 노드는 다음 노드의 주소와
	struct node* prev;	// 이전 노드의 주소를 가지고 있음
}Node;

Node* head;
Node* tail;
int size = 0;	// 현재 노드의 개수를 관리하는 변수

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)	// empty list
	{
		head = new_node;
		tail = new_node;
	}
	else if (pre == NULL) // 연결 리스트의 맨 앞에 삽입
	{
		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->prev = pre;
		pre->next->prev = new_node;
		new_node->next = pre->next;
		pre->next = new_node;
	}
	size++;	// 노드의 개수 증가
}

---

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;
		head->prev == NULL;
		free(p);
	}
	else if (p->next == NULL)	// p가 tail인 경우
	{
		tail == p->prev;
		tail->next == NULL;
		free(p);
	}
	else	// p가 중간에 위치한 노드인 경우
	{
		p->prev->next = p->next;
		p->next->prev = p->prev;
		free(p);
	}
}

---

void add_ordered_list(char* item)	// 리스트가 정렬되어 있을 때
{
	Node* p = tail;
	while (p != NULL && strcmp(item, p->data) < 0)	// 뒤에서 앞으로 순회
		p = p->prev;	
	add_after(p, item); // 자신보다 큰 값의 앞 노드 뒤에 추가
	// 1. 리스트가 비어 있을 때
	// 2. 리스트의 맨 앞에 삽입할 때
	// 3. 리스트의 맨 뒤에 삽입할 때
	// 4. 중간에 삽입할 때 모두 가능
}