Double Linked List

#  더블 링크드 리스트의 구조 

  자료구조의 첫 개시글은 더블 링크드 리스트이다. 그림을 보면 개념을 이해하기 쉽다.

 

 

 

그림1. 간단한 구조의 링크드 리스트

 

 

next 포인터는 다음 노드 자체를 가리키고 있고, prev 포인터는 이전 노드를 가리킨다. 그림1에서는 설명되어 있지 않지만, 리스트 블럭중 가장 첫 번째 블럭은 Head, 가장 마지막 블럭은 Tail이라 불린다. 위 그림1을 예시로 들면 A 노드는 Head, B 노드는 Tail이다. 

 

그림2. Node

 

링크드 리스트의 구조는 prev, next 포인터와 데이터 부분으로 나누어진다. 

typedef int ElementType;
typedef struct tagNode
{
    ElementType Data;
    struct tagNode * PrevNode;
    struct tagNode * NextNode;
} Node;

 

헤더에 선언한 구조체 블럭이다. 

 

노드가 생성되면 데이터블럭을 제외한 두 포인터는 NULL을 가리킨다. Head, Tail에 해당하는 노드들은 각각 prev, next 포인터가 가리킬 대상이 없으므로 NULL을 가리킨다.

 

 

# 링크드 리스트의 함수

  사용자가 정의하기에 따라 다르겠지만 링크드 리스트는 보통 create, append, insert, delete 등과 같은 함수를 갖는다. 여기서 추가적으로 사용 편의에 따라 sort나 concatenate, 또는 인덱싱을 위한 다른 함수들을 선언할 수 있겠다. 본문에서는 위의 기본적인 4개 함수에 대해서 정의하겠다. 

 

Node*   DLL_CreateNode(ElementType NewData);
void    DLL_AppendNode(Node ** Head, Node* NewNode);
void    DLL_RemoveNode(Node ** Head, Node* Remove);
void    DLL_InsertAfter(Node * Current, Node* NewNode);

 

처음부터 차례로 create, append, delete, insert 에 관련된 함수이다. 나중에 추가하겠지만 사용자가 사용하기 편하도록 wrapper function으로 감쌀 생각이다. 

 

 

▶ Create Node Function

 

그림3. Create Node

 

  짐작되겠지만 create의 경우 node를 생성한다. (여기선 아직 구현되지는 않았지만)사용자 관점에서는 노드를 추가하고 넣는 작업이 필요없다. 파이썬 리스트를 생각해보자. 사용자가 굳이 노드를 생성하지 않는다. append 하면 알아서 다음 노드가 생성되고 append 된다. 이 기능이 구현된 코드를 곧 올리겠다. 새로 생성된 노드의 prev, next 포인터는 둘 다 NULL을 가리킨다.

 

 

▶ Append Node Function

 

그림4. Append Node

 

  append 함수의 경우 Tail 노드에 새로 들어온 노드를 붙이는 함수이다. 그림을 보면 알 수 있듯이, 색칠된 화살표의 번호 순서대로 포인터를 가리키게 된다. 주의할 점은 포인터가 서로의 prev, next 포인터 값을 가리키는 것이 아니라 각각의 노드 자체를 가리켜야 한다.

 

 

▶ Insert Node Function

그림5. Insert Node-1

 

  Insert 함수의 경우는 앞 전 함수들과 비교해서 약간 복잡하다. 새로운 노드 D를 생성하고, B와 C 사이에 D 노드를 삽입하겠다. 자세한 과정은 다음과 같다. 그림5는 D 노드를 생성한 모습이다.

1. 새로운 노드 D를 생성한다.
2. 새로운 노드의 필드를 채운다.
3. 이전 노드(prev)와 다음 노드(next)의 포인터를 각각 새로운 노드에 연결한다.

 

그림6. Insert Node-2

 

  노드 D의 필드를 적절하게 연결한 모습이다. prev 포인터는 B에, next 포인터는 C 에 연결한다.

 

 

 

그림7. Insert Node-3

 

  B 노드의 next(C) 의 prev 포인터를 D로, B 노드의 next 포인터를 D에 연결한 모습이다. 이 부분 코드가 약간 난해한데, 아래에 코드를 첨부하겠다.

 

1번 과정을 코드로 작성하면 다음과 같다. 여기서 Current는 B를 의미하고, NewNode는 D를 의미한다.

Current->NextNode->PrevNode = NewNode;

 

이어서 2번 과정을 코드로 작성하면 다음과 같다.

Current->NextNode = NewNode;

 

2번의 경우는 간단하게 구현할 수 있다.

 

append 함수와 insert 함수의 차이점은 사용자가 새로운 노드의 위치를 정할 수 있는지 여부이다. 위치를 정할 수 있다면 insert, Tail에 노드를 붙인다면 append이다. 경험상 append가 insert 보다 훨씬 많이 쓰이는 것 같다. 마찬가지로 사용자 입장에서 insert 함수를 사용하기 위해서 이전 노드의 주소를 알아야 하는 불편함이 있으므로 나중에 wrapper 함수를 만들어서 사용에 용이하게 하겠다.

 

