자료구조 02 이중 연결 리스트 | JS

이미지 출처

이중 연결 리스트 | Doubly Linked List

• 연결리스트와 다르게 노드가 이전 노드와 다음 노드로 구성됨
• node: prev + data + next
• 양방향으로 연결되어 있기 때문에 노드를 탐색하는 방향이 양쪽으로 가능함
• prev를 설정하기 위한 메모리가 더 쓰인다는 단점

prepend: 새 노드를 Head로 붙임
append: Tail 뒤에 덧붙임
delete: 삭제
find: 탐색
deleteTail: Tail 삭제
deleteHead: head 삭제

export default class DoublyLinkedListNode {
  constructor(value, next = null, prev = null) {
    this.value = value;
    this.next = next;
    this.prev = previous;
  }

  toString(callback) {
    return callback ? callback(this.value) : `${this.value}`;
  }
}

import DoublyLinkedListNode from './DoublyLinkedListNode';

export default class DoublyLinkedList {
  constructor(comparatorFunction) {
    this.head = null;
    this.tail = null;
  }

  // 새 노드를 Head로 붙임
  prepend(value) {
    const newNode = new DoublyLinkedListNode(value, this.head);

    // 이미 head가 있으면 head의 prev를 새 노드로 설정
    // head를 새 노드로 설정
    if (this.head) {
      this.head.prev = newNode;
    }
    this.head = newNode;

    // tail이 업승ㄹ 경우, 새 노드를 tail로 설정
    if (!this.tail) {
      this.tail = newNode;
    }

    return this;
  }

  // Tail 뒤에 덧붙임
  append(value) {
    const newNode = new DoublyLinkedListNode(value);

    // head가 없으면(노드가 없으면) 새 노드를 head와 tail로 설정
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;

      return this;
    }

    // 새 노드를 tail의 다음에 설정
    this.tail.next = newNode;

    // 새 노드의 prev에 tail을 설정
    newNode.prev = this.tail;

    // 새 노드를 tail로 설정
    this.tail = newNode;

    return this;
  }
  
  // 삭제
  delete(value) {
    if (!this.head) {
      return null;
    }

    let deletedNode = null;
    let currentNode = this.head;

    while (currentNode) {
      if (currentNode.value === value)) {
        // deletedNode 설정
        deletedNode = currentNode;        
        if (deletedNode === this.head) {
          // head가 삭제될 예정이라면
          // 두번째 노드를 head로 설정
          this.head = deletedNode.next;

          // 새로운 head의 prev를 null로 설정
          if (this.head) {
            this.head.prev = null;
          }

          // 목록에 있는 모든 노드의 값이 인수로 전달된 값과 동일하면
          // 모든 노드가 삭제되므로 tail을 업데이트함
          if (deletedNode === this.tail) {
            this.tail = null;
          }
        } else if (deletedNode === this.tail) {
          // tail이 삭제될 예정이라면
          // 뒤에서 두번째 노드를 tail로 설정
          this.tail = deletedNode.prev;
          this.tail.next = null;
        } else {
          // 삭제할 노드가 head도 tail도 아닌 경우
          const prevNode = deletedNode.prev;
          const nextNode = deletedNode.next;

          prevNode.next = nextNode;
          nextNode.prev = prevNode;
        }
      }

      currentNode = currentNode.next;
    }

    return deletedNode;
  }

  // 탐색
  find({ value = undefined, callback = undefined }) {
    if (!this.head) {
      return null;
    }

    let currentNode = this.head;

    while (currentNode) {
      // If callback is specified then try to find node by callback.
      if (callback && callback(currentNode.value)) {
        return currentNode;
      }

      // If value is specified then try to compare by value..
      if (value !== undefined && (currentNode.value === value)) {
        return currentNode;
      }

      currentNode = currentNode.next;
    }

    return null;
  }

  // tail 삭제
  deleteTail() {
    if (!this.tail) {
      return null;
    }

    if (this.head === this.tail) {
      // 단 하나의 노드만 있는 경우
      const deletedTail = this.tail;
      this.head = null;
      this.tail = null;

      return deletedTail;
    }

    const deletedTail = this.tail;

    this.tail = this.tail.prev;
    this.tail.next = null;

    return deletedTail;
  }
  
  // head 삭제
  deleteHead() {
    if (!this.head) {
      return null;
    }

    const deletedHead = this.head;

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

    return deletedHead;
  }
}

📚 참고

Github | tech-interview-for-developer
Github | Interview_Question_for_Beginner
Github | javascript-algorithms | trekhleb
Doubly linked list (이중 연결 리스트)

Photo by Alain Pham on Unsplash