단일 링크드 리스트 (Singly Linked List)

Singly Linked List 🙂

많은 데이터를 담기 위해서는 배열(Array)을 사용합니다. 그런데 배열은 간단하지만, 데이터를 담을 수 있는 사이즈에 제약이 있습니다. 자바스크립트에서의 배열은 메모리가 허용하는 한 사이즈가 무한하지만, C나 Java 같은 언어에서는 배열을 만들 때 정적으로 초기 사이즈를 결정한 후 사용해야 합니다. 그렇기 때문에 사이즈를 넘어서는 만큼의 데이터는 넣을 수 없다는 문제가 있습니다.

그래서 고안된 것이 링크드 리스트(Linked List)라 하는 선형(Linear) 자료구조입니다. 각 요소는 노드라는 것으로 표현하고, 노드들을 하나하나 연결해 놓은 것이 바로 링크드 리스트입니다. 요소를 추가할 때마다 새로운 노드를 만들어 연결하면 되기 때문에, 사이즈를 걱정할 필요가 없어졌습니다.

장점

• 배열과 달리 사이즈를 동적으로 늘리거나 줄일 수 있다.

단점

• 요소 접근을 순차적으로 해야 하므로 배열보다 속도가 느리다.
• 배열에 비해 구현이 비교적 복잡하다.

노드 생성

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

링크드 리스트를 만들기 전에, 데이터를 담을 수 있는 공간인 노드를 만들어야 합니다. 노드는 데이터를 담기 위한 data와 다음 노드를 가리키기 위한 next를 멤버로 갖고 있습니다. next의 값은 링크드 리스트에서 노드를 추가하는 과정 중에 결정되기 때문에, 노드를 생성하는 단계에서는 null로 초기화하면 됩니다.

리스트 생성

class LinkedList {
  // Private field
  #head;

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

const list = new LinkedList();

링크드 리스트는 위와 같이 클래스로 간단하게 만들면 되고, 필요한 기능을 메소드로 하나씩 구현해 나가면 됩니다. 그리고 head라고 하는 멤버 변수는 가장 처음 추가된 노드(맨 앞)를 저장해 두는 일종의 임시 변수입니다. 이 변수를 통해 노드를 차례대로 순회할 수 있습니다. 노드들이 서로 next로 연결되어 있기 때문에, 가장 처음이 되는 노드를 head에 저장해 두고 사용하는 것입니다.

노드 추가

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

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

const list = new LinkedList();

list.append(new Node('A'));
list.append(new Node('B'));
list.append(new Node('C'));

리스트에 새로운 노드를 추가하는 과정은 간단합니다. 리스트의 head가 null이라면, 리스트가 비어 있는 것이기 때문에, head에 새로 추가할 노드만 할당하면 끝입니다. 반대로 head가 null이 아니라면, 리스트에 노드가 하나 이상 있는 것이기 때문에, next의 값이 null인 노드를 반복문을 통해 찾은 후 연결하면 됩니다.

노드 제거 

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;
    else throw new Error('Out of range error!');
  }
}

노드의 위치를 매개변수로 받아 제거할 때는 index의 값이 리스트 내에서 유효한 지 매 순간 체크해야 합니다. 저는 여러 상황(리스트가 비어 있을 때, 인덱스를 넘어갔을 때 등)에 대한 예외 처리를 했으며, 배열과 동일하게 첫 번째 노드를 인덱스 0이라 가정하고 구현했습니다.

리스트 출력

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

리스트의 노드를 확인할 때는 현재 참조하고 있는 노드가 null이 아닐 때까지 반복하면서 출력하면 됩니다.

리스트 초기화

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

리스트를 초기화하는 방법은 위에서 만들었던 remove 메소드를 연속 호출함으로써 구현 가능합니다.

리스트 뒤집기

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

리스트를 뒤집는 방법은 사실 기본적인 기능은 아닌데, 가끔 이를 구현해 보라는 문제가 종종 있어서 추가로 소개합니다. 리스트를 뒤집을 때는 세 가지 변수(prev, next, current)를 사용하면 정말 간단하게 구현할 수 있습니다. 한 번 노트에 리스트를 그려본 다음, 위 코드를 단계별로 적용해 보면서 변화를 확인하면 이해하시기 쉬울 것 같습니다.

References 📝

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