연결리스트의 경우 O(1)에 삽입 및 삭제가 가능하다

by 지원
…
끄적임
|
이야기

연결 리스트의 특징:

  1. 각 데이터는 노드(Node)로 구성이 되어있다
  2. 노드는 메모리상 서로 각기 다른 위치에 존재한다
  3. 포인터를 이용하여 노드들을 연결한다

포인터를 통해 노드를 연결하다 보니, 삽입의 경우는 포인터로 다음 노드를 가리키면 끝이다.

-----------
| newNode | 
-----------
-----------     -----------
|  nodeA  | --> |  nodeB  |
-----------     -----------
// nodeA와 nodeB 사이에 newNode 삽입
int data = 17;
Node *newNode = new Node(data);

newNode->next = nodeA->next
nodeA->next = newNode
-----------     -----------     -----------
|  nodeA  | --> | newNode | --> |  nodeB  |
-----------     -----------     -----------

마찬가지로 삭제의 경우, 삭제가 될 노드와 연결되어 있는 노드(들)의 포인터를 해제하면 된다.

// newNode (두 번째 노드) 삭제
Node *curr = nodeA

Node *removeNode = curr->next;
curr->next = curr->next->next

removeNode->next = NULL;
delete removeNode
-----------     -----------
|  nodeA  | --> |  nodeB  |
-----------     -----------

삽입과 삭제의 경우 좋은 성능을 보이지만, 노드를 사용하는 만큼 메모리 사용량이 증가한다. 또한 삽입할 위치를 탐색하거나, 삭제할 노드가 있는 위치 만큼 이동을 해야하기 때문에 삽입 및 삭제 함수 자체의 시간복잡도는 O(n)이 된다. 이는 어디까지나 탐색의 시간이 포함된 것 뿐, 삽입과 삭제는 O(1)이다.

확장 🌱

  • 노드를 사용하므로써 메모리 사용량이 증가하지만, 배열보다는 메모리 친화적이지 않을까? 배열과 다르게 낭비되는 자원이 없으니까. -> 250516124750
    • 정말 없을까? 일단 메모리 누수의 위험도는 배열보다 높음. 포인터를 실수로 날려버리거나 덮어씌우면 그 이후 노드에 접근할 수 없음. -> 250517213935
  • 노드를 template로 구현하면, 각 노드마다 다른 타입의 데이터를 담을 수 있을까?
    • Node<int> nodeA -> Node<bool> nodeB -> Node<double> nodeC
  • 포인터가 없는 혹은 사용할 수 없는 언어들의 경우, 연결리스트를 구현하는 방법

관련 노트 📘

  • 250512043750 - 배열의 삽입과 삭제에는 O(n)의 시간이 필요하다
Backlinks: