단일 연결 리스트는 다음 노드를 가리키는 포인터가 1개입니다.
특정 노드를 찾기 위해서 Head부터 Tail까지 순차적으로 탐색해야 한다는 단점이 있습니다.
따라서 현재 노드에서 이전 노드로 돌아갈 수 없고 다시 Head부터 탐색이 필요합니다.
이중 연결 리스트는 노드를 가리키는 포인터를 1개 추가하여 탐색을 보안하였습니다.
다음 노드를 가리키는 포인터뿐만 아니라 이전 노드를 가리키는 포인터를 추가하는 방법입니다.
|
1
2
3
4
5
6
|
typedef struct tagNode
{
int Data;
struct tagNode* PrevNode;
struct tagNode* NextNode;
} Node;
|
▲ 이전 노드를 가리키는 포인터 변수를 추가해줍니다.
이중 연결 리스트의 연산
자료구조를 사용할 때는 데이터를 추가하거나 삭제, 변경 등을 합니다.
이중 연결 리스트를 만들고 포함된 자료를 사용하기 위해 사용하는 연산입니다.
- 노드 생성, 소멸
- 노드 추가
- 노드 탐색
- 노드 삽입
- 노드 삭제
1. 노드의 생성
단일 연결 리스트처럼 노드의 생성 부분은 같습니다.
malloc으로 노드 구조체의 크기만큼 자유 저장소에서 할당받아서 노드에 메모리 주소를 저장합니다.
생성된 노드에 데이터를 저장해주고 다음 노드에 대한 포인터를 NULL로 초기화 해줍니다.
단, 이전 노드에 대한 포인터가 추가됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
|
// DLL 노드 생성
Node* DLL_CreateNode(int NewData)
{
Node* NewNode = (Node*)malloc(sizeof(Node));
NewNode->Data = NewData;
NewNode->PrevNode = NULL;
NewNode->NextNode = NULL;
return NewNode;
}
|
2. 노드 소멸
단일 연결 리스트처럼 생성된 노드를 해제합니다.
free() 함수로 노드의 주소를 넘겨줘서 소멸시킵니다.
|
1
2
3
4
5
|
// DLL 노드 소멸
void DLL_DestroyNode(Node* Node)
{
free(Node);
}
|
3. 노드 추가
Tail 뒤에 새 노드를 생성해줍니다.
Tail 노드에 다음 포인터를 새 노드에 연결해주고, 새 노드의 이전 포인터를 Tail로 연결해줍니다.
노드 하나도 없을 경우 새 노드를 추가해주고 해당 노드는 헤드가 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
// DLL 노드 추가
void DLL_AppendNode(Node** Head, Node* NewNode)
{
if ((*Head) == NULL)
{
*Head = NewNode;
}
else
{
Node* Tail = (*Head);
while (Tail->NextNode != NULL)
{
Tail = Tail->NextNode;
}
Tail->NextNode = NewNode;
NewNode->PrevNode = Tail;
}
}
|
4. 노드 탐색
이중 연결 리스트의 Head 부터 원하는 위치까지 순차적으로 탐색합니다.
노드의 수가 동적이므로 while문을 통해 탐색합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
|
// DLL 노드 탐색
Node* DLL_GetNode(Node* Head, int Location)
{
Node* Current = Head;
while (Current != NULL && (--Location) >= 0)
{
Current = Current->NextNode;
}
return Current;
}
|
5. 노드 삽입
노드와 노드 사이에 새로운 노드를 만들어주는 연산입니다.
노드 안의 포인터를 사용해서 새 노드를 추가해줍니다.
이 때 연결 순서를 맞게 해줘야 노드를 잃어버리는 미아 상태가 되지 않습니다.
먼저, 새 노드의 다음은 현재 노드의 다음 노드의 주소를 연결하고, 새 노드의 이전은 현재 노드의 주소를 가리킵니다. (1, 2번)
다음노드의 이전 포인터는 새 노드, 현재 노드의 다음 포인터는 새 노드를 가리킵니다.(3, 4번)
6. 노드 삭제
노드의 삭제 연산은 4개의 포인터를 다룹니다.
삭제를 진행과 함께 노드들이 연결될 수 있도록 해줍니다.
삭제할 노드의 다음 노드를 이전 노드의 다음 포인터로 연결하고 다음 노드의 이전 포인터는 이전 노드를 가리킵니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
// DLL 노드 제거
void DLL_RemoveNode(Node** Head, Node* Remove)
{
if (*Head == Remove)
{
*Head = Remove->NextNode;
if ((*Head) != NULL)
(*Head)->PrevNode = NULL;
Remove->PrevNode = NULL;
Remove->NextNode = NULL;
}
else
{
Node* Temp = Remove;
if (Remove->PrevNode != NULL)
Remove->PrevNode->NextNode = Temp->NextNode;
if (Remove->NextNode != NULL)
Remove->NextNode->PrevNode = Temp->PrevNode;
Remove->PrevNode = NULL;
Remove->NextNode = NULL;
}
}
|
7. 노드 개수
이중 연결 리스트의 총 노드 수를 구하는 함수입니다.
알고리즘 문제를 푸는 것처럼 Count 변수를 하나 만들고 while문을 통해서 개수를 세주면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
// DLL 노드 개수
int DLL_GetNodeCount(Node* Head)
{
unsigned int Count = 0;
Node* Current = Head;
while (Current != NULL)
{
Current = Current->NextNode;
Count++;
}
return Count;
}
|
댓글