유튜브 동영상 거니님의 더블 링크드 리스트를 보면서 따라해본 코드이다.
정말 어려웠는데, 직접 구현하시는 걸보니 조금 이해가 되었다. 정말 유익한 영상이다.
#include <stdio.h>
#include <stdlib.h>
typedef struct listNode{
int Data;
struct listNode* Next;
struct listNode* Prev;
}Node;
// node creation
Node* createNode(int data){
Node* newNode = (Node *)malloc(sizeof(Node));
// varaibles initialization
newNode -> Data = data;
newNode -> Next = NULL;
newNode -> Prev = NULL;
return newNode;
}
//메모리 상에서 free 노드 - 청부업자
void deleteNode(Node * Node){
free(Node);
}
Node* getNodeAt(Node* head, int index){
Node* horse = head;
int count = 0;
while(horse != NULL){
if(count++ == index){
return horse;
}
horse = horse -> Next;
}
return NULL;
}
int countNode(Node* head){
int count = 0;
Node *horse = head;
while(horse != NULL){
horse = horse -> Next;
count ++;
}
return count;
}
void addNode(Node **head, Node* newNode){
//이걸 업데이트를 해줘야 하기 때문에 더블 포인트를 받아왔다.
//리스트에 아무것도 없는데 추가하고 싶은 상황
if(( *head) == NULL){
*head = newNode;
}
//리스트가 존재할 때 맨 뒤에 추가하는
else{
Node* horse = (*head);
while(horse -> Next != NULL){
horse = horse -> Next;
}
horse-> Next = newNode;
newNode->Prev = horse;
}
}
void insertAfter(Node* Current, Node* newNode){
//head
if(Current->Prev == NULL && Current->Next == NULL){
Current->Next = newNode;
newNode->Prev = Current;
}
//not head
//if tail
if(Current->Next == NULL){
Current ->Next = newNode;
newNode ->Prev = Current;
}
else{// int the middle of 2 nodes
Current->Next->Prev = newNode;
newNode->Prev = Current;
newNode->Next = Current->Next;
Current->Next = newNode;
}
}
//실질적으로 메모리를 지우는 함수, 헤드에 변화가 일어나기에 이중 포인터를 받음
void removeNode(Node** head, Node* remove){
// 지울 노드가 헤드일 때, 헤드는 우리가 추적하는 것이므로 한단계 앞으로 이동시켜준다.
if(*head == remove){
*head = remove->Next;
}
deleteNode(remove);
// remove 노드의 다음 링크에 노드가 있을 때
if(remove->Next != NULL){
remove->Next->Prev = remove->Prev;
}
// remove 노드의 이전 링크에 노드가 있을 때
if(remove->Prev != NULL){
remove->Prev->Next = remove->Next;
}
}
int main(void){
int i = 0;
int count = 0;
// future head
Node* List = NULL;
// temporary Node
Node* newNode = NULL;
//current node
Node* Curr = NULL;
for( i = 0; i < 5; i++)
{
newNode = createNode(i);
addNode( &List, newNode);
}
// 위에서 노드 다섯개 생성
count = countNode(List);
for(i = 0; i < count; i++)
{
Curr = getNodeAt(List,i);
printf("List[%d] = %d\n", i, Curr->Data);
}
printf("----------5 nodes created ----------\n");
// 위에서 노드가 잘 들어왔나 프린트
//다음은 99라는 노드를 생성하고 0다음에 그녀석을 집어 넣을거야
newNode = createNode(99);
Curr = getNodeAt(List,0);
insertAfter(Curr,newNode);
//444라는 노드를 생성하고 그걸 4번째 녀셕 다음에 집어넣을거야
newNode= createNode(444);
Curr = getNodeAt(List,4);
insertAfter(Curr,newNode);
//그리고 프린트를 해본다.
count = countNode(List);
for(i=0; i< count; i++)
{
Curr = getNodeAt(List,i);
printf("List[%d] = %d\n", i, Curr-> Data);
}
printf("----------After 2 Nodes inserted ----------");
//이제 노드를 지울거야.인덱스 1에있는 노드 지우고, 이에 있는 노드 0에 있는 노드 지우고
newNode = getNodeAt(List,1);
removeNode(&List, newNode);
newNode = getNodeAt(List,0);
removeNode(&List, newNode);
//그리고 프린트를 해본다.
count = countNode(List);
for (i = 0 ; i< count; i ++)
{
Curr = getNodeAt(List, i);
printf("List[%d] = %d\n", i, Curr -> Data);
}
printf("--------After Node with index 1 removed----------\n");
return 0;
}
참고자료