Двусвязный список

Всем привет,

Сегодня я буду говорить о структуре данных, называемой двусвязным списком. Прежде чем я начну говорить о двусвязном списке, я настоятельно рекомендую прочитать мой блог в односвязном списке (Щелкните здесь). Это даст вам обзор данных односвязного списка. Что такое двусвязный список? Двусвязный список (указывает на два направления) очень идентичен односвязному списку, за исключением того, что он содержит дополнительный указатель, который отслеживает предыдущий узел. Дважды связанный список имеет два указателя на каждом узле, которые отслеживают предыдущий узел и следующий узел, в отличие от односвязного списка, который отслеживает только следующий узел. Как и в односвязном списке, первый узел в двусвязном списке также называется головкой, а последний узел также называется хвостом. В двусвязном списке каждый узел хранит три вещи: данные (целые или строковые), ссылку на следующий узел и предыдущий узел.

Итак, на картинке выше у нас есть головной узел (A), указывающий на следующий узел (B), а также предыдущий указатель, но там ничего нет, поэтому он NULL. Если мы перейдем к узлу (B), вы увидите, что он указывает на следующий узел (C), а также указывает на предыдущий узел (A).

Теперь давайте реализуем двусвязный список (JavaScript).

Нам нужны два класса: один называется Node, другой - DoublyLinkedList.

• Класс Node будет иметь значение next и prev.
• Класс DoublyLinkedList будет иметь голову, хвост и длину.

class Node {
constructor(val) {
this.val = val;
this.next = null;
this.prev = null;
   }
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
   }
}

На данный момент Двусвязный список сейчас ничего не делает. Давайте напишем метод под названием push, чтобы добавить узел в конец двусвязного списка.

class DoublyLinkedList {
   constructor() {
   this.head = null;
   this.tail = null;
   this.length = 0;
   }
push(val) {
   let newNode = new Node(val);
   if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
   } else {
     this.tail.next = newNode;
     newNode.prev = this.tail
     this.tail = newNode;
   }
   this.length++
   return this;
  }
}

Давайте реализуем метод Pop, чтобы удалить его с конца

class DoublyLinkedList {
   constructor() {
   this.head = null;
   this.tail = null;
   this.length = 0;
   }
push(val) {
   let newNode = new Node(val);
   if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
   } else {
     this.tail.next = newNode;
     newNode.prev = this.tail
     this.tail = newNode;
   }
   this.length++
   return this;
  }
pop() {
   if (!this.head)
       return undefined;
   let currentTail = this.tail;
   if (this.length === 1) {
       this.head = null
       this.tail = null
    } else {
       this.tail = currentTail.prev;
       this.tail.next = null;
       currentTail.prev = null;
    }
     this.length--;
     return currentTail;
  }
}

Следующий метод Shift для удаления из начала двусвязного списка

class DoublyLinkedList {
   constructor() {
   this.head = null;
   this.tail = null;
   this.length = 0;
   }
push(val) {
   let newNode = new Node(val);
   if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
   } else {
     this.tail.next = newNode;
     newNode.prev = this.tail
     this.tail = newNode;
   }
   this.length++
   return this;
  }
pop() {
   if (!this.head)
       return undefined;
   let currentTail = this.tail;
   if (this.length === 1) {
       this.head = null
       this.tail = null
    } else {
       this.tail = currentTail.prev;
       this.tail.next = null;
       currentTail.prev = null;
    }
     this.length--;
     return currentTail;
  }
shift() {
     let oldHead = this.head;
     if (this.length === 0)
          return undefined;
     else if (this.length === 1) {
              this.head = null;
              this.tail = null;
     } else {
              this.head = oldHead.next;
              this.head.prev = null;
              oldHead.next = null;
     }
     this.length--;
     return oldHead;
  }
}

Наконец, метод, который добавляет вперед, называется unshift.

class DoublyLinkedList {
   constructor() {
   this.head = null;
   this.tail = null;
   this.length = 0;
   }
push(val) {
   let newNode = new Node(val);
   if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
   } else {
     this.tail.next = newNode;
     newNode.prev = this.tail
     this.tail = newNode;
   }
   this.length++
   return this;
  }
pop() {
   if (!this.head)
       return undefined;
   let currentTail = this.tail;
   if (this.length === 1) {
       this.head = null
       this.tail = null
    } else {
       this.tail = currentTail.prev;
       this.tail.next = null;
       currentTail.prev = null;
    }
     this.length--;
     return currentTail;
  }
shift() {
     let oldHead = this.head;
     if (this.length === 0)
          return undefined;
     else if (this.length === 1) {
              this.head = null;
              this.tail = null;
     } else {
              this.head = oldHead.next;
              this.head.prev = null;
              oldHead.next = null;
     }
     this.length--;
     return oldHead;
  }
unshift(val) {
       let newNode = new Node(val);
       if (this.length === 0) {
           this.head = newNode;
           this.tail = newNode;
       } else {
           this.head.prev = newNode;
           newNode.next = this.head;
           this.head = newNode;
       }
       this.length++
       return this
   }
}

• Посмотрите мой репозиторий GitHub, чтобы найти код выше ЗДЕСЬ, он также содержит много других методов.
• Gif-анимации ЗДЕСЬ

Вот и все. Надеюсь, вы нашли этот блог полезным. Если у вас возникнут какие-либо трудности или вам нужно больше объяснений, я более чем счастлив помочь вам. Пожалуйста, свяжитесь со мной в LinkedIn или мой адрес электронной почты [email protected].

Удачного кодирования :)

Использованная литература:

Https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass