그 중 환형리스트에 대해 조금 더 살펴보려 한다.
효율성을 생각한다면 낙제생인 샘이다.
이렇게 하면 노드들의 탐색간에 시간적인 비용을 상당히 줄일 수 있다.
아래 코드를 찬찬히 보면 적당히 환형 리스트가 어떤식으로 만들어지는지 알 수 있을것이다.
(아래 코드는 뇌를자극하는 알고리즘의 코드이다. 클래스화 하면 좋겠지만 크게 차이는 없으니..)
접기
//#ifndef CIRCULAR_LINKED_LIST_H
//#define CIRCULAR_LINKED_LIST_H
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef int ElementType;
typedef struct tagNode
{
ElementType Data;
struct tagNode* PrevNode;
struct tagNode* NextNode;
} Node;
Node* CDLL_CreateNode(ElementType NewData);
void CDLL_DestroyNode(Node* Node);
void CDLL_AppendNode(Node** Head, Node* NewNode);
void CDLL_InsertAfter(Node* Current, Node* NewNode);
void CDLL_RemoveNode(Node** Head, Node* Remove);
Node* CDLL_GetNodeAt(Node* Head, int Location);
int CDLL_GetNodeCount(Node* Head);
//#endif
//#include"Circular_linked_list.h"
Node* CDLL_CreateNode(ElementType NewData)
{
Node* NewNode = (Node*)malloc(sizeof(Node));
NewNode->Data = NewData;
NewNode->PrevNode = NULL;
NewNode->NextNode = NULL;
return NewNode;
}
void CDLL_DestroyNode(Node* Node)
{
free(Node);
}
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;
}
}
void CDLL_InsertAfter(Node* Current, Node *NewNode)
{
NewNode->NextNode = Current->NextNode;
NewNode->PrevNode = Current;
Current->NextNode->PrevNode = NewNode;
Current->NextNode = NewNode;
}
void CDLL_RemoveNode(Node** Head, Node* Remove)
{
if( *Head == Remove)
{
(*Head)->PrevNode->NextNode = Remove->NextNode;
(*Head)->NextNode->PrevNode = Remove->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;
}
CDLL_DestroyNode(Remove);
}
Node* CDLL_GetNodeAt(Node* Head, int Location)
{
Node* Current = Head;
while(Current != NULL && (--Location) >= 0)
{
Current = Current->NextNode;
}
return Current;
}
int CDLL_GetNodeCount(Node* Head)
{
unsigned int Count = 0;
Node* Current = Head;
while(Current != NULL)
{
Current = Current->NextNode;
Count++;
if( Current == Head)
break;
}
return Count;
}
void PrintNode(Node* _Node)
{
if( _Node->PrevNode == NULL)
cout<<"Prev: NULL"<<endl;
else
cout<<"Prev:"<<_Node->PrevNode->Data<<endl;
cout<<"Current: "<<_Node->Data<<endl;
if(_Node->NextNode == NULL)
cout<<"Next: NULL"<<endl;
else
cout<<"Next: "<<_Node->NextNode->Data<<endl;
}
접기 접기
int main()
{
int Count = 0;
Node *List = NULL;
Node *NewNode = NULL;
Node *Current = NULL;
for(int i=0; i<5; i++)
{
NewNode = CDLL_CreateNode(i*10);
CDLL_AppendNode(&List, NewNode);
}
//print//
Count = CDLL_GetNodeCount(List);
for(int i=0; i<Count; i++)
{
Current = CDLL_GetNodeAt(List, i);
cout<<"List["<<i<<"]: "<<Current->Data<<endl;
}
//세번째 칸 뒤에 노드삽입//
cout<<"\nInserting 3000 After [2]...\n\n";
Current = CDLL_GetNodeAt(List, 2);
NewNode = CDLL_CreateNode(3000);
CDLL_InsertAfter(Current, NewNode);
//출력
//환형리스트이기 때문에 리스트 크기를 넘어서면서도 출력이 가능
Count = CDLL_GetNodeCount(List);
for(int i=0; i<Count*2; i++)
{
if(i == 0)
Current = List;
else
Current = Current->NextNode;
cout<<"List["<<i<<"] : "<<Current->Data<<endl;
}
//delete all node
cout<<"Destroying list..."<<endl;
Count = CDLL_GetNodeCount(List);
for(int i=0; i<Count; i++)
{
Current = CDLL_GetNodeAt(List, 0);
if(Current != NULL)
{
CDLL_RemoveNode(&List, Current);
}
}
return 0;
}
접기
ㅇㅅㅇ.. 그림으로 설명 대체
..
