연결 리스트 (Linked List)

연결 리스트는 각 데이터 조각(노드)이 포인터(참조) 를 통해 다음 데이터 조각을 가리키는 방식으로 연결된 선형 자료구조이다.

• 데이터가 메모리상에 연속적으로 배치되지 않는다.
• 각 노드는 데이터(data) 와 다음 노드를 가리키는 참조(next) 로 구성된다.

기차의 각 칸이 다음 칸과 연결된 모습에 비유할 수 있다.
각 칸(노드)는 승객(데이터)를 태우고, 다음 칸을 연결하는 고리(포인터)를 가지고 있다.

🔗 Linked List 개념 설명 영상
🔗 Linked List 단방향/양방향 개념 설명 영상

왜 연결 리스트를 사용하는가?

배열(Array) 은 데이터를 연속된 메모리 공간에 저장하는 효율적인 방법이지만, 구조적인 특성상 두 가지 명확한 한계를 가진다.

• 고정된 크기와 메모리 낭비: 배열은 선언 시점에 사용할 메모리 크기를 미리 정해야 한다. (C/C++ 등)
  JavaScript나 Python 같은 언어는 동적 배열로 자동으로 크기를 조절해주지만, 이 과정에서도 내부적으로는 새로운 큰 배열을 만들고 복사하는 비용이 발생한다.

마치 고정된 좌석 수의 버스 와 같아서 만석이 되면 더 이상 앉을 자리가 없다.

• 삽입/삭제: 중간에 데이터 하나를 끼워 넣거나 빼려면, 그 뒤의 모든 데이터들을 한 칸씩 밀거나 당겨야 한다.

이러한 배열의 단점을 보완할 때 연결 리스트(Linked List) 를 사용한다.

단방향 연결 리스트 (Singly Linked List)

단방향 연결 리스트는 가장 기본적인 형태의 연결 리스트이다.
각 노드는 데이터와 함께 '다음(next)' 노드가 어디 있는지만을 기억한다.

• 구조: [ 데이터 | next ] -> [ 데이터 | next ] -> null

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

let head = new Node(10); // 첫 번째 노드 (head)
let second = new Node(20); // 두 번째 노드
let third = new Node(30); // 세 번째 노드

// 10 -> 20
head.next = second;

// 20 -> 30
second.next = third;

// 현재 상황
// [ 10 | next ] -> [ 20 | next ] -> [ 30 | null ]

let currentNode = head;

while (currentNode !== null) {
  // 현재 노드 데이터 출력
  process.stdout.write(currentNode.data + ' -> ');
  // 다음 노드로 이동
  currentNode = currentNode.next;
}

// 10 -> 20 -> 30 -> null
console.log(currentNode);

양방향 연결 리스트 (Doubly Linked List)

양방향 연결 리스트는 각 노드가 다음(next) 노드 뿐만 아니라 이전(prev) 노드까지 양쪽을 모두 가리킨다.

• 구조: null <- [ prev | 데이터 | next ] <-> [ prev | 데이터 | next ] -> null

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

let head = new Node(10); // 첫 번째 노드 (head)
let second = new Node(20); // 두 번째 노드
let third = new Node(30); // 세 번째 노드

// 10 <-> 20
head.next = second;
second.prev = head;

// 20 <-> 30
second.next = third;
third.prev = second;

// 현재 상황
// null <- [ 10 ] <-> [ 20 ] <-> [ 30 ] -> null

//순회하며 출력하기 (앞으로)
let currentNode = head;
while (currentNode !== null) {
  process.stdout.write(currentNode.data + ' <-> ');
  currentNode = currentNode.next;
}

// 출력 결과: 10 <-> 20 <-> 30 <-> null
console.log('null');

// 순회하며 출력하기 (뒤로) - 마지막 노드부터 시작
let lastNode = third;
while (lastNode !== null) {
  process.stdout.write(lastNode.data + ' <-> ');
  // 이전 노드로 이동
  lastNode = lastNode.prev;
}

// 출력 결과: 30 <-> 20 <-> 10 <-> null
console.log('null');