Посмотрим, как выглядит вставка узла в начало списка:
class DoublyLinkedListNode {
constructor(value, previous, next) {
this.value = value;
this.previous = previous;
this.next = next;
}
}
class DoublyLinkedList {
head = null;
tail = null;
insertBegin(value) {
if (this.head == null) {
const node = new DoublyLinkedListNode(value, null, null);
this.head = node;
this.tail = node;
} else {
const node = new DoublyLinkedListNode(value, null, this.head);
this.head.previous = node;
this.head = node;
}
}
}
Python
class DoublyLinkedListNode:
def __init__(self, value, previous, next):
self.value = value
self.previous = previous
self.next = next
class DoublyLinkedList:
head = None
tail = None
def insert_begin(self, value):
if self.head is None:
node = DoublyLinkedListNode(
value, None, None
)
self.head = node
self.tail = node
else:
node = DoublyLinkedListNode(
value, None, self.head
)
self.head.previous = node
self.head = node
PHP
<?php
class DoublyLinkedListNode
{
public function __construct($value, $previous, $next)
{
$this->value = $value;
$this->previous = $previous;
$this->next = $next;
}
}
class DoublyLinkedList
{
public $head = null;
public $tail = null;
public function insertBegin($value)
{
if ($this->head == null) {
$node = new DoublyLinkedListNode($value, null, null);
$this->head = $node;
$this->tail = $node;
} else {
$node = new DoublyLinkedListNode($value, null, $this->head);
$this->head->previous = $node;
$this->head = $node;
}
}
}
Java
class DoublyLinkedListNode {
Object value;
DoublyLinkedListNode previous;
DoublyLinkedListNode next;
DoublyLinkedListNode(Object value, DoublyLinkedListNode previous, DoublyLinkedListNode next) {
this.value = value;
this.previous = previous;
this.next = next;
}
}
class DoublyLinkedList {
DoublyLinkedListNode head = null;
DoublyLinkedListNode tail = null;
public void insertBegin(Object value) {
if (head == null) {
var node = new DoublyLinkedListNode(value, null, null);
head = node;
tail = node;
} else {
var node = new DoublyLinkedListNode(value, null, head);
head.previous = node;
head = node;
}
}
}
Разберем этот фрагмент кода подробнее.
Двусвязный список, как и односвязный, требует определения двух классов:
Первый класс — DoublyLinkedListNode
. Он описывает узел двусвязного списка и состоит из таких компонентов:
Второй класс — DoublyLinkedList
. Он представляет список целиком, вместе с его операциями-алгоритмами. Там находятся:
-
Ссылка на первый узел — head
-
Ссылка на последний узел — tail
-
Различные методы, например:
-
insertBegin(value)
— вставка в начало
-
insertEnd(value)
— вставка в конец
-
removeBegin()
— удаление из начала
Новый список пуст, поэтому поля head
и tail
содержат значение null
:
После вставки первого узла head
и tail
содержат его адрес. При этом поля previous
и next
у этого узла никуда не указывают, потому что он одновременно является первым и последним в списке — другими словами, у него нет ни предыдущего, ни следующего узла:
Теперь посмотрим на фрагмент кода:
if (this.head == null) {
const node = new DoublyLinkedListNode(value, null, null);
this.head = node;
this.tail = node;
}
Python
if self.head is None:
node = DoublyLinkedListNode(
value, None, None
)
self.head = node
self.tail = node
PHP
<?php
if ($this->head == null) {
$node = new DoublyLinkedListNode($value, null, null);
$this->head = $node;
$this->tail = $node;
}
Java
if (head == null) {
var node = new DoublyLinkedListNode(value, null, null);
head = node;
tail = node;
}
Условие this.head == null
выполняется для пустого списка. Нам достаточно создать узел с пустыми ссылками на предыдущий и следующий узлы, а затем присвоить его адрес полям this.head
и this.tail
.
При вставке каждого следующего узла в начало, head
всегда будет указывать на новый узел. Значение tail
при этом не изменится, потому что хвост списка остается прежним. Поле next
новой головы списка будет указывать на прежнюю голову, а в поле previous
старой головы вместо null должен появиться адрес новой головы:
Это довольно сложная логика, которая требует аккуратной реализации и проверки граничных условий. Поэтому код методов двусвязного списка сложнее, чем код методов односвязного. Посмотрите на этот пример:
const node = new DoublyLinkedListNode(value, null, this.head);
Python
node = DoublyLinkedListNode(value, None, self.head)
PHP
<?php
$node = new DoublyLinkedListNode($value, null, $this->head);
Java
var node = new DoublyLinkedListNode(value, null, head);
Создавая узел, мы сразу записываем в поле next
текущее значение this.head
— текущую голову. Поле previous
текущей головы должно ссылать на новый узел, за это отвечает такая строка:
this.head.previous = node;
Python
self.head.previous = node
PHP
<?php
$this->head->previous = $node;
Java
Наконец, новый узел становится новой головой списка:
Python
PHP
<?php
$this->head= $node;
Java