[자료구조] 연결 리스트 vs 배열 / JavaScript로 연결 리스트 구현하기 (Linked List, Array)
오늘은 선형 자료구조인 연결 리스트(Linked List), 배열(Array)에 대해 알아보자!
추가로 JavaScript로 연결 리스트를 직접 구현해보자! 🤓
1. 선형 자료구조 vs 비선형 자료구조
선형 자료구조
선형 자료 구조는 요소가 일렬로 나열되어 있는 자료 구조이다.
연결 리스트, 배열, 벡터, 스택, 큐 등이 있다.
비선형 자료구조
비선형 자료구조는 요소가 일렬로 나란하지 않고 자료 순서와 관계가 복잡한 구조이다.
일반적으로 트리, 그래프가 있다.
2. 배열 vs 연결 리스트
배열 (Array)
배열은 크기가 정해져 있는 자료구조이며, 같은 타입의 변수들이 인접한 메모리에 위치해 있다.
시간 복잡도
array[0]와 같이 인덱스로 바로 접근이 가능하여 탐색에 O(1) 시간이 걸리고 랜덤 접근이 가능하다.
하지만, 삽입과 삭제를 할 때 요소들의 메모리를 이동해야하기 때문에 O(n) 시간이 걸린다.
연결 리스트 (Linked List)
연결 리스트는 데이터를 감싼 노드를 포인터로 연결해서 공간 효율성을 극대화시킨 자료 구조이다. 배열과 달리 데이터가 인접한 메모리에 위치하지 않아도 된다.
시간 복잡도
랜덤 접근이 불가능하고 요소를 하나씩 확인하며 다음 노드를 찾아가야 하기 때문에 탐색에 O(n) 시간이 걸린다.
반면, 삽입과 삭제를 할 때는 이전, 다음 노드의 연결을 제어하면 되기 때문에 O(1) 시간이 걸린다.
첫번째 노드를 헤드(head)라고 부르며, 각 노드는 연결에 대한 정보를 가지고 있어 정보에 따라 다음 세가지 연결 리스트로 나뉜다.
- 싱글 연결 리스트: next 포인터만 가진다.
- 이중 연결 리스트: prev, next 포인터를 가진다.
- 원형 이중 연결 리스트: prev, next 포인터를 가지고, 마지막 노드의 next 포인터가 헤드 노드를 가리킨다.
그래서 뭘 써야 하나?!
- 배열: 탐색이 빠르다.
- 연결 리스트: 삽입/삭제가 빠르다.
⇒ 상황에 맞는 자료구조를 선택하는 것이 중요하다.
3. JavaScript로 연결 리스트 구현하기 ⭐️
- 각 노드는 자신의 데이터와, 다음 노드에 대한 정보를 가진다.
- 연결 리스트는 head, size 정보 갖고, 삽입/삭제 메서드를 포함한다.
(인덱스 에러 처리는 따로 하지 않았다. 여러분들이 직접 구현해보길,,,ㅎㅎ)
class Node {
constructor(data, next = null) {
this.data = data;
this.next = next;
}
}
class LinkedList {
#size;
// size는 외부에서 변경할 수 없도록 private field로 선언했다.
constructor(data) {
this.head = new Node(data);
this.#size = 1;
}
get size() {
// 외부에서는 getter를 이용한 조회만 가능하다.
return this.#size;
}
insertLast(value) {
let curr = this.head;
// 다음 노드가 존재하지 않는 마지막 노드까지 이동한다.
while (curr.next !== null) {
curr = curr.next;
}
// 마지막 노드의 다음에 새로운 노드를 추가하고, 사이즈를 증가시킨다.
curr.next = new Node(value);
this.#size++;
}
insertAt(index, value) {
const newNode = new Node(value);
if (index === 0) {
// 첫번째 index에 추가하는 경우
// 새로운 노드의 다음 노드로 첫번째 노드를 할당한다.
// 새로운 노드를 head에 할당한다.
newNode.next = this.head;
this.head = newNode;
} else {
// 두번째~ index에 추가하는 경우
// 이전 노드와 다음 노드의 중간에 새로운 노드를 추가한다.
const preNode = this.getAt(index - 1);
const nextNode = preNode.next;
preNode.next = newNode;
newNode.next = nextNode;
}
// 사이즈를 증가시킨다.
this.#size++;
}
deleteNode(index) {
if (index === 0) {
// 첫번째 index를 삭제하는 경우
// 다음 노드를 head에 할당한다.
this.head = this.head.next;
} else {
// 두번째~ index를 삭제하는 경우
// 이전 노드와 다음 노드를 연결한다.
const preNode = this.getAt(index - 1);
preNode.next = preNode.next.next;
this.#size--;
}
}
getAt(index) {
// head 노드부터 index 만큼 다음 노드를 찾아간다.
let count = 0;
let node = this.head;
while (count < index) {
node = node.next;
count++;
}
return node;
}
printAll() {
// head 노드부터 마지막 노드까지 노드를 출력한다.99-
let curr = this.head;
while (curr !== null) {
console.log(curr.data);
curr = curr.next;
}
}
}여담
몇달 전만 하더라도 다른 사람 코드를 보고 이해하는 것조차 힘들었는데 지금은 스스로 자료구조를 구현할 수 있게 되어 굉장히 뿌듯하다. 🥹
덧붙여서 메모리(stack, heap, GC)와 JavaScript Class, prototype 공부를 해두길 정말 잘했다! 코딩을 하면 할수록 CS 지식과 언어에 대한 심화 지식은 필수인 것 같다. 그리고 그게 재밌어서 넘 다행이다,,ㅎㅎ 역시 난 born to be 공순이 😉
이제 stack, queue 자료형도 구현해보도록 하자!
Reference
