[자료구조] 연결리스트(Linked List)
삽입과 삭제가 자주 반복되는 로직에서는 어떤 자료 구조를 사용해야할까?
배열의 경우 자료 탐색 시 인덱스를 알고 있다면 상수 시간 복잡도 O(1)을 가지지만, 삽입과 삭제의 경우는 선형 시간 복잡도 O(n)를 갖게 되기 때문에 자료를 삽입, 삭제하는 것보단 탐색하는데에 유리하다.
따라서 삽입과 삭제가 자주 일어나는 경우에는 배열보다는 연결 리스트를 사용하는 것이 바람직하다.
연결 리스트
각 요소를 포인터로 연결해 관리하는 선형 자료 구조이다. 이때 각 요소를 노드라고 부르며 노드는 데이터 영역과 포인터 영역으로 구분된다.
연결 리스트의 특징
-메모리가 허용하는 한 노드를 제한없이 추가할 수 있다.
-탐색 시 시간 복잡도는 O(n)이다.
-노드 삽입 및 삭제할 때의 시간 복잡도는 O(1)이다.배열과 연결 리스트의 차이점
메모리 차이
배열은 순차적으로 데이터가 들어가기 때문에 메모리 영역을 연속적으로 사용한다. 반면에, 연결 리스트는 순차적이지 저장되지 않기에 데이터가 메모리 상에 퍼져 있으며, 퍼져 있는 메모리 영역을 알기 위해 포인터를 사용하여 각 영역을 참조한다.
요소 삽입, 삭제 방식 차이
배열
노드 삭제 시, 삭제 된 노드의 공백을 채우기 위해 뒤의 노드들을 앞으로 당겨줘야 하기 때문에 O(n)의 시간이 소요된다.
노드 추가도 마찬가지로 중간에 노드를 추가하게 되면 뒤의 노드들을 한 칸씩 뒤로 이동해야하기 때문에 O(n)의 시간이 소요된다.
연결 리스트
노드 삭제 시, 삭제할 노드 선택하고, 삭제할 노드의 이전 노드가 가리키는 포인터를 삭제할 노드 다음 노드에 연결한다. 그리고 삭제할 노드를 제거해주면 간단하게 노드를 삭제할 수 있다. 이때 걸리는 시간은 O(1)이다.
노드 삽입 시, 먼저 삽입할 노드의 포인터를 끼워 놓을 부분 다음 노드를 가리키게 한다. 이어서 끼워 놓을 부분 이전 노드의 포인터를 삽입할 노드를 가리키도록 수정한다. 이때의 로직은 O(1)의 시간이 소요된다.
연결 리스트 요소 탐색과 시간 복잡도
리스트의 헤드부터 차례대로 탐색하여 노드를 찾기 때문에 O(n)의 시간이 소요된다.
단일 연결 리스트(SinglyLinkedList) 구현하기
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
}
find() {
// 노드 탐색
let currentNode = this.head;
// 현재 노드가 찾는 값이 아니라면 다음 노드로 이동
while (currentNode.value !== value) {
currentNode = currentNode.next;
}
return currentNode;
}
append(newValue) {
const newNode = new Node(newValue);
// 추가하려는 노드가 첫 번째 노드라면
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
}
insert(node, newValue) {
const newNode = new Node(newValue);
newNode.next = node.next;
node.next = newNode;
}
remove(value) {
let prevNode = this.head;
// 삭제할 노드의 이전 노드를 찾기
while (prevNode.next.value !== value) {
prevNode = prevNode.next;
}
if (prevNode.next !== null) {
prevNode.next = prevNode.next.next;
}
}
}