자료구조와 알고리즘, 링크드 리스트, Double Linked List

더블 링크드 리스트(Doubly Linked List)는 각 노드가 두 개의 포인터를 가지는 링크드 리스트입니다. 하나는 다음 노드를 가리키고, 다른 하나는 이전 노드를 가리킵니다. 이를 통해 리스트의 양방향 탐색이 가능해집니다.

주요 특징

1. 노드 구조(Node Structure): 각 노드는 data, next, prev 세 가지 속성을 가집니다.
   • data: 노드가 저장하는 데이터
   • next: 다음 노드를 가리키는 포인터
   • prev: 이전 노드를 가리키는 포인터
2. 리스트의 구조(List Structure): 더블 링크드 리스트는 head와 tail 두 개의 포인터를 가집니다.
   • head: 리스트의 첫 번째 노드를 가리킴
   • tail: 리스트의 마지막 노드를 가리킴
3. 양방향 탐색: 양방향으로 탐색이 가능하여, 앞뒤로 이동하며 데이터를 처리할 수 있습니다.

주요 연산

1. 추가 (Insertion):
   • 리스트의 앞에 추가: unshift
   • 리스트의 끝에 추가: push
   • 리스트의 중간에 추가: insert
2. 제거 (Removal):
   • 리스트의 앞에서 제거: shift
   • 리스트의 끝에서 제거: pop
   • 리스트의 중간에서 제거: remove
3. 탐색 (Traversal):
   • 인덱스를 이용한 노드 탐색: get

JavaScript로 구현하기

다음은 더블 링크드 리스트의 간단한 구현입니다.

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

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

  push(data) {
    // Create a new node with the value passed to the function
    // If the head property is null set the head and tail to be the newly created node
    // If not, set the next property on the tail to be that node
    // Set the previous property on the newly created node to be the tail
    // Set the tail to be the newly created node
    // Increment the length
    // Return the Doubly Linked List

    let newNode = new Node(data);

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

      this.tail.next = newNode;
      this.tail = newNode;
      this.tail.prev = currentTail;
    }

    this.length++;

    return this;
  }

  pop() {
    // If there is no head, return undefined
    // Store the current tail in a variable to return later
    // If the length is 1, set the head and tail to be null
    // Update the tail to be previous Node
    // Set the newTail's next to null
    // Decrement the length
    // Return the value removed

    if (!this.head || this.length <= 0) return undefined;
    let currentTail = this.tail;

    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      currentTail.prev.next = null;
      this.tail = currentTail.prev;
      currentTail.prev = null;
    }

    this.length--;
    return currentTail;
  }

  shift() {
    // If length is 0, return undefined
    // Store the current head property in a variable(we'll call it old head)
    // If the length is one > set the head to be null, set the tail to be null
    // Update the head to be the next of the old head
    // Set the head's prev property to null
    // Set the old head's next to null
    // Decrement the length
    // Return old head

    if (this.length === 0) return undefined;
    let currentHead = this.head;

    if (this.length === 1) {
      this.head = null;
      this.tail = null;
    } else {
      let newHead = this.head.next;

      newHead.prev = null;
      currentHead.next = null;

      this.head = newHead;
    }

    this.length--;
    return currentHead;
  }
  unshift(data) {
    // Create a new node with the value passed to the function
    // If the length is 0, Set the head to be the new node and Set the tail to be the new node
    // Other wise
    // Set the prev property on the head of the list to be the new node
    // Set the next property on the new node to be the head property
    // Update the head to be the new node
    // Increment the length
    // Return the list
    let newNode = new Node(data);

    if (this.length === 0) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      newNode.next.prev = newNode;

      this.head = newNode;
    }

    this.length++;
    return this;
  }

  traverse() {
    var current = this.head;
    while (current) {
      console.log('current:', current);
      current = current.next;
    }
  }

  get(index) {
    // If the index is less than 0 or greater or equal to the length, return null
    // If the index is less than or equal to half the length of the list
    // Loop through the list starting from the head and loop towards the middle
    // If the index is greater than half the length of the list
    // Loop through the list starting from the tail and loop towards the middle

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

    let cnt = 0;
    let currentValue = this.head;

    if (index <= Math.floor(this.length / 2)) {
      // from head to tail
      while (cnt !== index) {
        currentValue = currentValue.next;
        cnt++;
      }
    } else {
      // from tail to head
      cnt = this.length - 1;
      currentValue = this.tail;

      while (cnt !== index) {
        currentValue = currentValue.prev;
        cnt--;
      }
    }

    return currentValue;
  }

  set(index, data) {
    // Create a variable which is the result of the 'get' method at the index passed to the function
    // If the get method returns a valid node, set the value of that node to be the value passed to the function
    // Return true

    let currentNode = this.get(index);

    if (currentNode.data) {
      currentNode.data = data;
      return true;
    }

    return false;
  }

  insert(index, data) {
    // If the index is less than zero or greater than or equal to the length, return false
    // If the index is 0, unshift
    // If the index is the same as the length, push
    // Use get method to access the index -1
    // Set the next and prev properties on the correct nodes to link everything together
    if (index < 0 || index > this.length) return false;

    let newNode = new Node(data);

    if (index === 0) {
      this.unshift(newNode);
    } else if (index === this.length) {
      this.push(newNode);
    } else {
      let prevNode = this.get(index - 1);

      newNode.prev = prevNode;
      newNode.next = prevNode.next;
      prevNode.next = newNode;
      prevNode.next.next.prev = newNode;
    }
    this.length++;

    return newNode;
  }

  remove(index) {
    // If the index is less than zero or greater than or equal to the length return undefined
    // If the index is 0, shift
    // If the index is the same as the length-1, pop
    // Use the get method to retrieve the item to be removed
    // Update the next and prev properties to remove the found node from the list
    // Set next and prev to null on the found node
    // Decrement the length;
    // Return the removed node
    if (index < 0 || index > this.length) return false;

    if (index === 0) {
      this.shift();
    } else if (index === this.length - 1) {
      this.pop();
    } else {
      let currentNode = this.get(index);
      let prevNode = currentNode.prev;

      prevNode.next.next.prev = currentNode.prev;
      prevNode.next = currentNode.next;

      currentNode.prev = null;
      currentNode.next = null;

      this.length--;
      return currentNode;
    }
  }
}

Array와의 차이점

1. 메모리 사용: 링크드 리스트는 노드당 추가적인 포인터(next, prev)를 저장해야 하므로 메모리 사용이 배열보다 큽니다.
2. 접근 시간: 배열은 인덱스를 통해 O(1) 시간에 요소에 접근할 수 있지만, 링크드 리스트는 O(n) 시간이 걸립니다.
3. 삽입/삭제 시간: 배열은 중간에 삽입하거나 삭제할 때 O(n) 시간이 걸리지만, 링크드 리스트는 해당 위치를 찾는 시간(O(n)) 외에는 O(1) 시간에 가능합니다.

더블 링크드 리스트는 양방향 탐색이 가능하다는 장점이 있어, 삽입과 삭제가 빈번한 경우 유리합니다. 그러나 배열에 비해 메모리 사용량이 많고, 임의 접근이 느리다는 단점도 있습니다.