추가와 삭제 로직이 많은 경우, 배열을 이용하면 시간 복잡도가 상당히 늘어나게 된다.
배열은 탐색에 유리하다.
이럴 때 유용하게 사용하기 위해 연결리스트가 등장했다.
1. 연결리스트란?
연결 리스트는 각요소를 포인터로 연결하여 관리하는 선형 자료구조다.
각 요소는 노드라고 부르고 데이터 영역과 포인터 영역으로 구성된다.
Head는 첫번째 노드를 가리킨다.
2. 연결리스트의 특징
- 메모리가 허용하는한 요소를 제한없이 추가할 수 있다.
- 탐색은 O(n)이 소요된다.
- 요소를 추가하거나 제거할 때 O(1)이 소요된다.
3. 배열과의 차이
3.1 메모리
메모리의 관점에서 볼 때 배열은 여러 값들을 연속적으로 담고 있어 메모리에서도 연속성을 띄고 있지만 연결리스트는 각각의 노드들이 흩어져있어 메모리 공간상에서도 흩어져 있는 것을 볼 수 있다.
3.2 배열 요소 삭제
배열에서는 요소를 삭제하면 뒤에 있는 요소를 앞으로 한칸씩 당겨야한다.
3.3 배열 요소 추가
배열에서는 요소를 추가하면 뒤로 한칸씩 미뤄야한다.
3.4 연결리스트 요소 삭제
원래 가리키고 있던 노드를 끊어주고 원래 가리키던 노드의 이전 노드를 원래 노드의 다음 노드를 가리키게 해준다. 그리고 원래 노드를 삭제하면 끝이난다.
상수시간 밖에 걸리지 않음을 알 수 있다.
3.5 연결리스트 요소 추가
요소 삭제와 마찬가지이다.
4. Singly Linked List
Head에서 Tail까지 단방향으로 이어지는 연결 리스트 가장 단순한 형태의 연결 리스트이다.
4.1 요소 찾기
4.2 요소 추가
4.3 요소 삭제
5. Doubly Linked List
5.1 요소 추가
5.2 요소 삭제
6. Circular Linked List
Singly 혹은 Doubly Linked List에서 Tail이 Head로 연결되는 연결 리스트 메모리를 아껴쓸 수 있다. 원형 큐 등을 만들때도 사용된다.
7. 구현(Singly Linked List)
{
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class SinglyLinkedList {
constructor() {
this.head = null;
this.tail = null;
}
// 찾기
find(value) {
let currNode = this.head;
while (currNode.value !== value) {
currNode = currNode.next;
}
return currNode;
}
// 끝부분 추가 로직
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;
}
}
// 중간 위치에 삽입 : node 다음에 newValue를 가진 노드가 오도록
insert(node, newValue) {
const newNode = new Node(newValue);
// 기존 node가 가리키는 값은 이제, newNode가 가리켜야함
newNode.next = node.next;
// 기존 node는 newNode를 가리키도록
node.next = newNode;
if (newNode.next === null) {
this.tail = newNode;
}
}
remove(value) {
// O(n)
let prevNode = this.head;
if (prevNode.value === value) {
this.head = this.head.next;
return true;
}
while (prevNode.next.value !== value) {
prevNode = prevNode.next;
}
if (prevNode.next !== null) {
// 지우고자하는 노드는 누구도 가리키지 않게됨 : 가비지 컬렉션으로 메모리에서 제거됨
prevNode.next = prevNode.next.next;
if (prevNode.next === null) {
this.tail = prevNode;
}
} else {
throw new Error('Invalid node');
}
}
display() {
let currNode = this.head;
let displayString = '[';
while (currNode !== null) {
displayString += `${currNode.value}, `;
currNode = currNode.next;
}
// displayString에 매번 붙여준 코드들 끝에는 ", "가 존재함. length길이 - 2를 수행해 이것들을 제거해줌
displayString = displayString.substring(0, displayString.length - 2);
displayString += ']';
console.log(displayString);
}
}
const linkedList = new SinglyLinkedList();
linkedList.append(1);
linkedList.append(3);
linkedList.append(4);
linkedList.display();
console.log(linkedList.find(4));
// fix error : insert가 제일 앞에 있는 경우
linkedList.insert(linkedList.find(1), 2);
linkedList.display();
// fix error : insert가 제일 뒤에 있는 경우
linkedList.insert(linkedList.find(4), 5);
linkedList.display();
// fix error : remove가 제일 앞에서 발생하는 경우
linkedList.remove(2);
linkedList.display();
// fix error : remove가 제일 뒤에서 발생하는 경우
linkedList.remove(5);
linkedList.display();
}
오호