자바스크립트로 연결리스트(Linked List) 구현하기

연결 리스트란?

배열과 다르게 Node와 Node의 연결을 이용해서 리스트를 만드는 자료구조.

자바스크립트에 익숙한 사람은 원래 배열이라는 자료형에 갯수 제한 없이 원하는 만큼 다 집어넣을 수 있는 줄 아는데

(그것도 자료형에도 구애받지 않고 넣을 수 있는 줄 안다.. 자료형도 정해야 한다. 기본이 any[]가 아니다.)

 

원래 배열은 몇 개까지 수납할지 선언할 때 그 갯수를 한정해야 한다.

이러한 배열의 단점을 보안하기 위해 추가나 삭제가 자유로운 리스트를 만들고 싶은 니즈가 있었는데 이를 구현한게 연결 리스트이다.

 

 

 

기본 구조

 

기본적으로 HEAD와 TAIL 등의 순서가 존재한다. 

Node라는 유닛으로 구성되어 있고, Node는 실제 데이터 값와 다음 데이터의 참조를 가지고 있다.

 

 

아래는 삭제 시의 모습이다. 삭제하는 노드를 사실 delete라던가 이런 예약어로 삭제 안 해줘도 된다.

이전 노드의 next를 이후 노드에 연결만 해주면 된다. 이렇게 연결 고리가 끊기면 GC가 알아서 수거한단다.

 

이렇듯 연결 리스트에 데이터를 추가하려면 Tail에 Node를 계속 추가하면 되고, 중간에 삭제해도 index를 재정렬할 필요도 없다.

 

 

자바스크립트 구현

class로 Node를 구현하고 이를 LinkedList라는 클래스로 엮어준다.

prev와 current를 이용하는 방법, while문으로 특정 인덱스까지 이동하거나, 마지막 인덱스로 이동하는 로직들을 주목할 것.

 

class Node { // 노드 유닛
  constructor(value) {
    this.value = value; // 현재 노드의 값
    this.next = null; // 다음 노드의 참조
  }
}


class LinkedList {
  constructor() {
    this.length = 0; // Array가 아니라 객체로 구현할거라 length를 따로 관리해줘야 한다.
    this.head = null;
  }

  add(value) { // 걊 추가 메소드
    if (this.head) {
      let current = this.head;
      while (current.next) { // current가 계속 있을 때까지 반복
        current = current.next;
      }
      // while문을 탈출한 다음은 next가 null인 상태!
      current.next = new Node(value); // 다음 Node 생성.
    } else { // this.head가 null이면
      this.head = new Node(value); // 생성자 함수로 Node(value)를 할당. 
    }
    this.length++;
    return this.length; // add하면서 길이 늘어나는거 확인하라고 length 반환.
  }

  search(index) { // 탐색 메소드
    return this.#search(index)[1]?.value;
  }
  
  // search 로직. private 메소드로 중복되는 부분을 처리하고 이를 다른 메소드에서 사용한다.
  #search(index) { 
    let count = 0;
    let prev;
    let current = this.head;
    while (count < index) {
      prev = current;
      current = current?.next;
      count++;
    }
    return [prev, current];
  }

  remove(index) { // 값 제거 함수
    const [prev, current] = this.#search(index);
    if (prev && current) {
      prev.next = current.next;
      this.length--;
      return this.length;
    } else if (current) {
      // index가 0일 때,
      this.head = current.next; // current.next는 null일테지만..!
    }
    // 삭제하고자 하는 대상이 없을 때,
    // 아무것도 안 함
  }
}

const ll = new LinkedList(); // LinkedList 사용법

 

 

Super Modern한 자바스크립트 배열이 있는데 굳이 왜 쓰나?

사실 자바스크립트 배열은 아까 말했듯이 추가/삭제 등이 자유로운 모던한 동적 배열이다.

심지어 shift() 메소드를 쓰면 선입선출도 가능하여 Queue구조로도 쓸 수 있다.

중간 부분의 아이템을 들여내는 것도 splice()메소드로 쉽게 할 수 있다.

자바스크립트는 거의 모든 I/O를 이런 슈퍼 모던 배열로 처리하다보니

자바스크립트로 입문한 개발자의 경우, 자료구조 공부를 하면서 초반에 실용성을 못 느끼는 경우가 많다.

 

하지만 자바스크립트 배열도 만능은 아니며, 위에 구현한 연결리스트가 우위를 가지는 부분도 분명 존재한다.

그건 바로, 자바스크립트 배열에서 splice나 shift로 특정 인덱스를 삭제했을 때, 재배열의 시간을 소모한다는 단점이 있다는 것이다.

예를 들어 shift로 맨 첫 인자를 뺐으면 뒤에 있는 인자들은 3 -> 2, 2 -> 1,  1 -> 0 이런 식으로 모두 재배열되어

재배열에만 O(n)의 시간을 쓴다. 즉 엄청나게 많은 인자가 들어있는 채로 Queue처럼 쓰겠다고

막 shift를 하면 매우 성능이 느린 서비스가 될 것이다.

 

이런 면에서 연결 리스트는 어디를 삭제해도 인덱스 재배열에 시간을 투자하지 않는다는 장점이 있다.

노드의 링크를 끊어서 원하는 곳에 붙이기만 하면 된다.