더블 링크드 리스트 (Doubly Linked List)

Doubly Linked List 🙂

더블 링크드 리스트(Doubly Linked List)는 기존의 링크드 리스트가 한 방향(Tail 방향)으로만 탐색 가능하던 것을 보완하기 위해 만들어진 자료구조입니다. 더블 링크드 리스트의 노드는 next 외에도 prev라는 것을 멤버 변수로 갖고 있는데, 이 변수의 값을 통해 바로 이전의 노드를 참조할 수 있습니다. 그렇다 해도 결국 리스트 내에 있는 head를 통해 하나씩 순차적으로 접근해야 하기 때문에, 단일 링크드 리스트와 특별하게 다른 부분은 없습니다.

노드 & 리스트 생성

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

class LinkedList {
  // private field
  #head;

  constructor() {
    this.#head = null;
  }
}

Node 클래스에는 이전 노드와 다음 노드를 가리킬 수 있도록 prev와 next가 멤버 변수로 있습니다. 그리고 첫 노드를 가리키는 head는 클래스 내부에서만 사용할 수 있도록 private하게 만들었습니다. 멤버를 private하게 만들면, 외부에서 멤버 변수에 접근하는 것이 불가능해집니다. 이렇게 내부의 멤버를 숨기는 작업을 객체지향에서는 정보 은닉(Information Hiding) 또는 캡슐화(Encapsulation)라 부릅니다.

노드 추가

class LinkedList {
  ...
  append(newNode) {
    if (!this.#head) {
      this.#head = newNode;
    } else {
      let current = this.#head;

      while (current.next !== null) {
        current = current.next;
      }
      newNode.prev = current;
      current.next = newNode;
    }
  }
  ...
}

새로운 노드를 추가하는 것은 단일 링크드 리스트와 동일하게, null이 아닌 노드까지 이동해서 붙이는 식으로 구현할 수 있습니다. 다만 이전 노드도 가리켜야 하므로, prev를 신경 써서 연결해야 합니다. 위 코드는 리스트가 비어 있는 경우와 노드가 하나라도 있는 경우를 나누어 처리했습니다.

노드 제거

class LinkedList {
  ...
  remove(index) {
    let current = this.#head;
    let prev = null;

    while (index-- > 0 && current !== null) {
      prev = current;
      current = current.next;
    }

    if (prev === null) {
      if (current !== null) this.#head = current.next;
      else throw new Error('Empty list!');
    } else {
      if (current !== null) {
        prev.next = current.next;
        if (prev.next !== null) prev.next.prev = prev;
      } else throw new Error('Out of range error!');
    }
  }
  ...
}

노드를 제거하는 remove 메소드는 인덱스를 매개변수로 받기 때문에 범위를 벗어나지 않는지 잘 확인해야 합니다. 그리고 prev 또는 next를 연결할 때, 참조하는 객체가 null인 경우 오류가 발생하므로 이 역시 체크해서 오류가 발생하지 않도록 신경 써야 합니다.

리스트 출력

class LinkedList {
  ...
  print() {
    let current = this.#head;

    while (current !== null) {
      // A → B → C 형태로 출력하도록 구현
      process.stdout.write(`${current.data}`);
      if (current.next !== null) process.stdout.write(` → `);
      else process.stdout.write('\n');

      current = current.next;
    }
  }
  ...
}

리스트를 출력하는 것은 head 노드부터 시작하여, null인 노드를 만나기 전까지 반복하는 식으로 구현하면 됩니다.

리스트 초기화

class LinkedList {
  ...
  clear() {
    while (this.#head !== null) {
      this.remove(0);
    }
  }
  ...
}

리스트 초기화는 모든 노드를 지우는 것이기에 head가 null이 될 때까지, 앞에서부터 노드를 제거하면 됩니다.

리스트 뒤집기

class LinkedList {
  ...
  reverse() {
    let current = this.#head;
    let [prev, next] = [null, null];

    while (current !== null) {
      [next, current.next] = [current.next, prev];
      [prev, current] = [current, next];
    }
    this.#head = prev;
  }
  ...
}

리스트를 뒤집는 작업은 임시 변수만 있으면 간단하게 구현할 수 있습니다. 잘 이해가 되지 않는다면, 위 코드를 보고 종이에 직접 그리면서 순서를 따라가 보시기 바랍니다. 그리고 마지막에 head를 새로운 첫 노드로 바꿔주지 않으면, 여전히 기존의 값 가리키므로 반드시 바꿔야 합니다.

References 📝

본문의 내용은 GeeksforGeeks의 자료구조 튜토리얼을 참고해 작성했습니다 ❤️