이중 연결 리스트(Double Linked List)는 앞에서 다뤘던 Simple Linked List와 함께 가장 많이 사용되는 연결 리스트의 형태다.
단순 연결리스트가 다음의 노드를 가리키는 하나의 링크만을 가져서 바로 전의 노드를 알 수 없던 단점에 비해서, 이중 연결 리스트는 다음의 노드를 가리키는 링크와, 바로 전 노드를 가리키는 링크 2가지를 가지고 있다는점이 큰 장점이다.
물론! 하나의 링크를 더 사용하기 때문에 약간의 메모리를 더 사용하겠지만, 낭비는 아니라고 생각한다!
Double Linked List의 모습
기본적인 Double Linked List의 모습
기본적인 Linked List와 개념적인 모습에는 큰 차이는 없다, 다만 previous node를 가리키는 link가 하나가 더 생겼을뿐!
초기화
typedef struct _node {
int key;
struct _node *prev;
struct _node *next;
} node;
node *head;
node *tail;
void init_list(void) {
head = (node *)malloc(sizeof(node));
tail = (node *)malloc(sizeof(node));
head->prev = head;
head->next = tail;
tail->prev = head;
tail->next = tail;
}초기화 하는 함수또한 크게 차이는 없다.
다만 노드를 삽입하거나 혹은 삭제할경우 조작해야할 링크가 기존의 2개에서 4개로 늘어나서 조금 복잡해진다는 단점이 있다.
여기서 눈여겨 봐야할 부분은 head->prev = head와 tail->next = tail부분인데, list의 link가 외부로 벗어나면서 잘못된 메모리를 참조하는 일이 없도록 하기 위함과 동시에 list의 처음과 끝을 명확하게 명시해주기 위해서이다.
초기화 이후의 Double Linked List의 모습
Double Linked List의 구조
앞 노드를 가리키는 포인터를 prev, 뒷 노드를 가리키는 포인터를 next라고 부를 예정!
노드 삽입하기
node *insert_front(int key, node *t) {
node *new;
if(t == head) {
return NULL;
}
new = (node *)malloc(sizeof(node));
new->key = key;
t->prev->next = new;
new->prev = t->prev;
t->prev = new;
new->next = t;
return new;
}t노드 앞에 key를 값으로 가지는 새로운 노드를 추가하는 함수다.
사실 개념적으로 다를건 없지만, 링크를 4개나 조작해야 하기 때문에 거부감이 들수도 있지만 아래 그림처럼 하나하나 살펴보면 전혀 어렵지 않다!
새로 삽입할 New 노드 생성 후 List의 모습
t->prev->next = new; 실행 후
new->prev = t->prev; 실행 후
t->prev = new; 실행 후
new->next = t; 실행 후
노드 삭제하기
int delete_node_ptr(node *t) {
if(t == head || t == tail) {
return 0;
}
t->prev->next = t->next;
t->next->prev = t->prev;
free(t);
return 1;
}다음으로 살펴볼 코드는, 특정 노드를 삭제하는 함수다.
삽입과 삭제하는 부분과 링크를 재조정하는것만 잘 이해한다면 사실상 list는 어려운게 없다고 생각하기에 이거 2개만 좀 그림그려가면서 정리해두려고 한다.
여튼! 삭제하고자 하는 노드가 head 혹은 tail이라면 삭제해서는 안된다.
왜냐면 삭제해버리면 list의 시작하는 부분과 끝나는 부분이 어디인지 명확하게 알 수 없고, 이는 정상적으로 리스트를 순회할 수 없어짐과 동시에 나가아서 잘못된 메모리를 참조하면서 프로그램이 다운되는 일까지 야기할 수 있기 때문이다.
따라서 삭제하고자 하는 노드가 머리나 꼬리가 아닐때에만 삭제가 가능하다.
삭제하는것도 생각보다 단순한데, "삭제하고자 하는 노드의 앞과 뒤 노드"의 링크만 서로 이어주면 된다.
간단!
t노드를 삭제하기 전 List의 상태
t->prev->next = t->next; 실행 후
t->next->prev = t->prev; 실행 후
free(t); 실행 후
전체코드
//
// main.c
// Double Linked List
//
// Created by 박재현 on 2024/05/05.
//
#include <stdio.h>
#include <stdlib.h>
typedef struct _node {
int key;
struct _node *prev;
struct _node *next;
} node;
node *head;
node *tail;
void init_list(void) {
head = (node *)malloc(sizeof(node));
tail = (node *)malloc(sizeof(node));
head->prev = head;
head->next = tail;
tail->prev = head;
tail->next = tail;
}
node *insert_front(int key, node *t) {
node *new;
if(t == head) {
return NULL;
}
new = (node *)malloc(sizeof(node));
new->key = key;
t->prev->next = new;
new->prev = t->prev;
t->prev = new;
new->next = t;
return new;
}
int delete_node_ptr(node *t) {
if(t == head || t == tail) {
return 0;
}
t->prev->next = t->next;
t->next->prev = t->prev;
free(t);
return 1;
}
node *find_node(int k) {
node *s;
s = head->next;
while(s->key != k && s != tail) {
s = s->next;
}
return s;
}
int delete_node(int k) {
node *s;
s = find_node(k);
if(s != tail) {
s->prev->next = s->next;
s->next->prev = s->prev;
return 1;
}
return 0;
}
// t를 갖고있는 node 앞에 k를 갖는 노드를 삽입
node *insert_node(int k, int t) {
node *s;
node *i = NULL;
s = find_node(t);
if(s != tail) {
i = (node *)malloc(sizeof(node));
i->key = k;
s->prev->next = i;
i->prev = s->prev;
s->prev = i;
i->next = s;
}
return i;
}
node *ordered_insert(int k) {
node *s;
node *i;
s = head->next;
while(s -> key <= k && s != tail) {
s = s->next;
}
i = (node *)malloc(sizeof(node));
i->key = k;
s->prev->next = i;
i->prev = s->prev;
s->prev = i;
i->next = s;
return i;
}
void print_list(node *p) {
printf("\n");
while(p != tail) {
printf("%-8d", p->key);
p = p->next;
}
printf("\n");
}
void delete_all(void) {
node *p;
node *s;
p = head->next;
while(p != tail) {
s = p;
p = p->next;
free(s);
}
head->next = tail;
tail->prev = head;
}
int main(int argc, const char * argv[]) {
node *t;
init_list();
ordered_insert(10);
ordered_insert(5);
ordered_insert(8);
ordered_insert(3);
ordered_insert(1);
ordered_insert(7);
ordered_insert(8);
printf("\nInitial Linked list status as below");
print_list(head->next);
printf("\nFinding 4 is %ssuccessful\n", find_node(4) == tail ? "un" : "");
t = find_node(5);
printf("\nFinding 5 is %ssuccessful\n", t == tail ? "un" : "");
printf("\nInserting 7 before 5");
insert_front(7, t);
print_list(head->next);
t = find_node(3);
printf("\nDeleting 3");
delete_node_ptr(t);
print_list(head->next);
printf("\nInserting node 2 before 10");
insert_node(2, 10);
print_list(head->next);
printf("\nDeleting node 2");
if(!delete_node(2)) {
printf("\nDeleting 2 is fail");
}
print_list(head->next);
printf("\nDeleting node 1");
delete_node(1);
print_list(head->next);
printf("\nInserting 15 at first");
insert_front(15, head->next);
print_list(head->next);
printf("\nDeleting all node");
delete_all();
print_list(head->next);
return 0;
}실행결과
