자료구조 - 링크드 리스트(Linked List)

 

링크드 리스트의 노드의 구성이 이렇다.

1. 데이터를 보관하는 필드

2. 다음 노드를 연결해주는 포인터

 

데이터를 추가 시키면 결국 이런 모양이 될 것이다.

 

 

typedef struct tagNode{ int Data; //데이터 필드 struct tagNode *NextNode; //다음노드에 대한 포인터 }Node;

 

Node *SLL_CreatNode(int NewData){ Node *NewNode = (Node*)malloc(sizeof(Node)); //void* malloc(size_t size); NewNode->Data = NewData; //데이터저장 NewNode->NextNode = NULL; //다음노드를 가리키는 포인터 NULL로 초기화 return NewNode; }

 

void SLL_DestoryNode(Node* Node){ free(Node); //void free(void *memblock) }

 

void SLL_AppendNode(Node** Head, Node* NewNode){ if((*Head)== NULL) //헤드노드가 NULL이면 새로운 노드가 헤드노드 *Head = NewNode; else{ //테일노드를 찾아 NewNode에 연결 Node* Tail = *Head; while(Tail->NextNode != NULL) Tail = Tail->NextNode; Tail->NextNode = NewNode; } }

여기서 이중간접연산자(**)가 필요한 이유

초기에는 생성된 노드가 없기 때문에 SLL_AppendNode()함수는 NULL인 Head포인터를 전달인수로 받는다.

그런데 이 Head포인터가 NULL이므로 단지 간접연산자(*)로만 전달을 받는다면  

 

특히 이부분(*Head로 전달받았다고 가정했을 때)

 if((Head)== NULL)
   //헤드노드가 NULL이면 새로운 노드가 헤드노드
      Head = NewNode;

에서 Head의 값은 주소값이 아니라 NULL이므로

Head = NewNode; 의 연산은 의미가 없는 것이다.

 

이를 해결하기 위해 포인터값이 아니라 포인터의 주소값을 전달인수로 넘겨야 하고

이중 간접연산자(**)를 사용하는 것이다.

 

 

void SLL_GetNodeAt(Node* Head, int Location){ Node* Current = Head; while(Location--) Current = Current->NextNode; return Current; }

일단 배열과 비교하기 위해

index개념으로 찾도록 짰다.

 

노드를 삭제하는 개념이 대충 이렇다.

(삭제할 노드를 가리키는 노드의 포인터를 삭제할 노드가 가리키는 노드를 가리키도록 지정)

(삭제할 노드는 단순히 free()함수로 메모리에서 삭제)

 

void SLL_RemoveNode(Node** Head, Node* Remove){ if((*Head) == Remove) //삭제할 노드가 헤드노드라면 *Head = Remove->NextNode; else{ Node* Current = *Head; while(Current->NextNode != Remove) Current = Current->NextNode; if(Current != NULL) Current->NextNode = Remove->NextNode; } }

여기서는 Head가 이미 값을 가지고 있을 것이므로

이중간접연산자(**)를 사용 할 필요는 없지만 SLL_AppendNode()함수와 일관성을 유지하기 위한 것 같다.

 

그리고 마지막으로 삭제할 노드는 따로 SLL_DestroyNode()함수로 삭제해주어야 한다.

코드에 else문 끝나고 추가해도 되지만 지금 내가 공부하고 있는 책에는 이렇게 적혀있는 걸.ㅋ 

 

 

int SLL_CetNodeCount(Node* Head){ unsigned int Count = 0; Node* Current = Head; while(Current != NULL){ Current = Current->NextNode; Count++; } return Count; }

 

보통 링크드 리스트는 배열에 비해 테이터의 삽입과 삭제가 빠른편이지만,

포인터로 메모리가 4byte를 더 사용하며, 특정 위치에 있는 노드를 찾을 때(탐색)의 속도는 배열보다 느리다.

따라서 링크드 리스트는 데이터의 추가/삽입/삭제가 잦고 조회가 드믄 자료구조에 적합하다.