(C/C++) 양방향/이중 연결리스트 구현하기 [Double Linked List] (삽입, 삭제, 탐색)

더블 링크드리스트에 대해 알아보자.

>> 이전 글에서 싱글 리스트 구현법에 대해 알아보았다. 아래 글 참고!!
[REAL Code] - (C/C++) 단방향 연결리스트 [Single Linked List] (삽입, 삭제)

(C/C++) 단방향 연결리스트 [Single Linked List] (삽입, 삭제)

더블 링크드리스트는 양방향성을 갖는 리스트로
필자와 C언어 기반으로 구현해가며
초기화, 삽입, 삭제, 탐색 순서대로 함께 알아보자.

1) 초기화

싱글 리스트에 비해 포인터가 하나더 추가되지만 원리를 이해하면 간단하다.
Node *prev는 Tail으로부터의 방향성을
Node *next는 Head로 부터의 방향이라 생각하면 된다.

struct Node 
{ 
	int data; 
	Node* prev; 
	Node* next; 
} node[MAXNODE];

그리고 지난 싱글리스트 구현에서 사용한 myalloc()함수를 추가해준다.
노드를 추가할때 사용하는 함수인데 일반적으로 getNode 라는 이름으로 많이 사용하기도 한다.

Node* myalloc() 
{ 
	return &node[arr_idx++]; 
}

더블 리스트에서 초기화 상태는 head의 포인터가 tail을 향하도록
tail의 포인터가 head를 향하도록 초기화 해준다.
초기화 상태가 리스트에 노드가 비어있음을 의미하며
if(head->next == tail) 를 만족하면 노드가 비어있는 상태이다.

void init() 
{ 
	arr_idx = 0; 
	head = myalloc(); 
	tail = myalloc(); 
	head->next = tail; 
	tail->prev = head; 
}

더블리스트 초기화

 

2) 삽입

더블 리스트의 삽입은
head쪽으로 삽입하는 방법과 tail쪽으로 삽입하는 2가지 방법이 있는데,
순서대로 모두 알아보도록 하자.

- head쪽으로 삽입

순서 0. 노드 생성
: 임의의 노드를 생성하여 값을 할당해준다.
Node* pp = myalloc();
pp->data = data;

순서 1.
: 노드의 next 포인터를 head next로 가져온다.

노드삽입 순서 1

pp->next = head->next;

순서 2.
: head의 next는 노드 (pp)를 가리키도록 한다.
head->next = pp;

노드삽입 순서2

순서 3.
: 노드(pp)의 prev 는 tail를 head를 향하는 포인터로 카피한다.
pp->prev = pp->next->prev;

노드삽입 순서3

순서 4.
마지막으로 tail를 노드(pp) 향도록하면 노드 삽입이 마무리 된다.

노드삽입 순서4

void addtoHead(int data) 
{ 
	Node* pp = myalloc();  // 순서0 
	pp->data = data; 
	pp->next = head->next; // 순서1 
	head->next = pp;       // 순서2 
	pp->prev = pp->next->prev; // 순서3 
	pp->next->prev = pp; // 순서4 
}

 

- tail쪽으로 삽입

tail쪽으로의 삽입도 head쪽으로 삽입과 크게 다르지 않다.
next와 prev의 방향만 반대로 해주면 모든 순서가 같음을 알 수 있다.

노드삽입 순서1

노드삽입 순서2

노드삽입 순서3

노드삽입 순서4

tail방향 삽입 소스코드

void addtoTail(int data) 
{ 
	Node* pp = myalloc(); // 순서0 
	pp->data = data; 
	pp->prev = tail->prev; // 순서1 
	tail->prev = pp; // 순서2 
	pp->next = pp->prev->next; // 순서3 
	pp->prev->next = pp; // 순서4 
}

 

3) 삭제

삭제는 오히려 싱글 리스트보다 단순해서
싱글 리스트보다 더블 리스트를 선호하는 분들이 있는 편이다.
리스트가 아래와 같이 연결되어 있을때
pp 노드를 삭제하고자 한다면,

초기 리스트

