JavaScript로 연결 리스트 구현하기

이전 노트에서 연결 리스트가 노드 사이의 참조로 순서를 표현하고 삽입과 삭제 시 그 연결을 어떻게 바꾸는지 살펴봤습니다. 이번에는 이 동작들을 메서드로 만들어 JavaScript에서 사용할 수 있는 단일 연결 리스트를 구현해보겠습니다.

메서드	동작
prepend(value)	맨 앞에 값을 추가합니다.
append(value)	맨 뒤에 값을 추가합니다.
toArray()	값을 순서대로 담은 배열을 반환합니다.
get(index)	해당 위치의 값을 반환합니다.
insert(index, value)	해당 위치에 값을 삽입합니다.
remove(index)	해당 위치의 노드를 삭제하고 그 값을 반환합니다.

노드와 리스트 만들기

먼저 값을 담을 Node 클래스를 만듭니다.

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

새 노드는 아직 다른 노드와 연결되지 않았으므로 next를 null로 초기화합니다.

LinkedList는 첫 번째 노드와 마지막 노드, 노드 개수를 관리합니다.

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

리스트가 비어 있으면 head와 tail은 모두 null입니다. 노드가 하나라면 둘은 같은 노드를 가리킵니다. 이후 어떤 연산을 수행하더라도 size는 실제 노드 개수와 같아야 하고 마지막 노드의 next는 null이어야 합니다.

이제 LinkedList 클래스에 메서드를 하나씩 추가해보겠습니다.

맨 앞에 추가하기

prepend는 새 노드를 기존의 첫 번째 노드와 연결한 뒤 head를 바꿉니다.

prepend(value) {
  const newNode = new Node(value);

  newNode.next = this.head;
  this.head = newNode;

  if (this.size === 0) {
    this.tail = newNode;
  }

  this.size += 1;
}

비어 있는 리스트에서는 기존 head가 null이므로 newNode.next도 null이 됩니다. 이때 새 노드는 첫 번째이면서 마지막 노드이기도 하므로 tail도 함께 설정합니다.

맨 뒤에 추가하기

append는 tail 뒤에 새 노드를 연결합니다.

append(value) {
  const newNode = new Node(value);

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

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

리스트가 비어 있으면 연결할 마지막 노드가 없으므로 head에 새 노드를 지정합니다. 노드가 있다면 기존 tail의 next에 새 노드를 연결합니다. 어느 경우든 새 노드가 마지막에 위치하므로 tail 갱신은 분기 밖에서 처리합니다.

순회하며 값 확인하기

노드가 늘어날 때마다 head.next.next처럼 직접 확인하기는 번거롭습니다. 전체 값을 배열로 반환하는 toArray를 추가하면 저장된 값과 순서를 한눈에 확인할 수 있습니다.

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

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

  return values;
}

원하는 위치의 값 읽기

인덱스는 0부터 시작합니다. 원하는 위치의 값을 읽으려면 head에서 출발해 해당 위치까지 이동해야 합니다.

조회에는 해당 위치의 노드가 필요하고 중간 삽입과 삭제에는 바로 앞 노드가 필요합니다. 원하는 위치의 노드를 찾는 과정은 동일함으로 #getNode로 분리해 함께 사용하겠습니다.

#getNode(index) {
  let current = this.head;

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

  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는 인덱스가 0이면 맨 앞에, size와 같으면 맨 뒤에 값을 추가합니다. 이 두 경우에는 앞에서 만든 메서드를 그대로 사용할 수 있습니다.

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 previous = this.#getNode(index - 1);
  const newNode = new Node(value);

  newNode.next = previous.next;
  previous.next = newNode;
  this.size += 1;
}

조회할 때와 달리 삽입은 인덱스 size까지 허용합니다.

중간에 삽입할 때는 바로 앞 노드를 찾은 뒤 연결을 바꿉니다. newNode.next에 기존의 다음 노드를 먼저 저장하고 그다음 previous.next를 새 노드로 바꿔야 나머지 연결을 유지할 수 있습니다.

원하는 위치에서 삭제하기

remove는 첫 번째 노드를 삭제하는 경우와 그 외의 경우로 나눠 구현하겠습니다.

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

  let removedNode;

  if (index === 0) {
    removedNode = this.head;
    this.head = removedNode.next;
  } else {
    const previous = this.#getNode(index - 1);
    removedNode = previous.next;
    previous.next = removedNode.next;

    if (removedNode === this.tail) {
      this.tail = previous;
    }
  }

  this.size -= 1;

  if (this.size === 0) {
    this.tail = null;
  }

  return removedNode.value;
}

첫 번째 노드를 삭제할 때는 head를 다음 노드로 옮깁니다. 그 외에는 앞 노드를 찾아 삭제할 노드를 건너뛰도록 연결합니다.

노드가 둘 이상일 때 마지막 노드를 삭제하면 바로 앞 노드가 새로운 tail이 되고 그 노드의 next는 null이 됩니다.

마지막 남은 노드를 삭제하는 경우에는 head를 다음 노드로 옮기면 null이 됩니다. size도 0이 되므로 tail을 null로 바꿉니다.

전체 코드

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

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

  prepend(value) {
    const newNode = new Node(value);

    newNode.next = this.head;
    this.head = newNode;

    if (this.size === 0) {
      this.tail = newNode;
    }

    this.size += 1;
  }

  append(value) {
    const newNode = new Node(value);

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

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

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

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

    return values;
  }

  #getNode(index) {
    let current = this.head;

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

    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 previous = this.#getNode(index - 1);
    const newNode = new Node(value);

    newNode.next = previous.next;
    previous.next = newNode;
    this.size += 1;
  }

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

    let removedNode;

    if (index === 0) {
      removedNode = this.head;
      this.head = removedNode.next;
    } else {
      const previous = this.#getNode(index - 1);
      removedNode = previous.next;
      previous.next = removedNode.next;

      if (removedNode === this.tail) {
        this.tail = previous;
      }
    }

    this.size -= 1;

    if (this.size === 0) {
      this.tail = null;
    }

    return removedNode.value;
  }
}

구현 후 확인할 점

구현을 마친 뒤에는 값의 순서와 함께 head, tail, size가 올바르게 유지되는지 확인합니다. 리스트가 비면 head와 tail이 모두 null이고 size는 0이어야 합니다. 노드가 하나일 때는 head와 tail이 같은 노드를 가리키고 size는 1이어야 합니다.