Linked List란❓

Linked List는 배열과 달리 메모리상에 index에 의한 물리적 배치를 하지 않고, node를 생성 후 해당 node의 pointer에 의해 다음 node를 연결한다. 이를 통해 Linked List는 데이터 삽입/삭제시 데이터의 구조를 재정렬하지 않아도 된다.

Array List 🆚 Linked List

Untitled

👩‍🦰Array List

Array List는 인덱스를 조회하는데 빠르지만 추가, 삭제 시 모든 노드를 옮겨야 하는 경우가 발생할 수 있음.

🧑‍🦰Linked List

Linked List는 새로운 node를 삽입, 삭제 시 O(1)으로 해결할 수 있음. 단, 특정 노드 검색시 비효율적임.

💡 구현

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가 아니다!

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

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

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