CS[DataStructure].push('LinkedList')

LinkedList란

next와 value를 갖고 있는 노드로 연결하여 리스트를 만든 것이다.

JS에서는 배열 이라는 메모리관리가 필요없는 자료구조가 있기 때문에 생각 안해도 되겠다 싶지만
배열이 없다고 생각하고 공부를 해야 자료구조를 배울 수 있다.

컴퓨터에서 데이터를 저장할 때 메모리에 순차적으로 저장한다. 예를 들어
1,2,3,4,5,6,7을 저장하고 다른 걸 또 해서 a를 넣고 다시 돌아와서 8을 넣는다고 하면
메모리 상으로는 7 다음 값이 a이고 그 다음 값이 8 이 된다.

바로 옆만 탐색하면 되던게 바뀌게 되었다. 어떻게 해결해야 할까?

다음 값을 함께 저장해줘서 다음 값을 주소값 삼아서 이동해서 찾으면 된다.
이러한 리스트를 연결 리스트 (Linked List)라고 한다.

[a1][ 1, next: b2] > [b2][ 2, next: v2] > [v2][ 3 next: f1] > ...

이런 식으로 데이터를 한번에 저장하여 CRUD 할 수 있게 된다.

JS로 연결리스트 종류중 하나인 원형 연결리스트와 이중 연결리스트의 시스템을 합친 원형 이중 연결리스트(Doubly Circular LinkedList)를 구현해보자.

class LinkedList {
  length = 0;
  head = null;
  tail = null;

  //create 무조건 맨 뒤에 넣기 때문에 tail의 값을 갱신해야 한다.
  add(value) {
    if (this.head) {
      let node = new Node(value);
      this.tail.next = node;
      node.prev = this.tail;
      this.tail = node;
      this.tail.next = this.head;
      this.head.prev = this.tail;
    } else {
      let node = new Node(value);
      this.head = node;
      this.tail = node;
      this.head.prev = this.tail;
      this.head.next = this.tail;
      this.tail.prev = this.head;
      this.tail.next = this.head;
    }
    return ++this.length;
  }

  //private method 
  //search와 remove을 한번에 처리하기 위해서 존재하는 private method. 탐색만 한다고 보면 된다.
  #prevCurrent(index) {
    let count = 0;
    let prev;
    let current = this.head;
    if (index >= this.length || index < 0) {
      return [undefined, null];
    }
    while (count < index) {
      prev = current;
      current = current?.next;
      count++;
    }
    return [prev, current];
  }

  //search
  // optional chaining을 사용해서 null 예외 처리를 해주며 private method를 그대로 써준다.
  search(index) {
    return this.#prevCurrent(index)[1]?.value;
  }

  //Delete
  //tail과 head를 생각해서 삭제해야 한다. head을 지운경우, tail을 지운 경우 그 사이를 지운 경우를 생각하여 구현
  remove(index) {
    const [prev, current] = this.#prevCurrent(index);
    if (prev !== undefined && current !== null) {
      prev.next = current.next;
      current.next.prev = prev;
      if (current.next === this.head) {
        this.tail = prev;
      }
      return --this.length;
    } else if (current !== null) {
      this.head = current.next;
      this.tail.next = this.head;
      this.head.prev = this.tail;
      return --this.length;
    }
  }

  getLength() {
    return this.length;
  }
}

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

const ll = new LinkedList();
console.log(ll.getLength());
console.log(ll.add(1));
console.log(ll.add(2));
console.log(ll.add(3));
console.log(ll.search(2));
console.log(ll.remove(0));
console.log(ll.search(1));
console.log(ll.getLength());

Reference

인프런 - 비전공자의 전공자 따라잡기 (제로초)
C언어로 쉽게 풀어쓴 자료구조 - 천인국,공용해,하상호