이번 글에서는 링크드 리스트 중 더블 링크드 리스트에 대해서 알아보고, 실제로 C언어 코드로 구현까지 해보도록 하겠습니다. 일반적으로 동적할당을 이용한 구현 코드가 널리 알려져 있지만, 저는 메모리 풀 방식을 활용한 코드를 작성하도록 하겠습니다(왜냐하면 알고리즘 문제 풀이시에는 메모리 풀 방식이 훨씬 시간이 적게 걸리기 때문입니다.) 자세한 내용은 밑에서 설명드리도록 하겠습니다.
링크드 리스트의 경우 직접 구현시에 포인터와 구조체를 사용합니다. "포인터, 구조체, 구조체 포인터"가 무엇인지 잘 모르시는 분들을 해당 내용을 먼저 공부하시고 다시 이 글을 보시면 훨씬 좋을 것 같습니다!
(1) 링크드 리스트란?
링크드 리스트는 위 그림처럼 여러 노드들을 연결한 자료구조입니다. 저장하는 데이터 하나의 단위를 일반적으로 노드라고 부릅니다. 노드에는 실제로 저장한 값들과 다른 노드를 가리키는 포인터가 저장되어 있습니다. 이번 글에서 알아볼 더블 링크드 리스트의 경우 위 그림처럼 노드에는 다음 노드를 가리키는 포인터가 저장되어 있습니다. 또한 이전 노드를 가리키는 포인터도 저장 되어 있습니다. 그래서 링크드 리스트는 가장 첫 노드(head)부터 가장 끝 노드(tail)까지 포인터를 이용해서 순차적으로 노드에 접근하는 자료구조입니다.
(2) 더블 링크드 리스트
더블 링크드 리스트는 노드에 포인터가 2개 존재하는 링크드리스트입니다. 노드의 한 포인터는 다음 노드를 가리킵니다. 또 다른 포인터는 이전 노드를 가리킵니다. 더블 링크드 리스트의 특정 노드 찾기, 노드 삽입, 노드 삭제, 노드 수정을 어떻게 수행하는지를 그림과 함께 설명드리겠습니다.
1) 특정 노드 찾기
특정 노드 찾는것의 경우 헤드부터 시작해서 순차적으로 각각 노드의 데이터 값을 확인해볼 것입니다. 그 과정에서 찾는 노드를 발견하면 멈추면 됩니다.
2) 특정 위치에 노드 삽입하기
노드 삽입의 경우 삽입할 위치의 왼쪽 노드와 새 노드를 연결시켜주고, 오른쪽 노드와 새 노드를 연결시켜주면 삽입이 완료됩니다.
3) 노드 삭제하기
노드 삭제의 경우 먼저 삭제할 노드와 그 노드의 왼쪽 노드의 연결을 끊어주고, 삭제할 노드와 그 오른쪽 노드의 연결을 끊어줍니다(사실 이부분은 실제 구현시에는 생략해도 되는 부분입니다) 그 다음에 삭제할 노드의 왼쪽 노드와, 삭제할 노드의 오른쪽 노드를 서로 연결해주면 됩니다.
4) 특정 노드 수정하기
특정 노드에 접근한뒤 그 노드의 값을 수정해주면 됩니다.
(3) 링크드 리스트의 시간복잡도
링크드 리스트에서 수행하는 작업은 "특정 노드 찾기, 노드 삽입, 노드 삭제, 노드 수정" 입니다. 배열의 경우와 비교하면서 설명드리겠습니다.
- 배열의 특정 인덱스 접근하기 : O(1), arr[index] 처럼 바로 특정 인덱스에 접근 할 수 있습니다
- 배열에서 특정 인덱스에 삽입하기 : O(N), 이번에 삽입하는 인덱스의 다음 데이터들을 한칸씩 오른쪽으로 이동시켜줘야하기 때문에 최악의 경우 N번 오른쪽으로 데이터들을 이동시켜야 합니다.
- 배열에서 특정 인덱스의 원소 삭제하기 : O(N), 삭제하는 인덱스 다음 데이터들을 한칸씩 왼쪽으로 이동시켜줘야 하기 때문에 최악의 경우 N번 왼쪽으로 데이터들을 이동시켜야 합니다.
- 배열에서 특정 인덱스 원소 수정하기 : O(1), 특정 인덱스에 바로 접근해서 값만 변경해주면 됩니다.
링크드 리스트의 경우 배열과 매우 다릅니다.
링크드 리스트는 배열처럼 바로 특정 인덱스에 접근 할 수 없습니다. 일반적으로 가장 첫 노드부터 순차적으로 노드를 순회하면서 원하는 노드를 찾아야 합니다(사실 특정 노드에 바로 접근 할 수 있는 방법이 있긴 한데 다음 글에서 설명드리겠습니다.)
- 링크드 리스트의 특정 노드 찾기 : O(N), 첫 노드부터 순차적으로 순회하면서 원하는 노드인지를 확인해야합니다.
- 링크드 리스트의 특정 위치에 노드 삽입하기 : O(1), 삽입할 위치를 알고 있다면 노드 삽입시에는 이전노드와 새 노드를 연결해주고 새 노드와 다음 노드를 연결해주면 됩니다(포인터만 저장해주면 됩니다)
- 링크드 리스트의 특정 노드 삭제하기 : O(1), 삭제할 노드의 위치를 알고 있다면 그 노드의 이전노드와 다음노드를 연결해주면 됩니다.
링크드 리스트와 배열의 시간복잡도를 보면 특정 원소 접근시 O(1)만에 가능한 배열이 더 유용할 것 같다고 생각하실 수도 있습니다. 하지만 삽입 삭제가 빈번하거나, 특정 위치가 계속 유지되는 형태의 문제들도 꽤 많습니다. 이런 경우에는 링크드 리스트를 적용시키는 것이 더 효율적입니다. 그래서 결론은 문제의 시간복잡도를 잘 분석해서 더 효율적인 자료구조를 선택하는 것이 정말 중요하다는 것입니다!!
(4) 메모리 풀(Memory Pool) 방식
링크드 리스트를 구현시에 노드를 생성해줘야 합니다. 보통 여러 책에는 malloc을 이용해서 동적할당을 통해 노드들을 필요할 때마다 생성하는 방식을 소개하고 있습니다. 하지만, 알고리즘 문제 풀이에서 링크드 리스트를 활용할 경우에 malloc을 사용해서 노드를 필요할 때마다 사용하면 시간이 너무 오래 걸립니다. 그래서 알고리즘 문제 풀이시에는 노드를 미리 배열로 많이 생성해두고 필요할 때 배열에 접근해서 미리 만들어 놓은 노드를 하나씩 사용합니다. 이처럼 사용할 객체들을 미리 만들어 놓고 필요할 때 그 객체들을 활용하는 방식을 메모리 풀(Memory Pool) 방식이라고 합니다. 아래 코드는 링크드 리스트에서 사용할 노드를 구조체로 정의한 코드입니다. 메모리 풀을 어떻게 구현해서 사용하는지를 눈여겨 봐주시면 좋을 것 같습니다.
const int MAXNODE = 100000;
struct Node {
int data = -1;
Node* prev;
Node* next;
Node* myAlloc(int _data, Node* _prev, Node* _next) {
data = _data; prev = _prev; next = _next;
_next->prev = this; //현재 node를 다음 node의 이전 node로 연결
return this;
}
}pool[MAXNODE]; //10만개의 노드 미리 만들어 놓고 필요할 때마다 pool 배열에서 가져와서 쓰기 pool[poolCnt]
int poolCnt = 0;node가 필요할 경우 pool 객체에서 하나씩 꺼내서 사용합니다.
(5) 구현 코드
더블 링크드 리스트의 삽입,삭제,검색을 구현해보겠습니다. 먼저 위에서도 확인하셨던 노드 구조체입니다. 그리고 제 코드는 head와 tail이 존재합니다. head와 tail을 사용하는 이유는 노드 삽입 삭제 및 검색을 더 간단히 할 수 있고, null포인터에 접근하는 경우가 없도록 만들어 주기 때문입니다. nodeInit함수에서 poolCnt를 초기화해주고 head와 tail을 서로 연결해주었습니다.
#include<stdio.h> //더블 링크드 리스트
const int MAXNODE = 100000;
struct Node {
int data = -1;
Node* prev;
Node* next;
Node* myAlloc(int _data, Node* _prev, Node* _next) {
data = _data; prev = _prev; next = _next;
_next->prev = this; //현재 node를 다음 node의 이전 node로 연결
return this;
}
}pool[MAXNODE]; //10만개의 노드 미리 만들어 놓고 필요할 때마다 pool 배열에서 가져와서 쓰기 pool[poolCnt]
int poolCnt = 0;
Node head, tail;
void nodeInit() {
poolCnt = 0;
head.next = &tail;
tail.prev = &head;
}
다음으로 특정 노드를 검색하는 함수 입니다. 노드의 id값을 기준으로 찾는 코드입니다. 주의할 점은 리턴하는 노드의 주소는 실제로 찾는 노드 이전 노드입니다(실제로 찾는 노드는 ptr->next가 가리키는 노드 입니다.) 이전 노드의 주소를 활용해서 삽입 삭제를 하는 것이 코드가 훨씬 깔끔합니다. 그리고 head와 tail을 사용하기 때문에 이전 노드가 null포인터가 될 위험도 전혀 없습니다(tail의 data는 -1이라서 아래 루프에서 ptr->next가 tail이면 탈출하게 됩니다)
Node* getNode(int _data) {
Node* ptr = &head;
while (ptr->next && ptr->next->data != -1) {
if (ptr->next->data == _data)break;
ptr = ptr->next;
}
return ptr;
}
다음으로 특정 위치에 새 노드를 삽입하는 함수 입니다. ptr노드 다음 위치에 새 노드를 삽입하는 코드입니다. 노드 pool에서 노드 1개를 가져와서 데이터를 할당해줍니다.
void nodeInsert(int data, Node* ptr) {
//ptr->next에 새 노드 삽입할 것임.
ptr->next = pool[poolCnt++].myAlloc(data, ptr, ptr->next);
}
다음으로 특정 노드를 삭제하는 함수 입니다. ptr노드 다음 노드를 삭제하는 코드입니다.
void nodeRemove(Node* ptr) {
//ptr->next에 해당하는 노드를 삭제할 것임
Node* temp = ptr->next;
ptr->next = temp->next;
temp->next->prev = ptr;
}
전체 소스코드입니다. main함수에서 삽입,삭제,검색 함수를 사용하는 내용도 작성하였습니다.
#include<stdio.h> //더블 링크드 리스트
const int MAXNODE = 100000;
struct Node {
int data = -1;
Node* prev;
Node* next;
Node* myAlloc(int _data, Node* _prev, Node* _next) {
data = _data; prev = _prev; next = _next;
_next->prev = this; //현재 node를 다음 node의 이전 node로 연결
return this;
}
}pool[MAXNODE]; //10만개의 노드 미리 만들어 놓고 필요할 때마다 pool 배열에서 가져와서 쓰기 pool[poolCnt]
int poolCnt = 0;
Node head, tail;
void nodeInit() {
poolCnt = 0;
head.next = &tail;
tail.prev = &head;
}
Node* getNode(int _data) {
Node* ptr = &head;
while (ptr->next && ptr->next->data != -1) {
if (ptr->next->data == _data)break;
ptr = ptr->next;
}
return ptr;
}
void nodeInsert(int data, Node* ptr) {
//ptr->next에 새 노드 삽입할 것임.
ptr->next = pool[poolCnt++].myAlloc(data, ptr, ptr->next);
}
void nodeRemove(Node* ptr) {
//ptr->next에 해당하는 노드를 삭제할 것임
Node* temp = ptr->next;
ptr->next = temp->next;
temp->next->prev = ptr;
}
void printAllNode() { //순서대로 출력하기
Node* ptr = &head;
while (ptr->next && ptr->next->data != -1) {
printf("%d ", ptr->next->data);
ptr = ptr->next;
}
printf("\n");
}
int main(void)
{
nodeInit();
Node* ptr = &head;
for (int i = 1; i <= 5; i++)
{
nodeInsert(i, ptr);
ptr = ptr->next;
}
printAllNode(); //순서대로 출력하기 1 2 3 4 5
//data=3인 노드 이전에 data=99인 노드 삽입하기
ptr = getNode(3);
nodeInsert(99, ptr);
printAllNode(); //순서대로 출력하기 1 2 99 3 4 5
//data=4인 노드 삭제하기
ptr = getNode(4);
nodeRemove(ptr);
printAllNode(); //순서대로 출력하기 1 2 99 3 5
return 0;
}
다음 글에서는 링크드 리스트의 성능을 조금 더 개선해보도록 하겠습니다. 링크드 리스트의 단점은 특정 노드를 찾기 위해서 첫 노드부터 순차적으로 순회하면서 찾아야 한다는 점이었습니다. 하지만 노드 고유의 id값이 존재한다면 unorderedmap이나 배열을 활용해서 원하는 노드에 바로 접근할 수 있어서 성능을 많이 개선할 수 있습니다. 자세한 설명은 다음 글에서 드리겠습니다.
'자료구조' 카테고리의 다른 글
| 스택(Stack) 자료구조란? (C언어, Java, Python 예시코드 포함) (0) | 2024.12.18 |
|---|---|
| 큐(Queue) 자료구조란? (C언어, Java, Python 예시코드) (0) | 2024.12.18 |
| 링크드 리스트(2) - 성능 개선 (0) | 2023.04.21 |
| HEAP (2) - 업그레이드 된 HEAP 힙 (특정원소 삭제, 업데이트 O(logN)만에 가능) (0) | 2023.03.12 |
| HEAP(1) - 힙 기본 구현 (C언어 구현, index 1부터 시작) (0) | 2023.03.12 |
댓글