Insert, append 의 경우 주의해야 할 점이 있다. append 함수의 경우 노드가 없을 경우 처음 들어오는 노드를 Head 노드로 설정해주어야 한다. Insert 함수의 경우는 리스트가 없을 때 현재 노드의 포인터를 모르기 때문에 처음의 경우는 사용할 수 없다. 

 

 

▶ Delete Node Function

 

delete(remove) 함수는 insert 함수의 역순으로 진행된다. 

1. 삭제 노드의 이전 노드의 포인터들과 이후 노드의 포인터들을 다시 연결한다.
2. 삭제 노드의 prev, next 노드 포인터를 NULL로 설정한다.
3. 할당된 메모리를 해제한다.

 

그림8. Delete Node-1

 

  1번 과정을 그림으로 나타냈다. insert 와 마찬가지로 삭제 노드 이전과 이후 노드들의 포인터들을 다시 적절하게 배치한 모습이다. 이 부분도 Insert 처럼 포인터의 포인터를 참조하는데, 때문에 코드가 조금 난해하다.

 

 

그림9. Delete Node-2

 

2번 과정이다. 삭제할 노드의 포인터 필드를 NULL로 한다. 이후 메모리를 해제한다.

 

 

※ 메모리를 해제하는 이유?

  비록 노드의 포인터들을 모두 NULL로 할당하더라도 malloc으로 할당받은 메모리를 해제해주어야 한다. 왜냐하면 함수를 동적으로 할당받을때 사용하는 malloc 함수는 free-list로 부터 빈 공간을 찾아서 할당하기 때문이다. 사실 메모리 할당은 실제 메모리 위치 주소를 사용하는 것이 아니라 가상 메모리 주소를 사용한다. 이러한 가상 메모리 주소를 사용하는 이유는 실제 메모리에 비해 큰 공간이 필요한 프로세스를 실행하는 등 추상화를 통해 여러 이점을 얻을 수 있기 때문이다. 

 

malloc은 사용자가 요청한 크기 만큼 가상 메모리를 요청하고, 이를 free-list의 남는 공간에서 뜯어온다. 이후에 메모리를 해제하면 free-list는 할당 받는 메모리 주소와 크기 만큼을 링크드 리스트 형태로 관리하게 된다. 이런 방식으로 메모리를 관리하게 되는데 OS에 따라 일정 간격으로 free-list를 합쳐주어 관리하기에 용이하게 해주는 경우도 있다. 이 경우, free-list에 메모리가 끊김없이 연속적으로 존재해야 한다. 

 

메모리 할당과 해제를 적절하게 해주지 않는다면 메모리 누수나 dangling pointer 등이 발생할 수 있다. 특히 링크드 리스트의 경우 이 문제가 많이 발생할 수 있는데, 순차적으로 데이터가 저장되는 배열과 대조해서 링크드 리스트의 경우 메모리 안에서 다음 노드의 위치는 빈 공간 어디든지 가능하기 때문이다. 최악의 경우 메모리 Fragmentation 현상이 일어날 수 있다. 그러나 임베디드 시스템과 같은 규모가 작은 환경에서는 오히려 메모리를 해제하는 것이 관리를 어렵게 하기 때문에 메모리 해제를 하지 않는 것을 권장하고 있다. 위 부분들은 나중에 OS 부분에서 자세하게 설명하겠다.

 

# Double Linked List의 장단점

  더블 링크드 리스트는 장점이 많은 데이터 구조이다. 때문에 OS 뿐만 아니라 여러 애플리케이션에서 사용된다. 크기가 정해져 있는 배열에 비해서 사용자가 원하는 만큼 데이터를 추가하거나 삭제할 수 있다. 또한 포인터로 엮이듯 이루어진 구조 때문에, 데이터의 추가나 삭제가 간편하다. 배열을 생각해보자. 데이터 삭제 또는 삽입한다면 그에 따른 공간을 어떻게 처리할 것인가? 데이터들을 순차적으로 옮겨야 한다.

 

리스트의 경우, 오직 포인터를 다시 재구성하면 얼마든지 원하는 만큼 원하는 곳에 데이터를 넣거나 뺄 수 있다. 사용자의 메모리가 허락하는 한, 무한정 데이터를 추가할 수 도 있다. 

 

그러나 더블 링크드 리스트는 단점도 많다. 사용자가 원하는 위치에 도달하고 싶다면 그 위치를 찾을 때까지 직접 순차적으로 접근해야 한다. 왜냐하면 데이터가 메모리 상에서 순차적이지 않고 흩뿌려져 있기 때문에, 주소를 직접 계산할 수 없기 때문이다.

 

# 코드