연결리스트 (Linked List)

배열

배열은 프로그래밍에서 가장 기본적이고 많이 사용되는 자료구조이다.

하지만 배열에도 분명한 한계가 있다.

배열의 장단점

배열의 장점

• 빠른 접근 속도: 인덱스를 통한 읽기/쓰기가 O(1)의 시간복잡도를 가진다.
• 메모리의 연속성: 데이터가 연속적으로 저장되어 캐시 효율성이 좋다.

배열의 단점

• 고정된 크기: 배열을 선언할 때 크기를 미리 정해야 하므로, 필요한 크기를 예측하기 어려운 경우 메모리 낭비가 발생할 수 있다.
• 비효율적인 삽입/삭제: 중간에 데이터를 삽입하거나 삭제할 때, 뒤에 있는 모든 요소를 이동시켜야 한다.

 

연결 리스트

연결 리스트(Linked List)는 배열의 단점을 보완하기 위해 만들어진 자료구조이다.

각 요소(노드)가 데이터와 다음 노드를 가리키는 포인터로 구성되어 있어, 메모리상에서 연속적으로 배치될 필요가 없다.

배열 vs 연결 리스트 비교

크기	배열	연결 리스트
주소	고정	동적
데이터 참조	연속	불연속
삽입과 삭제	O(n)	O(1) *삽입/삭제 위치를 알고 있을때의 시간 복잡도

 

단방향 연결 리스트 구현

연결 리스트의 기본 형태인 단방향 연결 리스트를 자바스크립트로 구현해보자.

Node 클래스

연결 리스트의 각 노드를 나타내는 클래스

class Node {
  constructor(data, next = null) {
    this.data = data; // 노드가 저장하는 데이터
    this.next = next; // 다음 노드를 가리키는 포인터
  }
}

LinkedList 클래스

연결 리스트의 전체 구조를 관리하는 클래스

class LinkedList {
  constructor() {
    this.head = null; // 첫 번째 노드를 가리킴
    this.count = 0;   // 리스트의 노드 개수
  }
}

 

주요 메서드

1. insertAt() - 특정 위치에 삽입

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++;
}

 

2. deleteAt() - 특정 위치의 노드 삭제

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

  let currentNode = this.head;

  if (index == 0) {
    // 첫 번째 노드 삭제
    let deletedNode = this.head;
    this.head = this.head.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;
  }
}

 

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

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;
}

 

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

단방향 연결 리스트는 앞에서 뒤로만 이동할 수 있다는 한계가 있다.

양방향 연결 리스트는 이전 노드를 가리키는 포인터를 추가하여 양방향 탐색이 가능하다.

DoublyLinkedList의 Node

class Node {
  constructor(data, next = null, prev = null) {
    this.data = data; // 데이터
    this.next = next; // 다음 노드
    this.prev = prev; // 이전 노드 (추가❗️)
  }
}

 

주요 차이점

양방향 연결리스트는 head뿐만 아니라 tail(마지막 노드)도 관리하며, 노드 간 연결을 양방향으로 유지해야 한다.

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null; // 마지막 노드를 가리킴 (추가❗️)
    this.count = 0;
  }
}

 

삽입 시에는 이전 노드와의 연결로 함께 처리해야 한다.

insertAt(index, data) {
  // ...
  
  // 중간에 삽입하는 경우
  newNode.next = currentNode.next;
  newNode.prev = currentNode;
  currentNode.next = newNode;
  newNode.next.prev = newNode; // 양방향 연결
  
  // ...
}

 

연결 리스트의 활용

연결 리스트는 다음과 같은 상황에서 유용하다.

1. 크기를 예측할 수 없는 데이터: 동적으로 크기가 변하는 데이터를 다룰 때
2. 잦은 삽입/삭제: 중간에 데이터를 자주 추가하거나 제거해야 할 때
3. 스택, 큐 구현: 다른 자료구조의 기반으로 사용

 

연결 리스트는 배열과는 다른 방식으로 데이터를 관리하는 자료구조이다. 각각의 장단점을 이해하고 상황에 맞게 선택하는 것이 중요하다.