[자료구조] 연결리스트(Linked List)

이진이·2023년 8월 30일

JavaScript data structure

JavaScript 자료구조

목록 보기

2/6

연결리스트

순서가 있는 데이터들을 저장할 때 그 다음(이전) 순서의 데이터가 있는 주소를 현재 데이터에 포함시키는 방식으로 자료를 저장하는 구조

노드

연결 리스트에서 노드는 데이터와 포인터를 가지는 객체를 의미

포인터 : 다음 노드의 주소
각 포인터 변수의 주소도 따로 존재한다.

장점

필요할 때마다 데이터를 생성하여 연결하면 되기 때문에 메모리 효율 좋음
삭제 및 추가 시 데이터 재구성 용이

단점

탐색 시 느림
(처음 또는 마지막 노드 탐색은 빠름)
구현이 까다롭다
데이터를 저장할 공간 뿐만 아니라 다음 노드의 주소를 저장하는 공간이 추가적으로 필요

사용

자바스크립트에서는 포인터가 없다. 때문에 객체를 참조하는 방식으로 구현

(오히려 더 간단하다)

연결리스트 구현

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;