[자료구조] 이중 연결 리스트
✔️ 이중 연결 리스트란?
[자료구조] 연결 리스트:
https://slumpdev.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8
이중 연결 리스트를 알려면 우선,
연결 리스트에 대하여 공부를 해야하는데 앞선 글을 참고하자.
이중 연결 리스트, Double Linked List는 자료구조에서 나오는
하나의 개념이다. 간단하게 줄여서 DLL이라고 부르는데,
이중 연결 리스트는 하나의, 단일의 연결 리스트에 있는 다음(Next) 포인터 및 데이터와
일반적으로 바로 이전(Prev) 포인터라고 하는 추가 포인터를 포함하는 개념이다.
해당 개념을 도식화하면 다음과 같은 그림으로 나타낼 수 있다.
해당 그림만으로는 쉽게 이해가 가지 않는데,
가장 앞에 위치한 노드는 head라는 포인터가 가리키게 된다.
그리고 tail이라는 포인터는 가장 뒤에 위치한 노드를 가리키게 된다.
이러한 이중 연결 리스트에 데이터를 추가하기 위해서는
여러가지 노드가 삽입되는 과정이 존재한다.
✔️ 이중 연결 리스트에 추가, 삽입
head로 연결된 노드와 tail로 연결된 노드만 존재할 때,
중간에 새로운 데이터를 가진 노드를 삽입하는 방법이 존재한다.
해당 과정을 도식화한 그림인데, 이러한 과정으로 삽입된다면
① new -> prev = head -> next
② new -> next = tail -> prev
③ head -> next = tail -> prev = new
④ head -> next = new
우선, new 노드의 prev 링크는 이전 head 노드의 next를 가리키게 된다.
그리고 new 노드의 next 링크는 다음 tail 노드의 prev를 가리키게 된다.
이전 head 노드는 tail 노드의 prev를 가리키고 있었고,
해당 prev 링크가 삽입될 new 노드를 가리키게 된다.
마지막으로 이전 head 노드가 new 노드를 가리키게 된다.
✔️ 이중 연결 리스트 삽입 구현.c (1)
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
int main()
{
struct Node* head = NULL;
struct Node* tail = NULL;
head = (struct Node*)malloc(sizeof(struct Node));
tail = (struct Node*)malloc(sizeof(struct Node));
head->data = 0;
head->prev = head;
head->next = tail;
tail->data = 0;
tail->prev = head;
tail->next = tail;
int i;
for(i=0; i<5; i++) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = i;
newNode->prev = head;
newNode->next = head->next;
head->next->prev = newNode;
head->next = newNode;
head = head->next;
printf("<- %d -> ", head->data);
}
return 0;
}
해당 코드는 위에 도식화 과정대로 코드를 구현하였는데,
앞서 연결 리스트에서 구현한 코드에서 새롭게 구조체 포인터 prev를 정의하고,
head 노드와 tail 노드의 prev 및 next 링크를 선언해준다.
그리고나서 이중 연결 리스트를 for 문으로 간단하게 구현하였다.
① data는 0부터 4까지 주면서 new 노드의 prev 링크는 head 자체를 가리킨다.
② new 노드의 next 링크는 head 노드의 next 링크를 가리킨다.
③ head 노드의 next 링크의 prev 링크가 new 자체를 가리킨다.
④ head 노드의 next 링크는 new 자체를 가리킨다.
다음과 같은 결과를 가져올 수 있다.
✔️ 이중 연결 리스트 삽입 구현.c (2)
이번에는 다른 방식으로 같은 내용을 출력해보았다.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
int main()
{
struct Node* head = NULL;
struct Node* tail = NULL;
head = (struct Node*)malloc(sizeof(struct Node));
tail = (struct Node*)malloc(sizeof(struct Node));
head->data = 0;
head->prev = head;
head->next = tail;
tail->data = 0;
tail->prev = head;
tail->next = tail;
int i;
for(i=0; i<5; i++) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = i;
tail->prev->next = newNode;
newNode->prev = tail->prev;
tail->prev = newNode;
newNode->next = tail;
head = head->next;
printf("<- %d -> ", head->data);
}
return 0;
}
해당 코드는 다음과 같이 구성되어 있다.
① data는 0부터 4까지 주면서 tail 노드의 prev 링크의 next 링크가 new 자체를 가리킨다.
② new 노드의 prev 링크는 tail 노드의 prev 링크를 가리킨다.
③ tail 노드의 prev 링크는 new 노드 자체를 가리킨다.
④ new 노드의 next 링크는 tail 자체를 가리킨다.
해당 과정을 수행하게 되면, tail 노드의 바로 앞에 추가되는 과정을 통해서
뒤로 새로운 노드가 삽입되는 것을 확인할 수 있다.
✔️ 이중 연결 리스트에 삭제
삭제하려는 노드는 새롭게 변수를 받아서 삭제 연산을 수행하게 되는데,
해당 과정은 삭제할 노드의 이중 연결을 해제하는 방식으로 수행된다.
① 삭제할 노드의 prev 링크의 next 링크가 삭제할 노드의 next 링크를 가리키게 한다.
② 삭제할 노드의 next 링크의 prev 링크가 삭제할 노드의 prev 링크를 가리키게 한다.
✔️ 이중 연결 리스트에 삭제 구현.c
위에서 구현한 이중 연결 리스트는 0의 뒤로 4까지 삽입하는 형태였는데,
이번에는 4까지 삽입된 형태에서 0까지 삭제하는 순서를 나타내는 코드를 구현해보았다.
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
struct Node* prev;
};
int main()
{
struct Node* head = NULL;
struct Node* tail = NULL;
head = (struct Node*)malloc(sizeof(struct Node));
tail = (struct Node*)malloc(sizeof(struct Node));
head->data = 0;
head->prev = head;
head->next = tail;
tail->data = 0;
tail->prev = head;
tail->next = tail;
int i;
for(i=0; i<5; i++) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = i;
newNode->prev = head;
newNode->next = head->next;
head->next->prev = newNode;
head->next = newNode;
}
for(i=0; i<5; i++) {
head = head->next;
printf("<- %d -> ", head->data);
if(head->data == head) break;
head->prev->next = head->next;
head->next->prev = head->prev;
}
return 0;
}
해당 과정은 위에서 설명한 1~2번의 과정을 담고 있는데,
삭제할 노드가 4부터 0까지의 순서로 진행된다.
4가 삭제되고 3이 삭제되고 ··· 와 같은 순서를 거치면 0이 남게 된다.
이중 연결 리스트에 대해 더 정확하게 공부하려면
다른 자료들도 더 찾아보면서 추가적인 공부가 필요할 것 같다.
그리고 틀린 내용이 있다면 해당 내용에 대한 수정도 하면 좋을 듯 하다.
화이팅 💪