[Javascript] 연결 리스트 구현하기 - 클래스 신택스 대신 프로토타입을 사용하려거든 참조
[자료구조] 연결리스트 with JavaScript - 꼼꼼한 개념설명 및 클래스로 구현을 하려거든 참조.

본 글에서는 jangws님의 [JS 자료구조] 단일 연결 리스트(Singly linked list) [JS]를 참조하여 클래스로 구현하고자 한다.

연결 리스트

연결 리스트는 어떠한 데이터 덩어리(노드)를 다른 데이터 덩어리(노드)와 연결(링크)시키는 자료구조이다.

연결 리스트는 배열에 비해

1. 메모리를 미리 할당하지 않아 메모리 낭비가 적다.
2. 요소의 추가 및 삭제에 대해 O(1)의 시간 복잡도를 가진다.
   (배열은 push, pop은 O(1), 나머지는 O(n)의 시간 복잡도를 가진다.)
3. 메모리 캐싱에 불리하다. 왜 링크드 리스트보다 배열을 기본으로 사용할까 (또한 운영체제가 paging을 이용하여 연속된 데이터를 관리함을 상기해보자.)

단방향으로 연결된 단일 연결 리스트singly linked list, 양방향으로 연결된 이중 연결 리스트doubly linked list가 존재할 수 있겠다.

갓무위키
단일 연결 리스트는 큐를 구현할 때 쓴다
이중 연결 리스트는 단일 연결 리스트에 비해

1. 데이터의 탐색이 자유롭다.-앞, 뒤로 이동이 가능하기 때문에 현실에서 쓰이는 리스트능 주로 이중연결리스트이다.
2. 데이터의 삭제가 비교적 빠르다(무조건 head부터 시작하는 단순 연결 리스트와 달리 tail에서 출발할 수 있다.)
3. 데이터의 보존이 유리하다. (두 노드가 서로를 연결하므로.)
4. 구현이 어렵다. (두 노드가 서로를 연결한다는 것은 하나의 수정사항에 대해 두 노드 모두에 적용시켜야 함을 의미한다.)

원형 리스트 : 단일 연결리스트의 마지막 리스트가 null대신 첫번째 원소를 지시하는 경우를 의미한다. 스트림 버퍼에 쓰인다.

자바스크립트에서 연결 리스트의 성능

스택오버플로우의 한 글에 따르면,
배열은 연결리스트보다 push, pop 연산이 3-5배 빠르다고 한다. 이는 데이터를 캐싱하는 등 배열의 성능 최적화가 이루어져있기 때문일 것이다.
반면, push, shift는 일반적인 환경에서는 약 40% 배열이 느리고, 자료의 양이 많아지면 100%까지 느려진다고 한다. 스택오버플로의 Array.push 대 Array.unshift의 성능 자료들의 인덱스를 교체하는 작업(O(n))을 방지하기 위해 새로운 메모리를 할당하고(새로운 인스턴스를 생성하고) 메모리를 복사한다. 이러한 스와핑의 비용으로 인해 자료가 커질수록 성능이 급격하게 저하되는 요인이 된다.

연결 리스트는 매 연산마다 새로운 인스턴스를 생성하고, 캐싱에 불리하지만, 메모리 스와핑은 일어나지 않는다. 이에 따라 큰 자료에 대한 shift, unshift 연산을 진행할 때에 유리하다. 즉 '큐' 자료구조를 구현하기에는 연결리스트가 유리하다고 할 수 있다.

연결리스트 구현

먼저 연결리스트 추상자료형의 변수를 살펴보자.
변수

1. element : 노드에 저장될 변수이다.
2. next: 다음 노드를 지시하는데 사용되는 변수이다.
3. prev: (이중 연결 리스트에서) 이전 노드를 지시하는데 사용되는 변수이다.
4. head: 연결 리스트의 가장 앞의 노드를 저장하기 위한 변수이다. head가 같은 노드들은 같은 연결리스트에 속한 노드들이다.
   (head에 상대적으로, next가 null인 노드를 tail이라 한다.)

연산은 다양할 수 있으나, 다음의 연산이 대표적일 수 있다.

1. push : 맨 뒤에 노드를 추가한다.
2. pop : 맨 뒤의 노드를 리스트에서 제거하고 해당 노드를 반환한다.
3. shift : 맨 앞에 노드를 제거한다.
4. unshift : 맨 앞에 노드를 추가한다.
5. get : 특정 위치에 있는 노드 값을 반환한다.
6. insert : 특정 위치에 노드를 삽입한다.
7. remove : 특정 위치의 노드를 제거한다.

