연결리스트
순서가 있는 데이터들을 저장할 때 그 다음(이전) 순서의 데이터가 있는 주소를 현재 데이터에 포함시키는 방식으로 자료를 저장하는 구조
노드
연결 리스트에서 노드는 데이터와 포인터를 가지는 객체를 의미
- 포인터 : 다음 노드의 주소
- 각 포인터 변수의 주소도 따로 존재한다.
장점
- 필요할 때마다 데이터를 생성하여 연결하면 되기 때문에 메모리 효율 좋음
- 삭제 및 추가 시 데이터 재구성 용이
단점
- 탐색 시 느림
(처음 또는 마지막 노드 탐색은 빠름) - 구현이 까다롭다
- 데이터를 저장할 공간 뿐만 아니라 다음 노드의 주소를 저장하는 공간이 추가적으로 필요
사용
자바스크립트에서는 포인터가 없다. 때문에 객체를 참조하는 방식으로 구현
(오히려 더 간단하다)
연결리스트 구현
function Node(val) {
this.val = val;
this.next = null;
}
let head = new Node(0);
let node1 = new Node(1);
let node2 = new Node(2);
head.next = node1;
node1.next = node2;이중 연결리스트 구현
function Node(val) {
this.val = val;
this.next = null;
this.prev = null;
}
let head = new Node(0);
let node1 = new Node(1);
let node2 = new Node(2);
head.next = node1;
node1.next = node2;
node1.prev = head;
node2.prev = node1;