JavaScript로 이중 연결 리스트 구현하기

이번 노트에서는 양방향으로 이동 가능한 이중 연결 리스트를 구현해보겠습니다.

노드와 리스트 만들기

Node 클래스에 prev를 추가하고 DoublyLinkedList는 이전과 같이 head, tail, size로 구성합니다.

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

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
}

맨 앞에 추가하기

새 노드가 기존 head를 가리키도록 하고, 기존 head의 prev도 새 노드로 연결합니다.

prepend(value) {
  const newNode = new Node(value);
  newNode.next = this.head;

  if (this.head === null) {
    this.tail = newNode;
  } else {
    this.head.prev = newNode;
  }

  this.head = newNode;
  this.size += 1;
}

빈 리스트에서는 새 노드가 첫 번째이면서 마지막 노드이므로 tail도 함께 지정합니다.

맨 뒤에 추가하기

새 노드의 prev에 기존 tail을 저장하고, 기존 tail의 next를 새 노드로 바꿉니다.

append(value) {
  const newNode = new Node(value);
  newNode.prev = this.tail;

  if (this.tail === null) {
    this.head = newNode;
  } else {
    this.tail.next = newNode;
  }

  this.tail = newNode;
  this.size += 1;
}

빈 리스트에서는 head도 새 노드를 가리키게 합니다. 새 노드의 next는 초기값인 null을 유지합니다.

순회하며 값 확인하기

값을 배열로 반환하는 toArray는 이전 리스트 구현과 동일합니다. head에서 시작해 next를 따라갑니다.

toArray() {
  const values = [];
  let current = this.head;

  while (current !== null) {
    values.push(current.value);
    current = current.next;
  }

  return values;
}

원하는 위치의 값 읽기

조회, 삽입, 삭제에 필요한 노드를 찾는 과정은 #getNode로 분리합니다. 앞뒤로 이동할 수 있으므로 인덱스가 앞쪽에 있으면 head에서, 뒤쪽에 있으면 tail에서 탐색을 시작합니다.

#getNode(index) {
  if (index < this.size / 2) {
    let current = this.head;

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

    return current;
  }

  let current = this.tail;

  for (let i = this.size - 1; i > index; i -= 1) {
    current = current.prev;
  }

  return current;
}

get(index) {
  if (!Number.isInteger(index) || index < 0 || index >= this.size) {
    throw new RangeError("Index out of range");
  }

  return this.#getNode(index).value;
}

원하는 위치에 삽입하기

맨 앞과 맨 뒤 삽입은 prepend, append로 처리합니다. 중간에 삽입할 때는 해당 위치의 노드를 찾고, prev로 바로 앞 노드에 접근합니다.

insert(index, value) {
  if (!Number.isInteger(index) || index < 0 || index > this.size) {
    throw new RangeError("Index out of range");
  }

  if (index === 0) {
    this.prepend(value);
    return;
  }

  if (index === this.size) {
    this.append(value);
    return;
  }

  const nextNode = this.#getNode(index);
  const previousNode = nextNode.prev;
  const newNode = new Node(value);

  newNode.prev = previousNode;
  newNode.next = nextNode;
  previousNode.next = newNode;
  nextNode.prev = newNode;
  this.size += 1;
}

새 노드의 prev와 next를 지정한 뒤 앞 노드의 next와 뒤 노드의 prev도 새 노드를 가리키도록 바꿉니다.

맨 앞에서 삭제하기

removeFirst는 head를 다음 노드로 옮기고 새 head의 prev를 null로 바꿉니다.

removeFirst() {
  if (this.size === 0) {
    throw new RangeError("List is empty");
  }

  const removedNode = this.head;
  this.head = removedNode.next;

  if (this.head === null) {
    this.tail = null;
  } else {
    this.head.prev = null;
  }

  this.size -= 1;
  return removedNode.value;
}

노드가 하나뿐이었다면 head가 null이 됩니다. 이때 tail도 null로 바꾸면 size가 0인 빈 리스트가 됩니다.

맨 뒤에서 삭제하기

