연결 리스트 (Linked List)

연결 리스트는 여러 개의 데이터를 순서대로 저장하는 자료구조이다.

배열처럼 데이터를 순서대로 다룰 수 있지만,
메모리상에 데이터를 연속적으로 저장하지 않고 각 데이터를 서로 연결해서 관리한다.

연결 리스트란?

연결 리스트는 데이터와 다음 데이터의 위치 정보를 함께 저장하는 자료구조이다.

연결 리스트에서 각각의 데이터를 노드(Node)라고 한다.

노드 = 데이터 값 + 다음 노드를 가리키는 참조

• 하나의 노드는 데이터를 담는 변수와 다음 노드를 가리키는 변수를 가진다.

연결 리스트의 구조

연결 리스트는 첫 번째 노드의 주소만 알고 있으면 다른 모든 노드에 접근할 수 있다.

첫 번째 노드를 보통 head라고 부른다.

head
↓
[10 | next] → [20 | next] → [30 | null]

head에서 시작해 각 노드의 next를 따라가면 다음 노드로 이동할 수 있다.

head → 10 → 20 → 30 → null

즉, 연결 리스트는 첫 번째 노드부터 차례대로 연결을 따라가며 데이터를 확인한다.

연결 리스트 순회하기

연결 리스트는 배열처럼 인덱스로 바로 접근할 수 없다.
따라서 첫 번째 노드부터 next를 따라가며 순서대로 확인해야 한다.

let current = node1;

while (current !== null) {
  console.log(current.data);
  current = current.next;
}
// 10;
// 20;
// 30;

위 코드는 현재 노드의 값을 출력한 뒤,
current를 다음 노드로 이동시키며 모든 노드를 확인한다.

연결 리스트의 모든 노드를 확인해야 하므로 전체 순회의 시간 복잡도는 O(n)이다.

배열과 연결 리스트 비교

배열과 연결 리스트는 모두 여러 데이터를 순서대로 저장할 수 있지만,
데이터를 저장하고 접근하는 방식이 다르다.

구분	배열	연결 리스트
크기	고정	동적
주소	연속	불연속
데이터 참조	O(1)	O(n)
삽입과 삭제	O(n)	위치를 알고 있으면 O(1), 위치를 찾아야 하면 O(n)

데이터 참조

배열은 인덱스를 사용해 원하는 위치의 데이터에 바로 접근할 수 있다.

const numbers = [10, 20, 30];

console.log(numbers[2]); // 30

배열은 시작 위치와 인덱스를 이용해 값을 바로 찾을 수 있기 때문에 데이터 참조가 O(1)이다.

반면 연결 리스트는 특정 위치에 바로 접근할 수 없다.

head → 10 → 20 → 30 → null

예를 들어 30을 찾으려면 head에서 시작해 10, 20, 30 순서로 이동해야 한다.
따라서 연결 리스트에서 특정 데이터를 참조하거나 찾는 작업은 O(n)이다.

삽입과 삭제

배열은 중간에 데이터를 삽입하거나 삭제하면 뒤에 있는 요소들의 위치를 이동해야 한다.

[10, 20, 30]
↓ 15 삽입
[10, 15, 20, 30]

그래서 배열의 앞이나 중간에서 삽입과 삭제가 일어나면 보통 O(n)의 시간이 걸린다.

반면 연결 리스트는 노드의 연결만 바꾸면 데이터를 삽입하거나 삭제할 수 있다.

[10] → [20] → [30]

10과 20 사이에 15를 추가하려면 다음처럼 연결을 바꾸면 된다.

[10] → [15] → [20] → [30]

이미 삽입할 위치를 알고 있다면 연결만 변경하면 되므로 O(1)에 처리할 수 있다.
하지만 삽입할 위치를 찾기 위해 처음부터 순회해야 한다면, 위치를 찾는 데 O(n)이 걸릴 수 있다.

연결 리스트가 적합한 경우

연결 리스트는 데이터의 삽입과 삭제가 자주 일어나는 경우에 유리할 수 있다.

삽입과 삭제가 자주 일어난다 → 연결 리스트

반대로 특정 위치의 데이터를 자주 참조해야 한다면 배열이 더 유리하다.

참조가 자주 일어난다 → 배열

배열은 인덱스를 이용해 원하는 위치의 데이터에 O(1)로 접근할 수 있지만,
연결 리스트는 첫 번째 노드부터 순서대로 이동해야 하므로 참조에 O(n)이 걸린다.

연결 리스트의 추상 자료형

추상 자료형 (Abstract Data Type, ADT)