단일 연결 리스트 구현

생성자 선언

//단순 연결리스트에 사용될 노드를 정의한다.
//스스로가 저장할 value와 다음 노드를 지시할 next를 가지고 있따.
class Node {
  constructor(val) {
    this.val = val;
    this.next = null;
  }
}

//단순연결리스트를 정의한다.
//가장 앞의 노드를 저장할 head
//가장 끝의 노드를 저장할 tail
//전체 노드의 길이를 저장한다.
class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

연산자

1. push()

  //새로운 노드를 추가하는 연산자이다.
  // 1. val를 갖는 새로운 노드를 생성한다.
  // 2. 해당 노드를 tail의 next에 연결시키고 tail을 갱신한다.
  // 2-1. 이때 만일 연결 리스트에 head가 없다면 해당 노드가 head가 되고, tail도 자기 자신을 지시하도록 한다.
  // 3. 길이를 갱신한다.
  // 4. 연산이 끝난 연결리스트를 반환한다.
  push(val) {
    //(1)
    const newNode = new Node(val);
    if (!this.head) {
      //(2-1)
      this.head = newNode;
      this.tail = this.head;
    } else { 
      //(2)
      this.tail.next = newNode;
      this.tail = newNode;
    }
    //(3)
    this.length++;
    //(4)
    return this;
  }

결과물

const list = new SinglyLinkedList();
list.push("HELLO");
list.push("MARCO");
list.push("GOODBYE");

console.log(list);

SinglyLinkedList {
  head: Node { 
    val: 'HELLO', 
    next: Node { 
      val: 'MARCO', 
      next: [Node] 
    }
  },
  tail: Node { 
    val: 'GOODBYE', 
    next: null 
  },
  length: 3
}

2. pop
   반복문을 이용해 current.next가 null이 될 때까지 이동한다.
   current는 제거될 값, current 이전의 값이 새로 tail이 될 값이다.
   current를 반환한다.

  pop() {
    // head가 없으면 undefined를 반환하고 종료한다.
    if (!this.head) return undefined;

    // newTail이라는 변수를 선언하고, current라는 포인터는 head로 초기화한다.
    let current = this.head;
    let newTail;

    //만일 current가 next 변수를 가지고 있으면,
    while (current.next) {
      //current를 newTail에 저장하고
      newTail = current;
      //current를 이동한다.
      current = current.next;
    }
    //위의 반복문은 결과적으로 tail 직전까지 실행된다.(tail은 next가 null이다.)

    //반복문이 끝나면 newTail을 tail로 만들어준다.
    this.tail = newTail;
    //tail의 next는 null이며,
    //기존 tail의 연결이 끊겼으므로 length가 1 줄어든다.
    this.tail.next = null;
    this.length = this.length - 1;

    // 만일 길이가 0이라면,
    // 연결 리스트에 요소가 없으므로 head와 tail을 모두 null로 수정한다.
    if (this.length === 0) {
      this.head = null;
      this.tail = null;
    }

    // pop된 노드(while문의 마지막에 지시된 current) 반환
    return current;
  }

3. shift
   head를 temp에 임시 저장한다.
   head.next로 변경하고 길이를 1 줄인다.
   temp를 반환한다.

  shift() {
    //head가 없으면 빈리스트로 판단하여 반환
    if (!this.head) return undefined;


    const currentHead = this.head;

    //헤드를 헤드의 다음번 요소로 지정하고 길이를 줄인다.
    this.head = currentHead.next;
    this.length--;

    // 만약 길이가 0이 되면 head는 이미 null이고,
    // tail도 null로 할당한다. 
    if (this.length === 0) {
      this.tail = null;
    }

    //임시 저장해두었던 기존 헤드를 반환한다.
    return currentHead;
  }

4. unshift
   새로운 노드를 생성하고,
   기존 헤드를 새로운 노드의 next로 지정한다.
   새로운 헤드는 this.head로 지정한다.

  unshift(val) {
    const newNode = new Node(val);

    //head가 null이면 현재 노드가 head이자 tail이 되도록 초기화 
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    }


    // 순서 중요!
    // 새 노드의 next를 헤드로
    newNode.next = this.head;
    // 헤드를 새 노드로
    this.head = newNode;
    
    this.length++;
    return this;
  }

5. get
   count라는 변수를 만든다.
   head부터 next로 순차적으로 이동하며 0인 카운트에 1씩 더한다.
   지정된 숫자에 도달하면 해당 노드의 value를 반환한다.

  get(index) {
    if (index < 0 || index >= this.length) {
      return null;
    }

    let counter = 0;
    let current = this.head;
    while (counter !== index) {
      current = current.next;
      counter++;
    }
    return current;
  }

