JS로 Linked List 구현하기

Linked List란❓

Array List 🆚 Linked List

💡 구현

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

export default class LinkedList {
  constructor() {
    this.head = this.tail = new Node();
    this.size = 0;
  }

  pushFront(data) {
    this.pushAt(this.head, data);
  }

  pushBack(data) {
    this.pushAt(this.tail, data);
  }

  popFront() {
    return this.remove(this.head.next);
  }

  popBack() {
    return this.remove(this.tail);
  }

  pushAt(curNode, data) {
    const newNode = new Node(data);
    const nextNode = curNode.next;

    curNode.next = newNode;
    newNode.prev = curNode;
    newNode.next = nextNode;

    if (nextNode) {
      nextNode.prev = newNode;
    }
    if (curNode === this.tail) {
      this.tail = newNode;
    }
    this.size++;
  }

  remove(curNode) {
    const prevNode = curNode.prev;
    const nextNode = curNode.next;

    prevNode.next = nextNode;

    if (nextNode) {
      nextNode.prev = prevNode;
    }
    if (curNode === this.tail) {
      this.tail = prevNode;
    }
    this.size--;
  }

  clean() {
    while (this.size > 0) {
      this.popBack();
    }
  }

  print() {
    let curNode = this.head.next;
    while (curNode) {
      console.log(curNode);
      curNode = curNode.next;
    }
  }
}

🍒 구현 포인트

index를 찾는건 Linked List가 아니다!

• Linked List는 단점에도 적어놨듯 인덱스를 조회하는 데 효율적이지 않다. 이는 node를 push할 때 파라미터로 index를 받도록 구현하면 안된다는 것을 의미한다.

• Linked List에서 노드를 추가할 땐 index로 찾는 것이 아닌, 뒤에 삽입을 원하는 curNode와 삽입할 data로 찾아야 한다.

• curNode를 기준으로 prevNode와 nextNode를 만들고, data로 newData를 인스턴스로 생성하여 prevNode → curNode → newNode → nextNode의 순서를 갖도록 만든다.

node를 삽입할 때 끝인지, 중간 노드인지를 구별해야 한다!

if (nextNode) {
    nextNode.prev = newNode;
  }
  if (curNode === this.tail) {
    this.tail = newNode;
  }

this.head는 언제나 mock node이다!

• 그렇다면 어떻게 Index를 사용하지 않을 수 있을까?

• 바로 head는 항상 비워두는 것이다.

• 여기서 헷갈린 점은 초기 세팅으로 this.head와 this.tail이 null로 구성된 node로 동일하다는 점이다.

• this.tail은 pushAt시 nextNode가 존재하지 않을 경우 갱신해준다.

• 이때 pushFront와 pushBack도 각각 this.head와 this.tail을 넣어주고 있지만 사실상 같은 의미이다.

next, prev, cur를 컴퓨터에게 알려줘야 한다!

• 이름을 직관적으로 짜다보면 컴퓨터도 해당 키워드를 알고 있는 것처럼 코드를 짜는 경우가 생긴다.

• 예를 들어, A 다음은 B다라고 정의했을 때, B 이전은 A다가 성립하지 않는다는 것이다. 이를 컴퓨터에게 따로 명시를 해야 한다.

• 이처럼 prev, next를 통해 마치 prev는 이전을, next는 다음을 알고 있는 것같지만 실제로 이는 우리가 정의한 변수이기 때문에 prev 다음은 next이고, next의 이전은 prev라는 것을 모두 명시해야 한다.