====== Двусвязный список — Основы алгоритмов и структур данных ======

Вы уже знакомы с односвязным списком. Эта структура данных позволяет быстро вставлять и удалять элементы. Звучит удобно, но такой подход работает не во всех случаях. В этом уроке вы познакомитесь с двусвязным списком, который лучше подходит для некоторых типичных задач в программировании.

Есть несколько задач, для которых односвязный список подходит не очень хорошо. В частности, он несимметричен — если вставка и удаление в начале списка выполняются за константное время   , то в конце — за линейное   . Если в списке будет тысяча элементов, вставка в начало может оказаться в тысячу раз быстрее, чем вставка в конец.

Другая задача, которую трудно решить с помощью односвязного списка — вставка перед заданным узлом. Предположим, у нас есть текст на русском языке, где каждый элемент — либо отдельное слово, либо знак препинания. В тексте могут быть ошибки: например, могут отсутствовать запятые и точки. Мы предполагаем, что если слово начинается с большой буквы, перед ним должна быть точка. Если в тексте есть союзы «но» и «а», перед ними должна стоять запятая.

Расссмотрим такой пример:

<code>
«Его» «пример» «другим» «наука» «но» «,» «боже» «мой» «,» «какая» «скука» «с» «больным» «сидеть» «и» «день» «и» «ночь» «,» «не» «отходя» «ни» «шагу» «прочь» «Какое» «низкое» «коварство» «полуживого» «забавлять» «ему» «подушки» «поправлять» «,» «печально» «подносить» «лекарство»
</code>

В этом тексте не хватает запятой перед словом «но» и точки перед словом «Какое». Попробуем решить эту задачу с помощью односвязного списка. Нам нужно:

  * Поместить слова в односвязный список 
  * Найти слово «но» 
  * Попробовать вставить перед ним запятую 

Здесь мы сталкиваемся с тем, что в узле нет ссылки на предыдущий элемент, только на следующий:

{{ :basics_of_algorithms:image_processing20231016-36-aaemuz.png?600 |}}

Односвязный список устроен так, что для вставки запятой между словами «наука» и «но» нужно модифицировать именно узел со словом «наука». Эти детали делают наш возможный алгоритм сложным и медленным.

Для подобных задач лучше использовать списки, в котором хранятся обе ссылки.

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

В каждом узле двусвязного списка хранится две ссылки — на следующий и на предыдущий узел. Кроме того, в нем хранятся ссылки и на голову списка (первый элемент), и на его хвост (последний элемент):

{{ :basics_of_algorithms:image_processing20231016-27-u0327f.png?600 |}}

Как и в случае с односвязным списком, нам приходится особым образом хранить ссылку на следующий узел для последнего узла. Там мы помещаем значение <color red>null</color> — пустую ссылку, которая ни на что не указывает. На рисунке последний узел в списке — это D.

У первого узла не может быть предыдущего узла, поэтому и здесь мы записываем <color red>null</color> вместо ссылки. На рисунке первый узел в списке — это A.

За счет изменения структуры, мы получаем две новые возможности:

  * Вставка и удаление в конце списка становятся настолько же быстрыми, как и в начале. Теперь они выполняются за константное время  
  * Вставка узла перед заданным узлом становится такой же простой операцией, как и вставка после O(1)

Конечно, есть и минусы. Во-первых, сама структура и код становятся сложнее. Во-вторых, структура теперь занимает больше памяти, поскольку в каждом узле хранится две ссылки, а не одна.

===== Вставка узла в начало списка =====

Посмотрим, как выглядит вставка узла в начало списка:

<code javascript>
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;
    }
  }
}
</code>

<details>
<summary>Python</summary>

<code 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
</code>
</details>

<details>
<summary>PHP</summary>

<code 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;
        }
    }
}
</code>
</details>

<details>
<summary>Java</summary>

<code 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;
        }
    }
}
</code>
</details>

Разберем этот фрагмент кода подробнее.

Двусвязный список, как и односвязный, требует определения двух классов:

Первый класс — <color red>DoublyLinkedListNode</color>. Он описывает узел двусвязного списка и состоит из таких компонентов:

  * Значения — <color red>value</color> 
  * Ссылки на предыдущий узел — <color red>previous</color> 
  * Ссылки на следующий узел — <color>next</color>

Второй класс — <color red>DoublyLinkedList</color>. Он представляет список целиком, вместе с его операциями-алгоритмами. Там находятся:

  * Ссылка на первый узел — <color red>head</color>
  * Ссылка на последний узел — <color red>tail</color> 
  * Различные методы, например: 
    * <color red>insertBegin(value)</color> — вставка в начало 
    * <color red>insertEnd(value)</color> — вставка в конец 
    * <color red>removeBegin()</color> — удаление из начала 