6. insert
   get을 이용하여 삽입될 위치의 이전 노드를 찾는다.
   이전 노드의 next를 새 노드의 next로 지정한다.
   이전 노드의 next는 새 노드로 지정한다.

(만일 찾는 인덱스 값이 0이거나, length와 같다면 unshift나 push를 사용하도록 예외처리한다.)

  insert(index, val) {
    if (index < 0 || index > this.length) return false;
    if (index === this.length) return !!this.push(val);
    if (index === 0) return !!this.unshift(val);

    const newNode = new Node(val);
    const prev = this.get(index - 1);
    const temp = prev.next;
    prev.next = newNode;
    newNode.next = temp;
    this.length++;
    return true;
  }

7. remove
   삭제될 노드의 '이전 인덱스'와 '다음 인덱스'를 찾는다.
   이전 인덱스의 next로 다음 인덱스를 연결하고,
   삭제된 노드를 반환한다.

  remove(index) {
    if (index < 0 || index >= this.length) return undefined;
    if (index === 0) return this.shift();
    if (index === this.length - 1) return this.pop();
    
    const previousNode = this.get(index - 1);
    const removed = previousNode.next;
    previousNode.next = removed.next;
    this.length--;
    return removed;
  }

최종 결과물은 아래와 같다.

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

class SinglyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  push(val) {
    const newNode = new Node(val);
    
    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.length++;
    return this;
  }

  pop() {
    if (!this.head) return undefined;

    let current = this.head;
    let newTail;

    while (current.next) {
      newTail = current;
      current = current.next;
    }

    this.tail = newTail;
    this.tail.next = null;
    this.length = this.length - 1;

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

    return current;
  }

  shift() {
    if (!this.head) return undefined;

    const currentHead = this.head;
    this.head = currentHead.next;
    this.length--;

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

    return currentHead;
  }

  unshift(val) {
    const newNode = new Node(val);

    if (!this.head) {
      this.head = newNode;
      this.tail = this.head;
    }

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

    this.length++;
    return this;
  }

  get(index) {
    if (index < 0 || index >= this.length) {
      return null;
    }

    let counter = 0;
    let current = this.head;
    while (counter !== index) {
      current = current.next;
      counter++;
    }

    return current;
  }

  insert(index, val) {
    if (index < 0 || index > this.length) return false;
    if (index === this.length) return !!this.push(val);
    if (index === 0) return !!this.unshift(val);

    const newNode = new Node(val);

    const prev = this.get(index - 1);
    const temp = prev.next;
    prev.next = newNode;
    newNode.next = temp;

    this.length++;
    return true;
  }

  remove(index) {
    if (index < 0 || index >= this.length) return undefined;
    if (index === 0) return this.shift();
    if (index === this.length - 1) return this.pop();

    const previousNode = this.get(index - 1);
    const removed = previousNode.next;
    previousNode.next = removed.next;

    this.length--;
    return removed;
  }
}

이중 연결 리스트 구현

생성자 선언

단일 연결리스트와 같다. 하지만 노드에 this.prev라는 변수가 추가된 것에 주목하자.

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

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

연산자

1. push
   일반적인 구조는 비슷하지만, prev를 항상 함께 업데이트 해줘야 한다는 점에서 다르다.

  push(val) {
    const newNode = new Node(val);
    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      //this.tail의 next도 업데이트해주고
      this.tail.next = newNode;
      //this.tail.next의 prev도 업데이트해준다
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length++;
    return this;
  }

2. get
   단순 연결리스트는 항상 head부터 탐색을 시작했다.
   하지만 이중 연결리스트는 tail에서부터 탐색을 시작할 수 있다.
   이를 이용해서 탐색을 하면 (시간 복잡도는 O(n)으로 같지만) 연산 시간을 최대 절반까지 줄일 수 있다.

  get(index) {
    if (index < 0 || index >= this.length) return null;
    let count; 
    let current; 
    //인덱스를 길이와 비교하여 더 짧은 방향을 찾는다.
    if (index <= this.length / 2) {
      count = 0;
      current = this.head;
      while (count !== index) {
        current = current.next;
        count++;
      }
    //뒤에서 탐색하는 것이 더 빠르면 뒤에서부터 역순으로 진행한다. (인덱스에 유의!)
    } else {
      count = this.length - 1;
      current = this.tail;
      while (count !== index) {
        current = current.prev;
        count--;
      }
    }
    return current;
  }

