Linked List (연결 리스트) 란 ?
각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 각 노드는 기본적으로 저장할 "데이터"와 다음 노드가 어디에 있는지 알려주는 "포인터"를 가지고 있고, 이러한 구조가 연결리스트의 연결을 가능하게 한다.
Linked List 의 시간 복잡도
일반적으로 앞에서부터 탐색을 하고 찾은 후에 변경하기 때문에 모두 O(n)의 시간 복잡도를 가지고 있다. 하지만 구현하기에 따라 더 효율적으로 만들 수 있다. 맨 앞 노드(head), 맨 뒤 노드(tail)을 이용하는 방법인데 이는 코드로 구현해보겠다.
| 조회 | O(n) |
| 삽입 | O(n) |
| 수정 | O(n) |
| 삭제 | O(n) |
Linked List의 종류
단일(단방향) 연결 리스트
각 노드가 포인터 공간을 하나만 가지고 있으며 포인터가 다음 노드(next)를 가리킨다.
장점
- 구조가 단순하고 메모리 사용이 효율적이다 (포인터 하나만 필요하기 때문에)
단점
- 역방향으로 이동이 불가능하다.
- 삭제 시 이전 노드에서 다음 노드를 삭제하는 구조라서 삭제할 노드의 앞 노드를 알아야 한다.
이중(양방향) 연결 리스트
각 노드가 두 개의 포인터 공간을 가지고 있고, 각 포인터는 이전(prev), 다음(next) 노드를 가리킨다.
장점
- 양방향 탐색 가능
- 탐색, 삽입,삭제가 비교적 더 자유로움
단점
- 비교적 메모리를 더 사용한다.
원형 연결 리스트
마지막 노드와 처음 노드를 연결 시켜(마지막 노드의 포인터가 첫번째 노드를 가리키는) 원형으로 만든 구조이다. 단일, 이중 연결 리스트 모두에서 사용이 가능하다.
마지막 노드의 next를 처음 노드로 연결 시켰기 때문에, head를 마지막 노드를 가리키게 하면, 리스트의 처음과 끝에 쉽게 삽입할 수도 있다.
장점
- 어느 노드에서든 순회가 가능하다 (시작 지점이 꼭 head일 필요가 없다.)
단점
- 무한 루프를 의식해야한다
구현
연결리스트의 삽입, 삭제, 조회 기능구현
단일 연결 리스트
Node + linkedList 틀 만들기
class Node {
next = null;
constructor(value) {
this.value = value;
}
}
class LinkedList {
head = null;
length = 0;
add(value) {}
search(index) {}
remove(index) {}
}
삽입 O(n) : Add 구현
add 시 고려할 점 : 비어있는 리스트인가? -> head가 있는지 없는지 조건문으로 판단하여 구현
add 메서드에 value를 넣었는데 value를 반환하면 이상할 것 같아서 add할 때마다 리스트의 length를 반환하기로 했다.
class LinkedList {
head = null;
length = 0;
add(value) {
if(this.head) {
let current = this.head;
while(current.next) {
current = current.next;
}
current.next = new Node(value);
} else {
this.head = new Node(value);
}
this.length++;
console.log(this.length);
return this.length
}
}
조회 O(n) : Search 구현
class LinkedList {
head = null;
length = 0;
search(index) {
let count = 0;
let current = this.head;
while(count < index) {
current = current?.next;
count++;
}
return current?.value
}
}
삭제 O(n) : remove 구현
단일 연결리스트의 단점을 위에서 얘기한 것처럼 삭제 시에는 삭제할 index까지 탐색 후 이전 노드를 이용해서 삭제를 해야한다.
class LinkedList {
head = null;
length = 0;
remove(index) {
let count = 0;
let current = this.head;
let prev;
while(count < index) {
prev = current;
current = current?.next;
count++;
}
if(prev && current) {
this.length--;
prev.next = current.next;
} else if (current) {
this.head = current.next;
this.length--;
}
return this.length;
}
}
코드를 구현하고 보니 remove는 결국 search 이후에 제거를 하는 것이기에 리팩토링을 할 수 있을 것 같다.
search, remove 리팩토링
linkedlist의 search, remove의 공통되는 코드를 빼내서 private 클래스를 이용하여 #search 메서드를 만들어놓고, search와 remove메서드에서 적절히 쓰면 좋을 것 같다.
class LinkedList {
head = null;
length = 0;
#search(index) {
let count = 0;
let current = this.head;
let prev;
while(count < index) {
prev = current;
current = current?.next;
count++;
}
return [prev, current];
}
search(index) {
return this.#search(index)[1]?.value;
}
remove(index) {
const [prev, current] = this.#search(index);
if(prev && current) {
this.length--;
prev.next = current.next;
} else if (current) {
this.head = current.next;
this.length--;
}
return this.length;
}
}// 테스트코드
const ll = new LinkedList();
ll.add(1); // length : 1
ll.search(3); // undefined
ll.add(2); // length : 2
ll.add(3); // length : 3
ll.add(4); // length : 4
ll.add(5); // length : 5
ll.search(3); // 4
ll.search(10); // undefined
ll.remove(3) // length : 4
ll.remove(0) // length : 3
ll.search(3); // lundefined
이중 연결리스트
1. Node에 prev 프로퍼티를 만들어놓고 삽입할때마다 prev를 업데이트 해주기 -> 각 노드마다 이전 값을 기억하도록 저장
2. 리스트에 tail 프로퍼티를 추가하여 add 시마다 업데이트하여 삽입을 O(1) 로 만들어보기
3. tail이 추가됨에 따라 remove 시에도 tail을 업데이트 해줘야한다.
+ 원형 연결리스트로 가려면 아래 코드에서 tail과 head만 연결 시켜주면 된다.
class Node {
prev = null;
next = null;
constructor(value) {
this.value = value;
}
}
// 이전 값 찾기 해보기 Node에 prev
// 삽입을 O(1) 로 만들어보기 tail add할 때마다 tail에 넣으면 되지않을까?
class LinkedList {
head = null;
tail = null;
length = 0;
add(value) {
const newNode = new Node(value);
if(this.head) {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
} else {
this.head = newNode;
this.tail = newNode;
}
this.length++;
console.log(this.length);
return this.length
}
#search(index) {
let count = 0;
let current = this.head;
let prev;
while(count < index) {
prev = current;
current = current?.next;
count++;
}
return [prev, current];
}
search(index) {
return this.#search(index)[1]?.value;
}
remove(index) {
const [prev, current] = this.#search(index);
if(prev && current) {
if(!current.next) { // 마지막 node 삭제인 경우
prev.next = null;
this.tail = prev;
} else { // 중간 node 삭제인 경우
prev.next = current.next;
current.next.prev = prev;
}
this.length--;
} else if (current) { // index 가 0일 때
this.head = current.next;
this.length--;
} else {
// 삭제하고자 하는 대상이 없을 때 아무것도 안함
}
return this.length;
}
}
const ll = new LinkedList();
// 테스트코드
ll.add(1); // length : 1
ll.search(3); // undefined
ll.add(2); // length : 2
ll.add(3); // length : 3
ll.add(4); // length : 4
ll.add(5); // length : 5
ll.search(3); // 4
ll.search(10); // undefined
ll.remove(3) // length : 4
ll.remove(0) // length : 3
ll.search(3); // lundefined