Новый список пуст, поэтому поля <color red>head</color> и <color red>tail</color> содержат значение <color red>null</color>:

{{ :basics_of_algorithms:image_processing20231016-24-v3t3k9.png?300 |}}

После вставки первого узла <color red>head</color> и <color red>tail</color> содержат его адрес. При этом поля <color red>previous</color> и <color red>next</color> у этого узла никуда не указывают, потому что он одновременно является первым и последним в списке — другими словами, у него нет ни предыдущего, ни следующего узла:

{{ :basics_of_algorithms:image_processing20231016-39-n7fcvw.png?600 |}}

Теперь посмотрим на фрагмент кода:

<code javascript>
if (this.head == null) {
  const node = new DoublyLinkedListNode(value, null, null);
  this.head = node;
  this.tail = node;
}
</code>

<details>
<summary>Python</summary>

<code python>
if self.head is None:
    node = DoublyLinkedListNode(
        value, None, None
    )
    self.head = node
    self.tail = node
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

if ($this->head == null) {
    $node = new DoublyLinkedListNode($value, null, null);
    $this->head = $node;
    $this->tail = $node;
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
if (head == null) {
    var node = new DoublyLinkedListNode(value, null, null);
    head = node;
    tail = node;
}
</code>
</details>

Условие <color red>this.head == null</color> выполняется для пустого списка. Нам достаточно создать узел с пустыми ссылками на предыдущий и следующий узлы, а затем присвоить его адрес полям <color red>this.head</color> и <color red>this.tail</color>.

При вставке каждого следующего узла в начало, <color red>head</color> всегда будет указывать на новый узел. Значение <color>tail</color> при этом не изменится, потому что хвост списка остается прежним. Поле <color red>next</color> новой головы списка будет указывать на прежнюю голову, а в поле <color red>previous</color> старой головы вместо null должен появиться адрес новой головы:

{{ :basics_of_algorithms:image_processing20231016-39-mkvx9s.png?600 |}}

Это довольно сложная логика, которая требует аккуратной реализации и проверки граничных условий. Поэтому код методов двусвязного списка сложнее, чем код методов односвязного. Посмотрите на этот пример:

<code javascript>
const node = new DoublyLinkedListNode(value, null, this.head);
</code>

<details>
<summary>Python</summary>

<code python>
node = DoublyLinkedListNode(value, None, self.head)
</code>
</details>
<details>
<summary>PHP</summary>

<code php>
<?php

$node = new DoublyLinkedListNode($value, null, $this->head);
</code>
</details>

<details>
<summary>Java</summary>

<code java>
var node = new DoublyLinkedListNode(value, null, head);
</code>
</details>

Создавая узел, мы сразу записываем в поле <color red>next</color> текущее значение <color red>this.head</color>— текущую голову. Поле <color red>previous</color> текущей головы должно ссылать на новый узел, за это отвечает такая строка:

<code javascript>
this.head.previous = node;
</code>

<details>
<summary>Python</summary>

<code python>
self.head.previous = node
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

$this->head->previous = $node;
</code>
</details>

<details>
<summary>Java</summary>

<code java>
head.previous = node;
</code>
</details>

Наконец, новый узел становится новой головой списка:

<code javascript>
this.head = node;
</code>

<details>
<summary>Python</summary>

<code python>
self.head = node
</code>
</details>
<details>
<summary>PHP</summary>

<code php>
<?php

$this->head= $node;
</code>
</details>

<details>
<summary>Java</summary>

<code java>
head = node;
</code>
</details>

===== Вставка узла в конец списка =====

Перейдем к вставке узла в конец списка:

<code javascript>
insertEnd(value) {
  if (this.tail == null) {
    const node = new DoublyLinkedListNode(value, null, null);
    this.tail = node;
    this.head = node;
  } else {
    const node = new DoublyLinkedListNode(value, this.tail, null);
    this.tail.next= node;
    this.tail = node;
  }
}
</code>
<details>
<summary>Python</summary>

<code python>
def insert_end(self, value):
    if self.tail is None:
        node = DoublyLinkedListNode(value, None, None)
        self.tail = node
        self.head = node
    else:
        node = DoublyLinkedListNode(value, self.tail, None)
        self.tail.next = node
        self.tail = node
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

public function insertEnd($value)
{
    if ($this->tail == null) {
        $node = new DoublyLinkedListNode($value, null, null);
        $this->tail = $node;
        $this->head = $node;
    } else {
        $node = new DoublyLinkedListNode($value, $this->tail, null);
        $this->tail->next= $node;
        $this->tail = $node;
    }
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
class DoublyLinkedList {
    // ...

    public void insertEnd(Object value) {
        if (tail == null) {
            var node = new DoublyLinkedListNode(value, null, null);
            tail = node;
            head = node;
        } else {
            var node = new DoublyLinkedListNode(value, tail, null);
            tail.next= node;
            tail = node;
        }
    }
}
</code>
</details>

Такая вставка симметрична вставке в начало. Разница только в том, что здесь мы должны везде менять местами <color red>head</color> и <color red>tail</color>, а также <color red>previous</color> и <color red>next</color>.

===== Удаление узла =====

Перейдем к операциям удаления:

<code javascript>
removeBegin() {
  if (this.head == null) {
    return undefined;
  }

  const result = this.head.value;

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

  return result;
}
</code>

<details>
<summary>Python</summary>

<code python>
def remove_begin(self):
    if self.head is None:
        return None

    result = self.head.value

    if self.head == self.tail:
        self.head = None
        self.tail = None
    else:
      self.head = self.head.next
      self.head.previous = None

    return result
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

public function removeBegin()
{
    if ($this->head == null) {
        return null;
    }

    $result = $this->head->value;

    if ($this->head == $this->tail) {
        $this->head = null;
        $this->tail = null;
    } else {
        $this->head = $this->head->next;
        $this->head->previous = null;
    }

    return $result;
}
</code>
</details>


<details>
<summary>Java</summary>

<code java>
class DoublyLinkedList {
  // ...

    public Object removeBegin() {
        if (head == null) {
            return null;
        }

        var result = head.value;

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

        return result;
    }
}
</code>
</details>

Метод удаления возвращает значение из удаленного узла. Если список пуст и удалять нечего, метод возвращает <color red>undefined</color>. В остальных случаях мы сохраняем значение в переменную <color red>result</color>:

<code javascript>
if (this.head == null) {
  return undefined;
}

const result = this.head.value;
</code>

<details>
<summary>Python</summary>

<code python>
if self.head is None:
    return None

    result = self.head.value
</code>
</details>
<details>
<summary>PHP</summary>

<code php>
<?php

if ($this->head == null) {
    return null;
}

$result = $this->head->value;
</code>
</details>

<details>
<summary>Java</summary>

<code java>
if (head == null) {
    return null;
}

var result = head.value;
</code>
</details>

Если <color red>this.head == this.tail</color>, значит, в списке находится один последний узел — он является одновременно и головой, и хвостом. Чтобы его удалить, достаточно обнулить <color red>head</color> и <color red>tail</color>:

<code javascript>
if (this.head == this.tail) {
  this.head = null;
  this.tail = null;
}
</code>

<details>
<summary>Python</summary>

<code python>
if self.head == self.tail:
    self.head = None
    self.tail = None
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

if ($this->head == $this->tail) {
    $this->head = null;
    $this->tail = null;
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
if (head == tail) {
    head = null;
    tail = null;
}
</code>
</details>

А теперь посмотрим обратный пример — избавимся от первого узла в списке. Сначала записываем в <color red>head</color> ссылку на второй узел, а потом обнуляем у нее поле <color red>previous</color>:

<code javascript>
this.head = this.head.next;
this.head.previous = null;
</code>

<details>
<summary>Python</summary>

<code python>
self.head = self.head.next
self.head.previous = None
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

$this->head = $this->head->next;
$this->head->previous = null;
</code>
</details>

<details>
<summary>Java</summary>

<code java>
head = head.next;
head.previous = null;
</code>
</details>

===== Перебор значений в прямом порядке =====

Раньше для работы с массивами, связными и двусвязными списками, программисты писали разный код. Например, если надо было просуммировать элементы массива и элементы связного списка, приходилось писать две похожие функции. Каждая из них складывала элементы коллекций, но доступ к этим элементам у массива и списка был разным.

Дублирование кода — одна из самых неприятных вещей в программировании. При внесении правок можно забыть поменять код в одной из копий и это приведет к ошибкам, которые трудно обнаружить. Но есть решение этой проблемы: в языках постоянно появляются новые инструменты, которые помогают избавиться от старых ошибок и реже дублировать код.

Чтобы просуммировать элементы из разных структур данных, сейчас достаточно написать всего одну функцию. Это стало возможным благодаря итераторам. Обычно итерацией в программировании называют отдельный шаг цикла. Но у слова есть и другое значение.

**Итератор** — это объект, который одинаковым образом перебирает элементы коллекции, независимо от структуры данных. Скажем, мы можем написать функцию суммирования элементов любой коллекции и вызвать ее для списка:

<code javascript>
const sum = (items) => {
  let result = 0;

  for (item of items) {
    result = result + item;
  }

  return result;
};

console.log(sum([1, 2, 3, 4])); // => 10
</code>

<details>
<summary>Python</summary>

<code python>
def sum(items):
    result = 0
    for item in items:
        result = result + item

    return result

print(sum([1, 2, 3, 4]))  # => 10
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

function sum($items)
{
  $result = 0;

  foreach ($items as $item) {
    $result = $result + $item;
  }

  return $result;
};

print_r(sum([1, 2, 3, 4])); // => 10
</code>
</details>

<details>
<summary>Java</summary>

<code java>
class App {
    public static int sum(Iterable<Integer> items) {
        var result = 0;

        for (var item: items) {
            result = result + (int) item;
        }

        return result;
    }
}

System.out.println(App.sum(List.of(1, 2, 3, 4))); // => 10
</code>
</details>

Эта функция сможет работать и с нашим двусвязным списком, но для этого нам потребуется реализовать собственный итератор.

Однако, здесь есть проблема. Массив и односвязный список имеют естественный порядок перебора — от начала к концу. В двусвязном списке поддерживаются два равноправных порядка:

  * От начала к концу 
  * От конца к началу 

Поэтому двусвязный список должен иметь два итератора — прямой и обратный. Чтобы так сделать, можно возвращать итераторы из методов класса. Например, метод ''fore()'' может создавать и возвращать прямой итератор:

<code javascript>
fore() {
  let iterator = {
    current: this.head
  };

  iterator[Symbol.iterator] = function* () {
    while (this.current != null) {
      yield this.current.value;

      this.current = this.current.next;
    }
  };

  return iterator;
}
</code>

<details>
<summary>Python</summary>

<code python>
def fore(self):
    current = self.head
    while current is not None:
        yield current.value
        current = current.next
</code>
</details>
<details>
<summary>PHP</summary>

<code php>
<?php

public functon fore()
{
    $current = $this->head;

    while($current !== null) {
        yield $current->value
        $current = $current->next
    }
}
</code>
</details>

Использовать итератор можно так:

<code javascript>
let list = new DoublyLinkedList();
list.insertBegin(1);
list.insertBegin(2);
list.insertBegin(3);
list.insertBegin(4);

console.log(sum(list.fore())); // => 10
</code>

<details>
<summary>Python</summary>

<code python>
lst = DoublyLinkedList()
lst.insert_begin(1)
lst.insert_begin(2)
lst.insert_begin(3)
lst.insert_begin(4)

print(sum(lst.fore()))
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

$list = new DoublyLinkedList();
$list->insertBegin(1);
$list->insertBegin(2);
$list->insertBegin(3);
$list->insertBegin(4);

print_r(sum($list->fore())); // => 10
</code>
</details>

<details>
<summary>Java</summary>

<code java>
class DoubleLinkedList implements Iterable<Object> {
  // ...

    @Override
    public Iterator<Object> iterator() {
        return new DoubleLinkedListIterator();
    }

    private class DoubleLinkedListIterator implements Iterator<Object> {
        DoubleLinkedListNode current = head;

        @Override
        public Object next() {
            if (!this.hasNext()) {
                throw new NoSuchElementException();
            }
            var lastReturnedNode = current;
            current = current.next;
            return lastReturnedNode.value;
        }

        @Override
        public boolean hasNext() {
            return current != null;
        }
    }
}

var list = new DoubleLinkedList();
list.insertBegin(1);
list.insertBegin(2);
list.insertBegin(3);
list.insertBegin(4);

System.out.println(App.sum(list)); // => 10
</code>
</details>

В JavaScript используется синтаксис <color red>function*</color> и <color red>yield</color>, который упрощает работу с итераторами. В нашем примере порядок действий такой:

  * Начинаем с первого узла, адрес которого хранится в поле head 
  * Пробегаем по всем узлам списка 
  * Передаем значения узлов в вызывающую функцию с помощью конструкции <color red>yield</color> 

===== Выводы =====

  * Односвязный список подходит не для всех задач — вставка и удаление в конец списка гораздо медленнее, чем вставка и удаление в начало. Кроме того, в односвязном списке нельзя вставить узел перед другим узлом. 
  * Чтобы справиться с этими трудностями, программисты используют такую структуру данных, как двусвязный список. 
  * В каждом узле двусвязного списка хранится не только ссылка на следующий узел (как у односвязного), но и на предыдущий.
  * К плюсам двусвязного списка можно отнести возможность «пробегать» по списку как вперед, так и назад, а к минусам — сложный код и больший расход памяти.
  * Итераторы позволяют писать один код для работы с коллекциями разных типов. Мы можем реализовать итераторы для тех структур данных, которые мы разрабатываем.

===== Примеры =====

**solutions/solution.js** 
Импортируйте в solution.js класс <color red>DoubleLinkedListNode</color> и функцию <color red>getDoubleLinkedList()</color> следующим образом:
<code javascript>
import DoubleLinkedListNode from '../double_linked_list/DoubleLinkedListNode.js';
import getDoubleLinkedList from '../helpers/helper.js';
</code>

Реализуйте функцию, которая принимает на вход массив и возвращает также массив. Внутри функция должна создавать двусвязный список, после этого поменять первые два элемента списка местами и вернуть массив всех значений.

Для преобразования массива в список используйте функцию <color red>getDoubleLinkedList()</color>, а чтобы получить массив из списка воспользуйтесь методом <color red>toArray()</color> на объекте списка.

Экспортируйте функцию по умолчанию.

<code javascript>
import solution from './solution.js';
 
const items = [[10, 20], 0, -1, ['hey']];
</code>

<details>
<summary>**solutions/solution.php**</summary>
Импортируйте в solution.php код из файлов DoubleLinkedListNode.php и helper.php следующим образом:
<code php>
<?php
 
require_once(__DIR__ . '/../DoubleLinkedList/DoubleLinkedListNode.php');
require_once(__DIR__ . '/../helpers/helper.php');
</code>
Реализуйте функцию <color red>solution()</color>, которая принимает на вход массив и возвращает также массив. Внутри функция должна создавать двусвязный список, после этого поменять первые два элемента списка местами и вернуть массив всех значений.

Для преобразования массива в список используйте функцию <color red>getDoubleLinkedList()</color>, а чтобы получить массив из списка воспользуйтесь методом <color red>toArray()</color> на объекте списка.

<code php>
<?php
 
$items = [[10, 20], 0, -1, ['hey']];
solution($items); // [0, [10, 20], -1, ['hey']]
solution([]); // []
</code>
</details>

<details>
<summary>**solutions/solution.py**</summary>
Импортируйте в solution.py класс <color red>DoubleLinkedListNode</color> и функцию <color red>getListFromArray()</color> следующим образом:
<code python>
import os
import sys
 
sys.path.append(os.path.abspath('/usr/src/app/'))
 
from double_linked_list.DoubleLinkedListNode import DoubleLinkedListNode  # noqa: E402
from helpers.helper import get_double_linked_list  # noqa: E402
</code>

Реализуйте функцию <color red>solution()</color>, которая принимает на вход список и возвращает также список. Внутри функция должна создавать двусвязный список, после этого поменять первые два элемента двусвязного списка местами и вернуть список всех значений.

Для преобразования списка в двусвязный список используйте функцию <color red>get_double_linked_list()</color>, а чтобы получить список из экземпляра двусвязного списка воспользуйтесь методом <color red>to_array()</color> на объекте двусвязного списка.
<code python>
import solution from solution
 
items = [[10, 20], 0, -1, ['hey']]
 
solution(items) # [0, [10, 20], -1, ['hey']]
solution([]) # []
</code>

</details>

<details>
<summary>**solutions/Solution.java**</summary>
  * Создайте в классе пакет <color red>solutions</color> и определите в нем публичный класс <color red>Solution</color>
  * Создайте в классе публичный статический метод <color red>swap()</color>, который меняет местами первые два элемента двусвязного списка. Метод принимает в качестве параметра двусвязный список <color red>DoubleLinkedList</color>, меняет местами первые два элемента и возвращает новый связный список
<code java>
import linkedlist.DoubleLinkedList;
 
DoubleLinkedList list = new DoubleLinkedList();
list.append(1);
list.append(2);
list.append(3);
list.append(4);
list.toList(); // [1, 2, 3, 4]
 
DoubleLinkedList swapped = Solution.swap(list);
 
swapped.toList(); // [2, 1, 3, 4]
</code>
  * Добавьте в класс Solution метод run() со следующим кодом:

<code java>
public static java.util.List<Object> run(java.util.List<Object> coll) {
    return helpers.Helper.run(coll);
}
</code>

</details>