[자바스크립트] 연결리스트(Linked List) 예시를 통해 쉽게 이해하기 (1)
연결리스트(Linked List)란?
연결리스트는 모든 요소(a.k.a 노드)가 다음 요소에 연결된 자료구조입니다. 예를 들어 학교의 한 반에 있는 학생들을 데이터로 저장한다면, 1번 학생 데이터를 노드로 생성할 때 2번 학생 데이터가 어디에 있는지 노드의 위치를 표시하는 방식입니다.
자료가 연결되어있기 때문에 새로운 자료를 앞쪽에 추가/삭제할 때 굉장히 유용하게 사용할 수 있습니다. 하지만 특정한 자료를 불러올 때는 무조건 순회하며 찾아가는 과정이 필요하기 때문에 특정한 노드를 찾기 까다롭다는 단점이 있습니다. 위 예시에서 3번 학생 데이터를 확인하기 위해선 2번 학생 데이터를 무조건 거쳐야 3번 학생 데이터가 어디있는지 알 수 있습니다. 만약 1만명의 학생들이 엮여있다면, 특정 학생을 찾을 때마다 꽤나 고생해야되겠죠. 이럴 경우에는 배열 자료구조를 사용하는 편이 훨씬 효율적일 것입니다. 그렇기 때문에 배열과 연결리스트의 장단점은 서로 반대라고 이해하시면 됩니다.
구현방법
연결리스트 노드에는 데이터를 저장할 value 프로퍼티, 다음 노드의 위치를 알려주는 next 프로퍼티가 있습니다.
// 노드 클래스
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}각 노드가 다음 노드를 가리키는 방식을 단일 연결리스트(Singly Linked List)라고 합니다.
단일 연결리스트(Singly Linked List)
class LinkedList {
constructor() {
this.root = null;
this.size = 0;
}
}
연결 리스트 끝에 요소 추가/제거
- 연결리스트의 루트 노드에 값이 존재하지 않는다면 바로 노드를 추가하면 됩니다.
- 반대로 연결리스트에 이미 노드가 존재할 경우 가장 끝 노드를 찾기 위한 순회가 필요하고, 가장 끝 노드에 도달했을 때 끝 노드에 추가할 노드를 연결합니다.
// LinkedList.prototype.addLast
addLast(value) {
const node = new Node(value);
if (this.root) {
let currentNode = this.root;
while(currentNode && currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = node;
} else {
this.root = node;
}
this.size++;
}첫 노드를 추가할 때 시간복잡도는 O(1)이지만, 다음 노드를 추가할 때는 연결된 노드의 개수만큼 순회가 필요하기 때문에 O(n) 시간복잡도를 가집니다.
연결리스트 끝 노드를 제거하는 코드도 이와 비슷합니다. 끝 노드의 이전 노드까지 도달하기 위해 순회가 필요하기 때문입니다. 마지막 이전 노드를 찾고, next 참조값을 null로 변경해야 합니다.
// LinkedList.prototype.removeLast
removeLast() {
let currentNode = this.root;
let target;
if (currentNode && currentNode.next) {
while(currentNode && currentNode.next && currentNode.next.next) {
currentNode = currentNode.next;
}
target = currentNode.next;
currentNode.next = null;
} else {
this.root = null;
target = currentNode;
}
this.size--;
return target.value;
}마지막 노드의 이전까지 도달해야되기 때문에 시간복잡도는 O(n)입니다.
연결리스트 시작 부분에 노드 추가/제거
연결리스트 시작 부분에 노드를 추가하는 것은 매우 쉽습니다. 노드를 생성하고, 루트노드를 생성한 노드의 다음 참조로 추가한 뒤, 연결리스트 루트를 노드로 변경하면 됩니다.
// LinkedList.prototype.addFirst
addFirst(value) {
const node = new Node(value);
node.next = this.root;
this.root = node;
}시작 부분의 노드를 삭제하는 방법도 간단합니다. 가장 앞쪽 노드의 next를 root 노드로 변경하면 됩니다.
removeFirst() {
const target = this.root;
if (target) {
this.root = target.next;
return target.value
}
}예상대로 연결리스트에서 첫 번째 요소를 제거/추가하는 시간복잡도는 O(1)로 항상 일정합니다.
노드 검색
연결리스트를 순회하며 노드를 검색합니다. 특정 노드를 찾기 위해 순회작업이 필요하기 때문에 O(n) 시간복잡도를 가지고 있습니다.
contains(value) {
let currentNode = this.root;
let i = 0;
while(currentNode) {
if (currentNode.value === value) {
return i;
}
currentNode = currentNode.next;
i++;
}
}시간복잡도 (Time Complexity)
| 구현로직 | 시간복잡도 |
| addFirst | O(1) |
| addLast | O(n) |
| removeFirst | O(1) |
| removeLast | O(n) |
| contains | O(n) |
전체 코드 예시
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.root = null;
this.size = 0;
}
addLast(value) {
const node = new Node(value);
if (this.root) {
let currentNode = this.root;
while(currentNode && currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = node;
} else {
this.root = node;
}
this.size++;
}
removeLast() {
let currentNode = this.root;
let target;
if (currentNode && currentNode.next) {
while(currentNode && currentNode.next && currentNode.next.next) {
currentNode = currentNode.next;
}
target = currentNode.next;
currentNode.next = null;
} else {
this.root = null;
target = currentNode;
}
this.size--;
return target.value;
}
/**
* 시간복잡도: O(1)
* @param {any} value
*/
addFirst(value) {
const node = new Node(value);
node.next = this.root;
this.root = node;
}
removeFirst() {
const target = this.root;
if (target) {
this.root = target.next;
return target.value
}
}
contains(value) {
let currentNode = this.root;
let i = 0;
while(currentNode) {
if (currentNode.value === value) {
return i;
}
currentNode = currentNode.next;
i++;
}
}
add(value, index = 0) {
if (index === 0) {
return this.addFirst(value);
}
}
remove(index = 0) {
if (index === 0) {
return this.removeFirst();
}
}
}