[자료구조] 연결 리스트 | Linked List

연결 리스트는 값을 저장하고 있는 노드가 데이터와 포인터를 가지고 연결되는 방식으로 데이터를 저장하는 자료구조입니다.

1. 단일[Singly] 연결 리스트 # 포인터 공간이 1개
2. 이중[Doubly] 연결 리스트 # 포인터 공간이 2개
3. 원형[Circular] 연결 리스트 # 처음 노드와 끝 노드가 연결됨

단일 연결 리스트는 각 노드가 다음 노드의 위치를 포인터값으로 가지는 형태입니다.

 

이중 연결 리스트는 각 노드가 이전 노드와 다음 노드의 위치를 포인터값으로 가지는 형태입니다.

원형 연결 리스트는 일반적인 연결 리스트에서, 끝 노드가 다음 노드의 위치를 포인터값으로 가지는 형태입니다.

 

링크드리스트에서의 노드의 삽입과 삭제는 다음과 같습니다.

삽입의 경우, 기존 노드(Prev Node)의 포인터를 삽입하고자 하는 노드로(New Node),

삽입한 노드의 포인터를 기존 노드의 다음에 위치한 노드로(NextNode) 변경합니다.

 

삭제의 경우, 삭제하려는 노드(Delete Node)의 이전 노드의 포인터를(PrevNode) 다음 노드로(NextNode) 변경하고, 

삭제하려는 노드에 할당된 메모리를 해제합니다.

 

삽입
NewNode.next = PrevNode.next
PrevNode.next = NewNode

삭제
PrevNode.next = DeleteNode.Next
Free(DeleteNode) # --> 메모리 할당 해제

 

 

원하는 값을 찾는 방식은 다음과 같습니다.

링크드 리스트는,  맨 앞에 위치한 노드(Head Node)부터 시작해 순차적으로 원하는 값을 탐색합니다.

 

순회 및 탐색
NowNode = HeadNode
while NowNode != null: #원하는 노드를 찾을때까지 값을 순회하며 이동
    if NowNode.val == WantValue:
       return NowNode
    NowNode = NowNode.next
return -1 #원하는 값이 존재하지 않는 경우

 

링크드리스트는 배열과 달리 자료구조를 구성하는 각 노드들이 연속된 메모리 공간에 할당될 필요가 없다는 장점을 가지고 있습니다.

 

다만, 위에서 본 바와 같이, 링크트 리스트에서 값의 삽입과 삭제 자체는 O(1)의 연산을 필요로 하지만,

해당 노드의 포인터에 접근하기까지 O(N)의 연산을 필요로 하므로,

전체적인 동작에 있어 느린 시간 복잡도를 가짐을 알 수 있습니다.

 

때문에 이러한 문제의 해결을 위해 Key값을 가지는 노드들을 트리형태로 관리하는 B-Tree 자료구조가 고안되어

사용되고있습니다.