순서 1.
pp->next->prev = pp->prev 를 통해
tail이 head를 가리도록 해주고

노드삭제 순서1

순서 2.
pp->prev->next = pp->next 를 통해
head가 tail을 가리키도록 하면 삭제가 마무리 된다.

노드삭제 순서2

pp가 남아 있는듯 보일 수 있지만, 삭제와 동시에 리스트에서 접근할 수 있는 방법이 없기 때문에
알고리즘을 구현하고 공부할때 전혀 문제가 없다.
삭제시 순서1과 순서2의 순서는 상관없다.

void delNode(int data) 
{ 
	for (Node* pp = head->next; pp != tail; pp = pp->next) 
	{ 
		if (pp->data == data) 
		{ 
			pp->next->prev = pp->prev; // 순서 1 
			pp->prev->next = pp->next; // 순서 2 
			break; 
		} 
	} 
}

 

4) 탐색

이중 리스트의 탐색에서 싱글리스트와 다른점은
head에서부터 탐색할때는 tail이 아닐때까지,
tail에서부터 탐색할대는 head가 아닐때까지 만 유의해주면 된다.
아래 코드는 head에서부터 탐색할때 코드이고
for (Node* pp = head->next; pp != tail; pp = pp->next) 부분만
for (Node* pp = tail->prev; pp != head; pp = pp->prev) 로 바꾸면 tail에서부터의 탐색이 된다.

void search(int data) 
{ 
	for (Node* pp = head->next; pp != tail; pp = pp->next) 
	{ 
		if (pp->data == data) 
		{ 
			printf("find : %d\n", data); 
			break; 
		} 
	} 
}

다음은 전체 소스코드 공유 ~!

#include <stdio.h> 
#define MAXNODE 100 
struct Node 
{ 
	int data; 
	Node* prev; 
	Node* next; 
} node[MAXNODE]; 

int arr_idx; 
Node* head, * tail; 
Node* myalloc() 
{ 
	return &node[arr_idx++]; 
} 

void init() 
{ 
	arr_idx = 0; 
	head = myalloc(); 
	tail = myalloc(); 
	head->next = tail; 
	tail->prev = head; 
} 

void addtoHead(int data) 
{ 
	Node* pp = myalloc(); 
	pp->data = data; 
	pp->next = head->next; 
	head->next = pp; 
	pp->prev = pp->next->prev; 
	pp->next->prev = pp; 
} 

void addtoTail(int data) 
{ 
	Node* pp = myalloc(); 
	pp->data = data; 
	pp->prev = tail->prev; 
	tail->prev = pp; 
	pp->next = pp->prev->next; 
	pp->prev->next = pp; 
} 

void search(int data) 
{ 
	for (Node* pp = head->next; pp != tail; pp = pp->next) 
	{ 
		if (pp->data == data) 
		{ 
			printf("find : %d\n", data); 
			break; 
		} 
	} 
} 

void delNode(int data) 
{ 
	for (Node* pp = head->next; pp != tail; pp = pp->next) 
	{ 
		if (pp->data == data) 
		{ 
			pp->next->prev = pp->prev; 
			pp->prev->next = pp->next; 
			break; 
		} 
	} 
} 

void print_all() 
{ 
	for (Node* pp = head->next; pp != tail; pp = pp->next) 
	{ 
		printf("%d ", pp->data); 
	} 
		printf("\n"); 
} 

int main(void) 
{ 
	init(); 
    
	addtoHead(10); 
	addtoHead(20); 
	addtoHead(30); 
	addtoHead(40); 
	print_all(); 
	addtoTail(100); 
	addtoTail(200); 
	print_all(); 
	delNode(20); 
	delNode(100); 
	print_all(); 
    
    
	return 0; 
}

그리고 실행결과

소스코드는 제가 즉흥적으로 작성한 코드입니다.
공부할때 도움이 됐으면 좋겠네요~!
감사합니다.

(C/C++) 양방향/이중 연결리스트 구현하기 [Double Linked List] (삽입, 삭제, 탐색)

레알북 : https://real-book.tistory.com

Real Book