싱글 링크드리스트 ( Single Linked List )
- 배열과는 다르게 크기를 유연하게 바꿀 수 있는 자료구조 입니다.
- 노드 (Node) 들의 연결된 리스트로 구성이 되며 노드는 데이터와 다음 노드를 가르키는 포인터로 구성됩니다.
* 위 그림은 이해하기 쉽게 그림으로 그린 개념적 구조입니다.
* 노드엔 데이터가 담길 공간과 , 다음 노드를 가르키기 위한 정보를 담을 공간 두개로 이루어져 있습니다.
* 그림으로 나타내면 위와 같은 구조가 됩니다.
* 가장 첫번째 노드를 HEAD 노드라 하고, 가장 마지막 노드를 TAIL 노드라고 합니다.
* 데이터를 넣으면 이런 형태로 볼 수 있습니다.
* 코드로 표현하면 다음과 같이 나타낼 수 있습니다.
typedef struct NODESL
{
int data;
NodeSL* nextNode;
}NodeSL;
* int 형 데이터를 넣을 수 있는 변수와 다음 노드를 가르킬 수 있는 Node 포인터 변수 두개로 이루어져 있습니다.
싱글 링크드리스트의 연산
필요한 기능이 어떤 것들이 있는지 쭉 나열해보면 다음과 같은 것들이 있다고 할 수 있습니다.
1. Node 생성
2. Node Insert
3. Tail 가져오기
4. 특정 인덱스 가져오기
5. Node 모두 출력
6. 특정 인덱스 삭제
7. 모든 Node 삭제
1. Node 생성
NodeSL* SL_CreateNode(int newData)
{
NodeSL* node = new NodeSL();
node->data = newData;
return node;
}
* 새로운 노드를 생성합니다.
이 노드를 리턴 받아 연결해주어야 합니다.
2. Node Insert
1) Node Append
void SL_AppendNode(NodeSL** headNode, NodeSL* newNode)
{
// head가 null 일 경우 newNode가 head Node 가 된다
if (*headNode == nullptr)
{
*headNode = newNode;
}
else
{
NodeSL* tailNode = SL_GetTailNode(*headNode);
tailNode->nextNode = newNode;
}
}
* head로 쓸 node 가 null 일 경우 newNode 가 head 노드가 됩니다.
* 이미 head 가 있을 경우엔 tail node를 찾은 뒤에 그 뒤에 붙입니다
2) Node Insert Before
.
- 만약 2번 노드 앞에 새로운 노드를 삽입하려 한다면 head에서부터 순차적으로 찾아 2번 노드의 바로 전 노드인 1번 노드를 구한 뒤에 , 1번 노드의 다음 노드(2번 노드)를 새로운 노드의 다음 노드로 연결하고, 1번 노드의 다음노드를 새로운 노드로 만들어 줍니다.
void SL_InsertBefore(NodeSL* head,NodeSL* current, NodeSL* newNode)
{
if (current == nullptr)
{
printf("Select Node is NULL\n");
return;
}
if (head == current)
{
SL_InsertAfter(head, newNode);
return;
}
NodeSL* cur = head;
while (cur->nextNode != current)
{
cur = cur->nextNode;
}
cur->nextNode = newNode;
newNode->nextNode = current;
}
3) Node Insert After
- 만약 1번 노드 다음에 새로운 노드를 삽입하려 한다면 1번 노드를 구한 뒤에 1번 노드의 다음노드(2번노드)를 새로운 노드의 다음노드로 만들어주고 1번 노드의 다음 노드를 새로운 노드로 만들어줍니다.
void SL_InsertAfter(NodeSL* current, NodeSL* newNode)
{
if (current == nullptr)
{
printf("Select Node is NULL\n");
return;
}
NodeSL* curNext = current->nextNode;
current->nextNode = newNode;
newNode->nextNode = curNext;
}
3. Tail 가져오기
NodeSL* SL_GetTailNode(NodeSL* head)
{
NodeSL* curNode = head;
while (curNode->nextNode != nullptr)
curNode = curNode->nextNode;
return curNode;
}
* 단순히 끝의 노드에 도달할때까지 반복해서 이동한 후에 ( curNode = curNode->nextNode; ) 그것을 리턴해주면 됩니다.4. 특정 인덱스 가져오기
NodeSL* SL_GetNodeAt(NodeSL* head, int index)
{
NodeSL* curNode = head;
int cnt = 0;
if (index == 0)
return curNode;
while (cnt != index && curNode != nullptr)
{
cnt++;
curNode = curNode->nextNode;
}
return curNode;
}
* 배열과는 다르게 인덱스의 랜덤 엑세스가 불가능하고, 순차적으로 찾아야 하기 때문에 비효율적이라는 단점이 있습니다.
5. 노드 모두 출력
void SL_AllPrint(NodeSL* head)
{
NodeSL* curNode = head;
int index = 0;
printf("SL_AllPrint -------------------\n");
while (curNode != nullptr)
{
index++;
printf(" [ %d ] --> ", curNode->data);
if (index % 5 == 0)
printf("\n");
curNode = curNode->nextNode;
}
}
* 순차적으로 노드를 탐색하면서 값을 출력합니다.
6. 특정 인덱스 삭제
void SL_RemoveAt(NodeSL** head,int index)
{
// index 가 0일 경우 head 를 지워야 한다.
if (index == 0)
{
NodeSL* temp = *head;
*head = ((*head)->nextNode);
delete temp;
return;
}
NodeSL* curNode = *head;
NodeSL* prevNode;
int cnt = 0;
while (curNode->nextNode != nullptr)
{
cnt++;
prevNode = curNode;
curNode = curNode->nextNode;
if (cnt == index)
{
prevNode->nextNode = curNode->nextNode;
delete curNode;
return;
}
}
}
void SL_RemoveAll(NodeSL** head)
{
NodeSL* curNode = *head;
NodeSL* tempNode = nullptr;
while (curNode != nullptr)
{
tempNode = curNode;
curNode = curNode->nextNode;
delete tempNode;
}
*head = nullptr;
}
* 순차적으로 노드를 삭제하면 됩니다.( 다음 노드를 가져오고 현재 노드는 삭제하고 )
더블 링크드리스트 (Double Linked List)
- 다음 노드와 이전 노드를 가르키는 포인터가 있다는 점 외에는 싱글 링크드리스트와 비슷합니다.
* 코드로 표현하면 다음과 같이 나타낼 수 있습니다.
typedef struct NODEDL
{
int data;
NODEDL* nextNode;
NODEDL* prevNode;
}NodeDL;
더블 링크드리스트의 연산
- 싱글 링크드리스트와 비슷하지만 이전 노드를 가르킨다는 점에서 차이점이 있습니다. ( 노드 한개를 알면 이전 노드와 다음 노드에 접근이 가능합니다. )
1. Node 생성
2. Node Insert
3. Tail 가져오기
4. 특정 인덱스 가져오기
5. Node 모두 출력
6. 특정 인덱스 삭제
7. 모든 Node 삭제
1. Node 생성
NodeDL* DL_CreateNode(int newData)
{
NodeDL* newNode = new NodeDL();
newNode->data = newData;
newNode->prevNode = nullptr;
newNode->nextNode = nullptr;
return newNode;
}
* 새로운 노드를 생성하고 리턴합니다. 이 노드를 이용해 연산을 해야 합니다.
2. Node Insert
1) Node Append
* 싱글과는 다르게 '이전'노드가 있으므로 Tail의 다음 노드를 새로운 노드로 지정한 뒤에 , 새로운 노드의 이전노드를 Tail 로 지정해줍니다.
void DL_AppendNode(NodeDL** headNode, NodeDL* newNode)
{
if (*headNode == nullptr)
{
*headNode = newNode;
}
else
{
NodeDL* tail = DL_GetTailNode(*headNode);
tail->nextNode = newNode;
newNode->prevNode = tail;
}
}
2) Node Insert Before
*만약 3번 노드 전 위치에 삽입을 하고자 한다면 '3번 노드'만 갖고 있으면 가능 합니다.
3번 노드의 이전 노드(2번노드)의 다음 노드를 새로운 노드로, 새로운 노드의 다음 노드를 3번 노드로 지정해주고,
새로운 노드의 이전 노드를 3번 노드의 이전노드(2번노드)로 지정하고, 3번 노드의 이전 노드를 새로운 노드로 지정합니다.
void DL_InsertBefore(NodeDL* current, NodeDL* newNode)
{
if (current == nullptr)
{
printf("Select Node is NULL\n");
return;
}
// curPrev <-> newNode <-> current
NodeDL* curPrev = current->prevNode;
current->prevNode = newNode; // newNode <- current
newNode->nextNode = current; // newNode -> current
newNode->prevNode = curPrev; // curPrev <- newNode
curPrev->nextNode = newNode; // curPrev -> newNode
}
3) Node Insert After
* 만약 2번 노드 다음에 새로운 노드를 추가한다고 한다면 2번 노드의 다음 노드(3번노드)를 새로운 노드의 다음 노드로 지정해주고 2번 노드의 다음 노드(3번노드)의 이전 노드를 새로운 노드로 지정해 줍니다.
그리고 2번 노드와 새로운 노드를 서로 이어주면 됩니다.
newNode <-> curNext NodeDL* curNext = current->nextNode; current->nextNode = newNode; // current -> newNode newNode->prevNode = current; // current <- newNode newNode->nextNode = curNext; // newNode -> curNext curNext->prevNode = newNode; // newNode <- curNext }
3. Tail 가져오기
NodeDL* DL_GetTailNode(NodeDL* head)
{
NodeDL* curNode = head;
while (curNode->nextNode != nullptr)
curNode = curNode->nextNode;
return curNode;
}
* 싱글과 마찬가지로 끝까지 노드를 돌고 그 노드를 리턴 받으면 됩니다.
4. 특정 인덱스 가져오기
NodeDL* DL_GetNodeAt(NodeDL* head, int index)
{
if (index < 0)
return nullptr;
int cnt = 0;
NodeDL* curNode = head;
while (cnt != index && curNode != nullptr)
{
curNode = curNode->nextNode;
cnt++;
}
return curNode;
}
* 마찬가지로 랜덤 엑세스는 불가능하고 순차적으로 찾아야 합니다.
5. Node 모두 출력
void DL_AllPrint(NodeDL* head)
{
NodeDL* curNode = head;
int cnt = 0;
printf("DL_AllPrint----------------------------------\n");
while (curNode->nextNode != nullptr)
{
cnt++;
printf("<-- [ %d ] -->", curNode->data);
if (cnt % 5 == 0)
printf("\n");
curNode = curNode->nextNode;
}
}
*순차적으로 돌면서 출력합니다.
6. 특정 인덱스 삭제
* 삭제할 노드의 이전 노드를 삭제할 노드의 다음 노드와 이어주고 , 삭제할 노드의 다음 노드의 이전 노드를 삭제할 노드의 이전 노드로 이어줍니다.
그 후 삭제할 노드를 삭제합니다.
void SL_RemoveAt(NodeSL** head,int index)
{
// index 가 0일 경우 head 를 지워야 한다.
if (index == 0)
{
NodeSL* temp = *head;
*head = ((*head)->nextNode);
delete temp;
return;
}
NodeSL* curNode = *head;
NodeSL* prevNode;
int cnt = 0;
while (curNode->nextNode != nullptr)
{
cnt++;
prevNode = curNode;
curNode = curNode->nextNode;
if (cnt == index)
{
prevNode->nextNode = curNode->nextNode;
delete curNode;
return;
}
}
}
7. 모든 노드 삭제
void DL_RemoveAll(NodeDL** head)
{
NodeDL* curNode = *head;
NodeDL* temp = nullptr;
while (curNode != nullptr)
{
temp = curNode;
curNode = curNode->nextNode;
delete temp;
}
*head = nullptr;
}
* 현재 노드의 다음 노드를 따로 빼고, 현재 노드를 삭제합니다. - 반복
환형 링크드리스트 (Circular Linked List)
- 더블 링크드리스트에서 Head 와 Tail 이 서로 맞물려있는 상태를 생각하시면 됩니다.
- Head 의 이전 노드는 Tail 이며 Tail 의 다음 노드는 Head 입니다.
- 따로 구현은 하지 않겠습니다. ( 간단하므로 )
싱글 링크드리스트 (Single Linked List) 와 더블 링크드리스트 (Double Linked List) 를 구현한 예제는 이곳에 있습니다.
소스코드 : MoonAuSosiGi's GitHub