removeLast는 tail을 이전 노드로 옮기고 새 tail의 next를 null로 바꿉니다.

removeLast() {
  if (this.size === 0) {
    throw new RangeError("List is empty");
  }

  const removedNode = this.tail;
  this.tail = removedNode.prev;

  if (this.tail === null) {
    this.head = null;
  } else {
    this.tail.next = null;
  }

  this.size -= 1;
  return removedNode.value;
}

마지막 남은 노드를 삭제하면 head도 null로 바꿉니다.

원하는 위치에서 삭제하기

첫 번째와 마지막 노드는 removeFirst, removeLast로 삭제합니다. 중간 노드는 삭제 대상을 찾은 뒤 양쪽 연결을 바꿉니다.

remove(index) {
  if (!Number.isInteger(index) || index < 0 || index >= this.size) {
    throw new RangeError("Index out of range");
  }

  if (index === 0) {
    return this.removeFirst();
  }

  if (index === this.size - 1) {
    return this.removeLast();
  }

  const removedNode = this.#getNode(index);

  removedNode.prev.next = removedNode.next;
  removedNode.next.prev = removedNode.prev;
  this.size -= 1;

  return removedNode.value;
}

삭제 대상의 앞 노드와 뒤 노드가 서로를 가리키게 하면 대상이 리스트에서 빠집니다.

전체 코드

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

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  prepend(value) {
    const newNode = new Node(value);
    newNode.next = this.head;

    if (this.head === null) {
      this.tail = newNode;
    } else {
      this.head.prev = newNode;
    }

    this.head = newNode;
    this.size += 1;
  }

  append(value) {
    const newNode = new Node(value);
    newNode.prev = this.tail;

    if (this.tail === null) {
      this.head = newNode;
    } else {
      this.tail.next = newNode;
    }

    this.tail = newNode;
    this.size += 1;
  }

  removeFirst() {
    if (this.size === 0) {
      throw new RangeError("List is empty");
    }

    const removedNode = this.head;
    this.head = removedNode.next;

    if (this.head === null) {
      this.tail = null;
    } else {
      this.head.prev = null;
    }

    this.size -= 1;
    return removedNode.value;
  }

  removeLast() {
    if (this.size === 0) {
      throw new RangeError("List is empty");
    }

    const removedNode = this.tail;
    this.tail = removedNode.prev;

    if (this.tail === null) {
      this.head = null;
    } else {
      this.tail.next = null;
    }

    this.size -= 1;
    return removedNode.value;
  }

  #getNode(index) {
    if (index < this.size / 2) {
      let current = this.head;

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

      return current;
    }

    let current = this.tail;

    for (let i = this.size - 1; i > index; i -= 1) {
      current = current.prev;
    }

    return current;
  }

  get(index) {
    if (!Number.isInteger(index) || index < 0 || index >= this.size) {
      throw new RangeError("Index out of range");
    }

    return this.#getNode(index).value;
  }

  insert(index, value) {
    if (!Number.isInteger(index) || index < 0 || index > this.size) {
      throw new RangeError("Index out of range");
    }

    if (index === 0) {
      this.prepend(value);
      return;
    }

    if (index === this.size) {
      this.append(value);
      return;
    }

    const nextNode = this.#getNode(index);
    const previousNode = nextNode.prev;
    const newNode = new Node(value);

    newNode.prev = previousNode;
    newNode.next = nextNode;
    previousNode.next = newNode;
    nextNode.prev = newNode;
    this.size += 1;
  }

  remove(index) {
    if (!Number.isInteger(index) || index < 0 || index >= this.size) {
      throw new RangeError("Index out of range");
    }

    if (index === 0) {
      return this.removeFirst();
    }

    if (index === this.size - 1) {
      return this.removeLast();
    }

    const removedNode = this.#getNode(index);

    removedNode.prev.next = removedNode.next;
    removedNode.next.prev = removedNode.prev;
    this.size -= 1;

    return removedNode.value;
  }

  toArray() {
    const values = [];
    let current = this.head;

    while (current !== null) {
      values.push(current.value);
      current = current.next;
    }

    return values;
  }
}