단일 연결 리스트와 이중 연결 리스트는
원형 연결 리스트는 연결 리스트에서 Tail이 Head를 가리키는 데이터 구조입니다.
Head와 Tail의 이동이 간단하고, 다시 탐색할 필요가 없습니다.
노드들이 고리처럼 연결되어 있어 무한 루프를 사용해서 반복적으로 순회할 수 있습니다.
따라서 순환과 반복 작업의 무한 스크롤 인터페이스 등에서 사용할 수 있습니다.
이중 연결 리스트의 노드 구체의 수정없이 구현할 수 있습니다.
단일에서 이중 연결 리스트로 구현에서는 이전 노드의 주소를 저장하고 있는 포인터를 추가했지만, 원형 연결 리스트는 단순히 Head의 Prev 포인터가 NULL이 아니라, Tail을 가리키면 됩니다.
물론 Tail의 Next 포인터는 Head를 가리키면 됩니다.
원형 연결 리스트의 연산
자료구조를 사용할 때는 데이터를 추가하거나 삭제, 변경 등을 합니다.
원형 연결 리스트를 만들고, 자료를 사용하기 위해 구현하는 간단한 연산들입니다.
- 노드 생성, 소멸
- 노드 추가
- 노드 탐색
- 노드 삽입
- 노드 삭제
- 노드 위치
- 노드 개수
1. 노드 생성
이중 연결 리스트처럼 노드의 생성 부분은 같습니다.
malloc으로 노드 구조체의 크기만큼 자유 저장소에서 할당 받아서 노드에 메모리 주소를 저장합니다.
생성된 노드에 데이터를 저장해주고 다음 노드에 대한 포인터를 NULL로 초기화 해줍니다.
|
1
2
3
4
5
6
7
8
9
10
|
Node* CDLL_CreateNode(int Data)
{
Node* NewNode = (Node*)malloc(sizeof(Node));
NewNode->Data = Data;
NewNode->PrevNode = NULL;
NewNode->NextNode = NULL;
return NewNode;
}
|
2. 노드의 소멸
이중 연결 리스트처럼 생성된 노드를 해제합니다.
free() 함수로 노드의 주소를 넘겨줘서 소멸시킵니다.
|
1
2
3
4
|
void CDLL_DestroyNode(Node* Node)
{
free(Node);
}
|
3. 노드의 추가
Tail 뒤에 새 노드를 생성합니다.
이중 연결 리스트와 다른 점은 노드가 노드가 하나인 경우(Head만 존재)에 Prev와 Next를 연결해주는 것입니다.
노드가 한 개인 경우에도 순환하는 것처럼 만들어줍니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
void CDLL_AppendNode(Node** Head, Node* NewNode)
{
if ((*Head) == NULL)
{
*Head = NewNode;
(*Head)->NextNode = *Head;
(*Head)->PrevNode = *Head;
}
else
{
Node* Tail = (*Head)->PrevNode;
Tail->NextNode->PrevNode = NewNode;
Tail->NextNode = NewNode;
NewNode->NextNode = (*Head);
NewNode->PrevNode = Tail;
}
}
|
4. 노드 탐색
원형 연결 리스트의 Head부터 원하는 위치까지 순차적으로 탐색합니다.
노드의 수가 동적이므로, while문을 통해 탐색합니다.
|
1
2
3
4
5
6
7
8
9
10
|
Node* CDLL_GetNode(Node* Head, int Location)
{
Node* Current = Head;
while (Current!=NULL && (--Location) >= 0)
{
Current = Current->NextNode;
}
return Current;
}
|
5. 노드 삽입
이중 연결 리스트처럼 노드와 노드 사이에 새로운 노드를 만들어주는 연산입니다.
노드 안의 포인터를 사용해서 새 노드를 추가합니다. 이 때 연결 순서에 맞게 연결해야만 노드를 잃어버리는 미아 상태가 되지 않습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
|
// CDLL 노드 삽입
void CDLL_InsertNode(Node* Current, Node* NewNode)
{
NewNode->NextNode = Current->NextNode;
NewNode->PrevNode - Current;
if (Current->NextNode != NULL)
{
Current->NextNode->PrevNode = NewNode;
Current->NextNode = NewNode;
}
}
|
6. 노드 삭제
노드를 삭제한 다음 이전 노드와 다음 노드를 연결합니다.
다음 노드의 위치를 알 수 있도록 삭제할 노드의 Next를 이전 노드의 Next으로 연결합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
// CDLL 노드 삭제
void CDLL_Remove(Node** Head, Node* Remove)
{
if (*Head == Remove)
{
(*Head)->PrevNode->NextNode = (*Head)->NextNode;
(*Head)->NextNode->PrevNode = (*Head)->PrevNode;
*Head = Remove->NextNode;
Remove->PrevNode = NULL;
Remove->NextNode = NULL;
}
else
{
Node* Temp = Remove;
Remove->PrevNode->NextNode = Temp->NextNode;
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
|
// CDLL 노드 개수
int CDLL_CountNode(Node* Head)
{
unsigned int Count = 0;
Node* Current = Head;
while (Current != NULL)
{
Current = Current->NextNode;
Count++;
}
return Count;
}
|
댓글