3. remove
   앞서 언급했듯 prev와 next를 항상 동시에 관리해야 한다.

  remove(index) {
    if (index < 0 || index > this.length) return undefined;
    if (index === 0) return this.shift();
    if (index === this.length - 1) return this.pop();

    const removedNode = this.get(index);
    removedNode.prev.next = removedNode.next;
    removedNode.next.prev = removedNode.prev;
    /* 위의 두 줄은 아래와 같이 4줄로 표현할 수 있다.
    const prevNodeOfremovedNode = removedNode.prev;
    const nextNodeOfremovedNode = removedNode.next;
    prevNodeOfremovedNode.next = nextNodeOfremovedNode;
    nextNodeOfremovedNode.prev = prevNodeOfremovedNode;
    */

    removedNode.next = null;
    removedNode.prev = null;
    this.length--;
    return removedNode;
  }

4. reverse
   뒤집는 연산이 생각보다 복잡할 수 있다. prev와 next를 동시에 관리해야하기 때문에 임시 변수도 2배가 필요하고, 연산도 2배가 더 필요할 수 있다는 점에 유의하자.

  reverse() {
    let node = this.head;
    this.head = this.tail;
    this.tail = node;

    let next;
    let prev = null;
    for (let i = 0; i < this.length; i++) {
      next = node.next;
      node.next = prev;
      prev = node;
      node = next;
    }

    next = null;
    node = this.head;

    for (let i = 0; i < this.length; i++) {
      prev = node.prev;
      node.prev = next;
      next = node;
      node = prev;
    }
  }

최종 결과는 아래와 같다.

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

class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
  push(val) {
    const newNode = new Node(val);
    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      //this.tail의 next도 업데이트해주고
      this.tail.next = newNode;
      //this.tail.next의 prev도 업데이트해준다
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length += 1;
    return this;
  }

  pop() {
    if (!this.head) return undefined;
    const poppedNode = this.tail;
    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      this.tail = poppedNode.prev;
      this.tail.next = null;
      poppedNode.prev = null;
    }
    this.length += 1;
    return poppedNode;
  }

  shift() {
    if (this.length === 0) return undefined;
    const oldHead = this.head;
    if (this.length === 1) {
      this.head = null;
    } else {
      this.head = oldHead.next;
      this.head.prev = null;
      oldHead.next = null;
    }
    this.length += 1;
    return oldHead;
  }

  unshift(val) {
    const newNode = new Node(val);
    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.head.prev = newNode;
      newNode.next = this.head;
      this.head = newNode;
    }
    this.length += 1;
    return this;
  }

  get(index) {
    if (index < 0 || index >= this.length) return null;
    let count;
    let current;
    if (index <= this.length / 2) {
      count = 0;
      current = this.head;
      while (count !== index) {
        current = current.next;
        count++;
      }
    } else {
      count = this.length - 1;
      current = this.tail;
      while (count !== index) {
        current = current.prev;
        count += 1;
      }
    }
    return current;
  }

  insert(index, val) {
    if (index < 0 || index > this.length) return false;
    if (index === this.length) return !!this.push(val);
    if (index === 0) return !!this.unshift(val);

    const newNode = new Node(val);
    const beforeNode = this.get(index - 1);
    const afterNode = beforeNode.next;

    (beforeNode.next = newNode), (newNode.prev = beforeNode);
    (newNode.next = afterNode), (afterNode.prev = newNode);
    this.length += 1;
    return true;
  }

  remove(index) {
    if (index < 0 || index > this.length) return undefined;
    if (index === 0) return this.shift();
    if (index === this.length - 1) return this.pop();

    const removedNode = this.get(index);
    removedNode.prev.next = removedNode.next;
    removedNode.next.prev = removedNode.prev;

    removedNode.next = null;
    removedNode.prev = null;
    this.length--;
    return removedNode;
  }

  reverse() {
    let node = this.head;
    this.head = this.tail;
    this.tail = node;

    let next;
    let prev = null;
    for (let i = 0; i < this.length; i++) {
      next = node.next;
      node.next = prev;
      prev = node;
      node = next;
    }

    next = null;
    node = this.head;

    for (let i = 0; i < this.length; i++) {
      prev = node.prev;
      node.prev = next;
      next = node;
      node = prev;
    }
  }
}

결과적으로 연결리스트는 get 연산에서 비교적 빠른 연산이 가능하지만,
prev 노드의 존재로 인해 관리가 어렵고 메모리가 많이 든다는 단점이 있다.