データ構造02二重接続リスト|JS

24250 ワード


画像ソース

二重リンクリスト|二重リンクリスト

  • 接続リストとは異なり、ノードは前のノードと次のノードからなる:
  • 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
    ダブルリンクリスト
    Photo by Alain Pham on Unsplash