추상 자료형은 데이터와 그 데이터에 대해 수행할 수 있는 연산을 정의한 것이다.

즉, 내부 구현 방식보다 “어떤 기능을 제공하는가”에 초점을 둔다.

연결 리스트는 다음과 같은 기능을 제공할 수 있다.

기능	메서드	설명
모든 데이터 출력	printAll()	연결 리스트의 모든 노드를 순서대로 출력한다.
모든 데이터 제거	clear()	연결 리스트를 비운다.
인덱스 삽입	insertAt(index, data)	원하는 위치에 새 데이터를 삽입한다.
마지막 삽입	insertLast(data)	연결 리스트의 마지막에 데이터를 삽입한다.
인덱스 삭제	deleteAt(index)	원하는 위치의 데이터를 삭제한다.
마지막 삭제	deleteLast()	연결 리스트의 마지막 데이터를 삭제한다.
인덱스 읽기	getNodeAt(index)	원하는 위치의 노드를 가져온다.

JavaScript로 연결 리스트 구현하기

Node 클래스

각 노드는 데이터와 다음 노드의 참조를 가진다.

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

• data: 노드가 저장하는 값
• next: 다음 노드를 가리키는 참조

LinkedList 클래스

class LinkedList {
  constructor() {
    this.head = null;
    this.count = 0;
  }

  printAll() {
    let currentNode = this.head;
    let text = "[";

    while (currentNode !== null) {
      text += currentNode.data;
      currentNode = currentNode.next;

      if (currentNode !== null) {
        text += ", ";
      }
    }
    text += "]";
    console.log(text);
  }

  clear() {
    this.head = null;
    this.count = 0;
  }

  insertAt(index, data) {
    if (index > this.count || index < 0) {
      throw new Error("범위를 넘어갔습니다.");
    }

    let newNode = new Node(data);

    if (index === 0) {
      newNode.next = this.head;
      this.head = newNode;
    } else {
      let currentNode = this.head;

      for (let i = 0; i < index - 1; i++) {
        currentNode = currentNode.next;
      }
      newNode.next = currentNode.next;
      currentNode.next = newNode;
    }
    this.count++;
  }

  insertLast(data) {
    this.insertAt(this.count, data);
  }

  deleteAt(index) {
    if (index >= this.count || index < 0) {
      throw new Error("제거할 수 없습니다.");
    }

    let currentNode = this.head;

    if (index === 0) {
      let deletedNode = this.head;
      this.head = deletedNode.next;
      this.count--;
      return deletedNode;
    } else {
      for (let i = 0; i < index - 1; i++) {
        currentNode = currentNode.next;
      }

      let deletedNode = currentNode.next;
      currentNode.next = currentNode.next.next;
      this.count--;
      return deletedNode;
    }
  }

  deleteLast() {
    return this.deleteAt(this.count - 1);
  }

  getNodeAt(index) {
    if (index >= this.count || index < 0) {
      throw new Error("범위를 넘어갔습니다.");
    }

    let currentNode = this.head;

    for (let i = 0; i < index; i++) {
      currentNode = currentNode.next;
    }

    return currentNode;
  }
}

기본 노드 연결

let node1 = new Node(1);
let node2 = new Node(2);
let node3 = new Node(3);

node1.next = node2;
node2.next = node3;

console.log(node1.data); // 1
console.log(node1.next.data); // 2
console.log(node1.next.next.data); // 3

insertAt() - 특정 위치에 삽입

let list = new LinkedList();

list.insertAt(0, 0);
list.insertAt(1, 1);
list.insertAt(2, 2);
list.insertAt(3, 3);
list.insertAt(4, 4);
list.printAll(); // [0, 1, 2, 3, 4]

clear() - 모든 데이터 제거

list.clear();
list.printAll(); // []

insertLast() - 마지막에 삽입

list.insertLast(0);
list.insertLast(1);
list.insertLast(2);
list.printAll(); // [0, 1, 2]

deleteAt() - 특정 위치에서 삭제

list.deleteAt(0);
list.printAll(); // [1, 2]

list.deleteAt(1);
list.printAll(); // [1]

deleteLast() - 마지막 노드 삭제

list.insertLast(5);
list.printAll(); // [1, 5]

list.deleteLast();
list.printAll(); // [1]

getNodeAt() - 특정 위치의 노드 조회

list.insertLast(1);
list.insertLast(2);
list.insertLast(3);
list.insertLast(4);
list.insertLast(5);
list.printAll(); // [1, 1, 2, 3, 4, 5]

let secondNode = list.getNodeAt(2);
console.log(secondNode); // Node { data: 2, next: Node { ... } }