basics_of_algorithms:linked_list []

Эта страница только для чтения. Вы можете посмотреть её исходный текст, но не можете его изменить. Сообщите администратору, если считаете, что это неправильно.
====== Связный список — Основы алгоритмов и структур данных ======

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

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

Из-за специфики работы склада кладовщик составляет базу данных, в которой:

  * Сложно найти товар на складе 
  * Просто сделать новую запись в журнале 

Ситуация в библиотеке совсем другая. Основная работа библиотекаря — поиск книг по фамилии автора, по названию книги или по тематике. Для быстрого поиска книг библиотекари используют картотеку. Для каждой книги заводятся несколько карточек и размещаются в разных ящиках. В одном они упорядочены по фамилии автора, в другом — по названию. Благодаря порядку карточки ищутся очень быстро.

Так в библиотеке составляется база данных с совсем другими свойствами:

  * Просто найти книгу в библиотеке 
  * Сложно сделать новую запись в картотеке 

И на складе, и в библиотеке нам приходится записывать и искать похожую информацию, однако скорость записи и поиска получается разная:

| | **Журнал** | **Картотека** |
| Запись | Быстро | Медленно |
| Поиск | Медленно | Быстро |

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

В обоих примерах своя **структура данных** — то есть способ хранения данных в памяти компьютера. Для каждой структуры существует набор основных операций — добавление, поиск, удаление. Из-за особенностей структуры, добавление и поиск могут быть быстрыми или медленными.

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

===== Как устроен массив =====

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

В JavaScript все данные относятся к примитивным или ссылочных типам. Числа и булевы значения хранятся непосредственно в переменных:

<code javascript>
let a = 1;
let b = false;
</code>

<details>
<summary>Python</summary>

<code python>
a = 1
b = False
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

$a = 1;
$b = false;
</code>
</details>

<details>
<summary>Java</summary>

<code java>
var a = 1;
var b = false;
</code>
</details>

{{ :basics_of_algorithms:image_processing20231016-23-ejm3jj.png?200 |}}


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

{{ :basics_of_algorithms:image_processing20231016-24-nim4pt.png?600 |}}

Название «куча» когда-то было сленговым, но прижилось и сейчас используется как официальный термин. Каждая ячейка в куче — это обычная переменная, которая может хранить одно значение. У каждой ячейки есть адрес — ее порядковый номер. Когда мы создаем новый массив, интерпретатор JavaScript размещает его в свободном месте кучи и записывает в переменную адрес массива:

<code javascript>
let items = [5, 8, 12, 3];
</code>

<details>
<summary>Python</summary>

<code python>
items = [5, 8, 12, 3]
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

$items = [5, 8, 12, 3];
</code>
</details>

<details>
<summary>Java</summary>

<code java>
int[] items = {5, 8, 12, 3};
</code>
</details>

{{ :basics_of_algorithms:image_processing20231016-27-oziva0.png |}}

На рисунке вы видите, как хранится массив в памяти. В ячейках с номерами 00, 01 и 02 уже есть какие-то данные — они «заняты», поэтому массив начинается с ячейки 03.

В самой первой ячейке массива хранится его длина или количество элементов, то есть 4. Затем последовательно хранятся сами значения 5, 8, 12 и 3.

Поскольку элементы массива хранятся последовательно, процессор легко определяет адрес элемента по его порядковому номеру в массиве:

<code javascript>
console.log(items[2]); // => 12
</code>

<details>
<summary>Python</summary>

<code python>
print(items[2]) # => 12
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

print_r($items[2]) // => 12
</code>
</details>

<details>
<summary>Java</summary>

<code java>
System.out.println(items[2]); // => 12
</code>
</details>

Массив начинается с адреса 03, где хранится длина массива. Нулевой элемент массива ''items[0]'' имеет адрес 04, а второй элемент ''items[2]'' — адрес 04 + 2, то есть 06. В этой ячейке находится число 12.

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

Порядковый номер элемента в массиве обычно называют индексом — это название пришло из математики.

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

<code javascript>
const sum = (items) => {
  let result = 0;
  for (let i = 0; i < items.length; i++) {
    result = result + items[i];
  }

  return result;
};

sum([1, 2, 3, 4]) // 10
</code>

<details>
<summary>Python</summary>

<code python>
def sum(items):
    result = 0

    for i in range(len(items)):
        result += items[i]

    return result

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

<details>
<summary>PHP</summary>

<code php>
<?php

function sum($items)
{
    $result = 0;
    for ($i = 0; $i < count($items); $i++) {
        $result = $result + $items[i];
    }

    return $result;
};

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

<details>
<summary>Java</summary>

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

        for (var i = 0; i < items.length; i++) {
            result = result + items[i];
        }

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

Иногда мы хотим расширить массив и добавить к нему несколько элементов. В JavaScript для этого используют метод ''push()'':

<code javascript>
items.push(7);
items.push(20);
</code>

<details>
<summary>Python</summary>

<code python>
items.append(7)
items.append(20)
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

$items[] = 7;
$items[] = 20;
</code>
</details>
<details>
<summary>Java</summary>

<code java>
// В Java массивы имеют фиксированную длину, которая задается при создании массива.
// Если в процессе работы нужно расширять массив, можно использовать
// класс ArrayList, который представляет реализацию динамического массива

List<Object> items = new ArraList<>();
items.add(7);
items.add(20);
</code>
</details>

В простом случае, если сразу за массивом есть свободное место, новые элементы попадут туда:

{{ :basics_of_algorithms:image_processing20231016-33-uwxnwb.png |}}

Мы видим, что длина массива теперь равна шести, и в его конце появились числа 7 и 20. А теперь представим, что программист создал после массива еще несколько объектов и свободной памяти сразу за массивом нет:

<code javascript>
let items = [5, 8, 12, 3];
let point = { x: -5, y: 7 };
items.push(7);
items.push(20);
</code>

<details>
<summary>Python</summary>

<code python>
items = [5, 8, 12, 3]
point = {'x': -5, 'y': 7}
items.append(7)
items.append(20)
</code>
</details>
<details>
<summary>PHP</summary>

<code php>
<?php

$items = [5, 8, 12, 3];
$point = ['x' => -5, 'y' => 7];
$items[] = 7;
$items[] = 20;
</code>
</details>

<details>
<summary>Java</summary>

<code java>
List<Object> items = new ArraList<>();
Map<String, Integer> point = Map.of("x", -5, "y", 7);
items.add(7);
items.add(20);
</code>
</details>

{{ :basics_of_algorithms:image_processing20231016-43-n42l97.png |}}

На рисунке сразу за массивом ''items'' в куче находится объект ''point''. Кажется, что в этом случае мы не можем расширить массив, ведь элементы должны располагаться в памяти подряд. На самом деле при вызове метода ''push()'' интерпретатор копирует весь массив в свободную область памяти и добавляет к ней несколько элементов. Исходная область памяти помечается как свободная:

{{ :basics_of_algorithms:image_processing20231016-33-24gkpl.png |}}

Расширение массива может привести к копированию большого объема данных и замедлению программы. Есть несколько способов борьбы с таким поведением, но копирование все равно случается. Как быть, если нам предстоит часто добавлять и удалять элементы? Можно применить связный список.

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

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

Каждое значение хранится в отдельном объекте, который называется **узлом**. Помимо значения, объект хранит ссылку на следующий узел списка. В самом последнем узле вместо ссылки на следующий элемент хранится значение ''null''.

Опишем класс, содержащий значение ''(value)'' и ссылку на следующий узел ''(next)'':

<code javascript>
class LinkedListNode {
  constructor(value, next) {
    this.value = value;
    this.next = next;
  }
}
</code>

<details>
<summary>Python</summary>

<code python>
class LinkedListNode:
    def __init__(self, value, next):
        self.value = value
        self.next = next
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

class LinkedListNode
{
    public function __construct($value, $next)
    {
        $this->value = $value;
        $this->next = $next;
    }
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
public class LinkedListNode {

    public Object value;
    public LinkedListNode next;

    LinkedListNode(Object value, LinkedListNode next) {
        this.value = value;
        this.next = next;
    }
}
</code>
</details>

Список из элементов 5, 8, 12 и 3 может быть создан так:

<code javascript>
const head = new LinkedListNode(5,
           new LinkedListNode(8,
           new LinkedListNode(12,
           new LinkedListNode(3, null))));
</code>

<details>
<summary>Python</summary>

<code python>
head = LinkedListNode(
    5, LinkedListNode(
        8, LinkedListNode(
            12, LinkedListNode(
                3, None))))
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

$head = new LinkedListNode(5,
        new LinkedListNode(8,
        new LinkedListNode(12,
        new LinkedListNode(3, null))));
</code>
</details>

<details>
<summary>Java</summary>

<code java>
var head = new LinkedListNode(5,
    new LinkedListNode(8,
        new LinkedListNode(12,
            new LinkedListNode(3, null)
        )
    )
);
</code>
</details>

Оператор ''new'' не только создает объект, но и выделяет для него место в памяти. Самый первый элемент односвязного списка часто называют головой (''head''), поэтому и переменную со ссылкой на голову мы назвали ''head''.

В поле ''next'' самого последнего узла находится ''null'' — значит, узлов больше нет. В отличие от массива, узлы списка не размещаются в памяти подряд:

{{ :basics_of_algorithms:image_processing20231016-39-vvop5f.png |}}

На рисунке узлы списка занимают две ячейки. В первой хранится значение, а во второй — адрес следующего узла или ''null''. Иногда узлы могут располагаться рядом (на рисунке это 12 и 3), но в общем случае это не так.

Вся работа со списком производится через ссылку на его первый элемент, так что переменная ''head'' — единственное, что нам нужно для реализации алгоритмов.

Поскольку мы пишем на языке JavaScript, который поддерживает объектно-ориентированное программирование, мы объединим поле ''head'' и все наши функции в один класс. Он будет называться ''LinkedList'', что в переводе с английского означает связный список. При создании нового списка в поле ''head'' хранится значение ''null'', что означает, что список пустой:

<code javascript>
class LinkedList {
  head = null;
}
</code>

<details>
<summary>Python</summary>

<code python>
class LinkedList:
    def __init__(self):
        self.head = None
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

class LinkedList
{
    public $head = null;
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
class LinkedList {
    public LinkedListNode head = null;
}
</code>
</details>

===== Вставка элемента в начало списка =====

В простейшем случае, мы вставляем элемент в пустой список. В самом начале значение поля ''head'' равно ''null'':

{{ :basics_of_algorithms:image_processing20231016-23-dg15lb.png?200 |}}

После вставки ''head'' указывает на единственный элемент списка:

{{ :basics_of_algorithms:image_processing20231016-28-btdjon.png?500 |}}

Мы не рисуем кучу целиком, потому что в реальной программе трудно предугадать, по какому адресу разместится то или иное значение. Конкретные адреса могут сбить с толку.

Поэтому мы просто отмечаем факт, что для нового узла списка в куче были выделены две ячейки, и ''head'' указывает на этот узел. Адрес первого узла мы запишем, как ''addr(1)'', это позволит нам отличать адреса друг от друга.

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

{{ :basics_of_algorithms:image_processing20231016-23-mkvx9s.png?500 |}}

Теперь ''addr(1)'', который находился в ''head'', переместился в узел 2, а в ''head'' попал адрес второго узла ''addr(2)''.

В обоих случаях (вставка в пустой и непустой список), сначала мы создаем узел, куда, в качестве указателя на следующий элемент, записываем текущее значение ''head''.

Взглянем на код:

<code javascript>
class LinkedList {
  head = null;

  add(value) {
    this.head = new LinkedListNode(value, this.head);
  }
}
</code>

<details>
<summary>Python</summary>

<code python>
class LinkedList:
    def __init__(self):
        self.head = None

    def add(self, value):
        self.head = LinkedListNode(value, self.head)
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

class LinkedList
{
    public $head = null;

    public function add($value)
    {
      $this->head = new LinkedListNode($value, $this->head);
    }
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
class LinkedList {
    public LinkedListNode head = null;

    public void add(Object value) {
        head = new LinkedListNode(value, head);
    }
}
</code>
</details>

Метод ''add'' принимает параметр ''value'' (значение). Он создает новый узел, помещает туда значение и вставляет узел в начало списка.

Метод состоит из единственной строки:

<code javascript>
this.head = new LinkedListNode(value, this.head);
</code>

<details>
<summary>Python</summary>

<code python>
self.head = LinkedListNode(value, self.head)
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

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

<details>
<summary>Java</summary>

<code java>
head = new LinkedListNode(value, head);
</code>
</details>

Здесь мы совместили две операции, которые можно было бы записать в две строки:

<code javascript>
let node = new LinkedListNode(value, this.head);
this.head = node;
</code>

<details>
<summary>Python</summary>

<code python>
node = LinkedListNode(value, self.head)
self.head = node
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

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

<details>
<summary>Java</summary>

<code java>
LinkedListNode node = new LinkedListNode(value, head);
head = node;
</code>
</details>

Если первый вариант кода кажется вам сложным, вы можете остановиться на втором. Обычно программисты, по мере чтения кода, привыкают к часто встречающимся конструкциям. Знакомые конструкции уже не кажутся сложными.

Насколько быстро работает метод ''add''? Создание объекта может занимать большое время, но у нас простой конструктор с двумя присваиваниями, поэтому работать он будет быстро.

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

===== Вставка элемента в середину или конец списка =====

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

<code javascript>
insert(index, value) {
  if (this.head === null) {
    this.head = new LinkedListNode(value, null);
  } else if (index === 0) {
    add(value);
  } else {
    let current = this.head;
    while (current.next !== null && index > 1) {
      current = current.next;
      index = index - 1;
    }

    current.next = new LinkedListNode(value, current.next);
  }
}
</code>

<details>
<summary>Python</summary>

<code python>
def insert(self, index, value):
    if self.head is None:
        self.head = LinkedListNode(value, None)
    elif index == 0:
        self.add(value)
    else:
        current = self.head
        while current.next is not None and index > 1:
            current = current.next
            index = index - 1

        current.next = LinkedListNode(value, current.next)
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

public function insert($index, $value)
{
    if ($this->head === null) {
        $this->head = new LinkedListNode($value, null);
    } else if ($index === 0) {
        add($value);
    } else {
        $current = $this->head;
        while ($current->next !== null && $index > 1) {
            $current = $current->next;
            $index = $index - 1;
        }

        $current->next = new LinkedListNode($value, $current->next);
    }
}
</code>
</details>

<details>
<summary>Java</summary>

<code javascript>
class LinkedList {
    // ...

    public void insert(int index, Object value) {
        if (head == null) {
            head = new LinkedListNode(value, null);
        } else if (index == 0) {
            add(value);
        } else {
            var current = head;
            while (current.next != null && index > 1) {
                current = current.next;
                index = index - 1;
            }

            current.next = new LinkedListNode(value, current.next);
        }
    }
}
</code>
</details>

Вызов ''insert(index, value)'' означает, что узел со значением ''value'' будет вставлен в середину списка в позицию ''index''. Если ''index'' равен 0, то значение вставится перед первым элементом — так же, как при вызове ''add'':

<code javascript>
if (index === 0) {
  add(value);
}
</code>

<details>
<summary>Python</summary>

<code python>
elif index == 0:
    self.add(value)
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

if ($index === 0) {
  $this->add($value);
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
else if (index == 0) {
    add(value);
}
</code>
</details>

Если список пустой, ''index'' не может быть больше нуля, потому что мы можем вставить значение только в начало списка. Как должна поступать в этом случае функция решает ее автор. Мы можем генерировать ошибку или попытаться выполнить какое-то разумное действие.

Пойдем вторым путем — если список пустой, при больших значениях ''index'' будем вставлять элемент в самое начало:

<code javascript>
if (this.head === null) {
  this.head = new LinkedListNode(value, null);
}
</code>

<details>
<summary>Python</summary>

<code python>
if self.head is None:
    self.head = LinkedListNode(value, None)
</code>
</details>
<details>
<summary>PHP</summary>

<code php>
<?php

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

<details>
<summary>Java</summary>

<code java>
if (head == null) {
    head = new LinkedListNode(value, null);
}
</code>
</details>

А в случае, если ''index'' оказывается за концом списка, будем вставлять элемент в самый конец. Для этого будем проверять два условия: либо мы нашли элемент с номером ''index'', и он не в конце, либо мы достигли последнего элемента:

<code javascript>
while (current.next !== null && index > 1) {
  current = current.next;
  index = index - 1;
}
</code>

<details>
<summary>Python</summary>

<code python>
while current.next is not None and index > 1:
    current = current.next
    index = index - 1
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

while ($current->next !== null && $index > 1) {
  $current = $current->next;
  $index = $index - 1;
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
while (current.next != null && index > 1) {
    current = current.next;
    index = index - 1;
}
</code>
</details>

Нарисуем, что должно происходить при вставке. Пусть в начале у нас есть список из элементов A и C. Мы хотим вставить элемент B после A, но перед C:

{{ :basics_of_algorithms:image_processing20231016-39-i1kwj1.png?500 |}}

Когда цикл заканчивается, переменная current указывается на узел A:

{{ :basics_of_algorithms:image_processing20231016-27-874b02.png?500 |}}

После вставки мы получим такую картину:

{{ :basics_of_algorithms:image_processing20231016-33-glw5s9.png?600 |}}

Перед вставкой в ''current.next'' хранится ссылка на C, но теперь она должна переехать в узел B, а в ''current.next'' мы запишем ссылку на новый узел B:

<code javascript>
current.next = new LinkedListNode(value, current.next);
</code>

<details>
<summary>Python</summary>

<code python>
current.next = LinkedListNode(value, current.next)
</code>

<details>
<summary>PHP</summary>

<code php>
<?php

$current->next = new LinkedListNode($value, $current->next);
</code>
</details>

<details>
<summary>Java</summary>

<code java>
current.next = new LinkedListNode(value, current.next);
</code>
</details>

===== Поиск элемента =====

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

Если при поиске элемента в массиве, функции часто возвращают индекс элемента, то для списка — логическое значение ''true'' или ''false''.

Вместо ответа на вопрос «если такой элемент в массиве есть, где он находится», функция поиска в списке отвечает на вопрос «есть ли такой элемент в списке»:

<code javascript>
contains(value) {
  let current = this.head;
  while (current !== null) {
    if (current.value === value) {
      return true;
    }

    current = current.next;
  }

  return false;
}
</code>

<details>
<summary>Python</summary>

<code python>
def contains(self, value):
    current = self.head
    while current is not None:
        if current.value == value:
            return True
        current = current.next
    return False
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

public function contains($value)
{
    $current = $this->head;
    while ($current !== null) {
        if ($current->value === $value) {
            return true;
        }

        $current = $current->next;
    }

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

<details>
<summary>Java</summary>

<code java>
class LinkedList {
    // ...
    public boolean contains(Object value) {
        var current = head;
        while (current != null) {
            if (current.value.equals(value)) {
                return true;
            }

            current = current.next;
        }

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

Здесь у нас простой цикл. Мы пробегаем по всем узлам, пока не натыкаемся на ''null''. Если мы встретили ''null'' и не нашли значения, значит, в списке его нет — в конце цикла мы возвращаем ''false''.

Если значение находится в одном из узлов, мы прерываем цикл и сразу возвращаем ''true'':

<code javascript>
if (current.value === value) {
  return true;
}
</code>

<details>
<summary>Python</summary>

<code python>
if current.value == value:
    return True
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

if ($current->value === $value) {
    return true;
}
</code>
</details>

<details>
<summary>Java</summary>

<code java>
if (current.value.equals(value)) {
    return true;
}
</code>
</details>
В конце цикла важно переходить к следующему узлу, иначе цикл станет бесконечным:

<code javascript>
current = current.next;
</code>

<details>
<summary>Python</summary>

<code python>
current = current.next
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

$current = $current->next;
</code>
</details>

<details>
<summary>Java</summary>

<code java>
current = current.next;
</code>
</details>

===== Определение длины списка =====

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

В целом, код получается простой:

<code javascript>
length() {
  let result = 0;
  let current = this.head;

  while (current !== null) {
    result = result + 1;
    current = current.next;
  }

  return result;
}
</code>

<details>
<summary>Python</summary>

<code python>
def length(self):
    result = 0
    current = self.head

    while current is not None:
        result += 1
        current = current.next

    return result
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

public function length()
{
    $result = 0;
    $current = $this->head;

    while ($current !== null) {
        $result = $result + 1;
        $current = $current->next;
    }

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

<details>
<summary>Java</summary>

<code java>
class LinkedList {
    // ...
    public int length() {
        var result = 0;
        var current = this.head;

        while (current !== null) {
            result = result + 1;
            current = current.next;
        }

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

Переменная ''result'' — это наш счетчик. Переменная ''current'' на каждой итерации указывает на текущий узел списка. Когда она становится равной ''null'', список пройден до конца. Перейдя к следующему узлу, мы увеличиваем счетчик, поэтому в конце цикла его значение равно количеству узлов.

===== Удаление элемента из начала списка =====

Удаление элемента из начала списка такое же простое, как и вставка. Мы будем возвращать значение из удаленного узла в качестве результата.

Если список пустой, мы не будем ничего удалять, и в качестве результата вернем ''undefined'':

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

  const value = this.head.value;
  this.head = this.head.next;

  return value;
}
</code>

<details>
<summary>Python</summary>

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

    value = self.head.value
    self.head = self.head.next

    return value
</code>
</details>

<details>
<summary>PHP</summary>

<code php>
<?php

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

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

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

<details>
<summary>Java</summary>

<code java>
class LinkedList {
    // ...
    public Object remove() {
        if (head == null) {
            return null;
        }

        var value = head.value;
        head = head.next;

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

При удалении в this.head попадает ссылка на следующий узел из первого узла. Когда в списке остается один узел, там находится null. После удаления последнего узла this.head становится равным null, что для нас означает пустой список.

Нам не приходится как-то по-особому описывать этот случай в коде — наш код работает для списков любой длины.

Рисунки помогут разобраться, как удаляются узлы из списка:

{{ :basics_of_algorithms:1111112121.png?500 |}}

{{ :basics_of_algorithms:22222sdadzsd.png?600 |}} 

{{ :basics_of_algorithms:333313asdadcac.png?200 |}}
===== Удаление элемента из середины или конца списка =====

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

Мы просто скомбинируем написанный нами ранее код:

<code javascript>
removeAt(index) {
  if (this.head === null) {
    return undefined;
  } else if (index === 0 || this.head.next === null) {
    return remove();
  } else {
    let current = this.head;
    while (current.next.next !== null && index > 1) {
      current = current.next;
      index = index - 1;
    }

    const value = current.value;
    current.next = current.next.next;

    return value;
  }
}
</code>

<details>
<summary>Python</summary>

<code python>
def remove_at(self, index):
    if self.head is None:
        return None

    elif index == 0 or self.head.next is None:
        return self.remove()

    else:
        current = self.head
        while current.next.next is not None and index > 1:
            current = current.next
            index -= 1

        value = current.value
        current.next = current.next.next

        return value
</code>
</details>
<details>
<summary>PHP</summary>

<code php>
<?php

public function removeAt($index)
{
    if ($this->head === null) {
        return undefined;
    } else if ($index === 0 || $this->head.next === null) {
        return $this->remove();
    } else {
        $current = $this->head;
        while ($current->next->next !== null && $index > 1) {
            $current = $current->next;
            $index = $index - 1;
        }

        $value = $current->value;
        $current->next = $current->next->next;

        return $value;
    }
}
</code>
</details>
<details>
<summary>Java</summary>

<code java>
class LinkedList {
    // ...
    public Object removeAt(int index) {
        if (head == null) {
            return null;
        } else if (index == 0 || head.next == null) {
            return remove();
        } else {
            var current = this.head;
            while (current.next.next != null && index > 1) {
            current = current.next;
            index = index - 1;
            }

            var value = current.value;
            current.next = current.next.next;

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

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

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

<code javascript>
if (index === 0 || this.head.next === null) {
  return remove();
}
</code>
<details>
<summary>Python</summary>

<code python>
elif index == 0 or self.head.next is None:
    return self.remove()
</code>
</details>
<details>
<summary>PHP</summary>

<code php>
<?php

if ($index === 0 || $this->head.next === null) {
    return $this->remove();
}
</code>
</details>
<details>
<summary>Java</summary>

<code java>
else if (index == 0 || head.next == null) {
    return remove();
}
</code>
</details>

Меняется и условие в цикле. Если раньше мы проверяли, что ''current.next'' не равен ''null'', то теперь мы проверяем ''current.next.next''. Иными словами, вместо ответа на вопрос «есть ли следующий узел в списке», мы отвечаем на вопрос «есть ли узел за следующим узлом».

В остальном код остается прежним.

===== Сравнение массива и связного списка =====

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

| | Массив | Список |
| Вставка в начало | O(n) | O(1) |
| Вставка в середину | O(n) | O(n) |
| Вставка в конец | O(1) | O(n) |
| Доступ по индексу | O(1) | O(n) |
| Удаление из начала | O(n) | O(1) |
| Удаление из середины | O(n) | O(n) |
| Удаление из конца | O(1) | O(n) |
| Поиск | O(n) | O(n) |
| Длина | O(1) | O(n) |

Всякий раз, когда нам нужно перебирать элементы в массиве или в списке, производительность составляет O(n). Односвязный список хорош, если нам приходится часто вставлять и удалять элементы — O(1).

Поиск и в массиве и в списке не очень быстрый, всего O(n).

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

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

В этом уроке мы изучили односвязный список. Повторим важные тезисы из урока:

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

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

Задача:
**solutions/solution.js**
Импортируйте в solution.js класс LinkedList и функцию getListFromArray() следующим образом:
<code javascript>
import LinkedList from "../lists/LinkedList.js";
import getListFromArray from "../helpers/helpers.js";
</code>


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

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

Экспортируйте по умолчанию.
<code javascript>
import solution from './solution.js';
 
const items = [[10, 20], 0, -1, ['hey']];
 
solution(items); // [['hey'], -1, 0, [10, 20]]
solution([]); // []
</code>

<details>
<summary>**solutions/solution.py**</summary>
Импортируйте в solution.py класс LinkedList и функцию get_linked_list_from_array следующим образом:

<code python>
import os
import sys
 
sys.path.append(os.path.abspath('/usr/src/app/'))
 
from lists.LinkedList import LinkedList
from helpers.helpers import get_linked_list_from_array

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

Для преобразования массива в связный список используйте функцию get_linked_list_from_array(), а чтобы получить список из экземпляра связного списка воспользуйтесь методом to_array() на объекте связного списка.

<code python>
import solution from solution
 
items = [[10, 20], 0, -1, ['hey']]
 
solution(items) # [['hey'], -1, 0, [10, 20]]
solution([]) # []
</code>
</details>

<details>

<summary>**solutions/solution.php**</summary>
Импортируйте в solution.php код из файлов LinkedList.php и helpers.php следующим образом:
<code php>
<?php
 
require_once(__DIR__ . '/../lists/LinkedList.php');
require_once(__DIR__ . '/../helpers/helpers.php');

</code>

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

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

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

</details>

<details>
<summary>**solutions/Solution.java**</summary>
+ Создайте в классе пакет solutions и определите в нем публичный класс Solution
+ Создайте в классе публичный статический метод reverse(), который переворачивает связный список. Метод принимает в качестве параметра связный список LinkedList, переворачивает его и возвращает новый связный список, в котором узлы расположены в обратном порядке:

<code java>
import linkedlist.LinkedList;
 
LinkedList list = new LinkedList();
list.append(1);
list.append(2);
list.head.value; // 1
list.tail.value; // 2
 
LinkedList reversed = Solution.reverse(list);
 
reversed.head.value; // 2
reversed.tail.value; // 1
</code>
Добавьте в класс Solution метод run() со следующим кодом:
<code java>
public static java.util.List<Object> run(java.util.List<Object> coll) {
    return helpers.Helpers.run(coll);
}
</code>

</details>

----

**LinkedListNode.js**
<code javascript>
export default class LinkedListNode {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}
</code>

<details>

<summary>python</summary>

<code python>
class LinkedListNode:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next


</code>

</details>

<details>
<summary>php</summary>

<code php>
<?php

class LinkedListNode {
  public function __construct($value, $next = null)
  {
    $this->value = $value;
    $this->next = $next;
  }
}


</code>
</details>

<details>

<summary>java</summary>

<code java>
package lists;

public class LinkedListNode {

    public Object value;
    public LinkedListNode next = null;

    LinkedListNode(Object value, LinkedListNode next) {
        this.value = value;
        this.next = next;
    }

    LinkedListNode(Object value) {
        this.value = value;
    }
}
</code>

</details>


----


**LinkedList.js**
<code javascript>
import LinkedListNode from './LinkedListNode.js';

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

  prepend(value) {
    // Делаем новый узел головой
    const newNode = new LinkedListNode(value, this.head);
    this.head = newNode;

    // Если нет хвоста, этот узел будет и хвостом
    if (!this.tail) {
      this.tail = newNode;
    }

    return this;
  }

  append(value) {
    const newNode = new LinkedListNode(value);

    // Если нет головы, этот узел будет головой
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;

      return this;
    }

    // Присоеденяем новый узел к концу, делаем его хвостом
    this.tail.next = newNode;
    this.tail = newNode;

    return this;
  }

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

    let deletedNode = null;
    // Проверяем с головы какие ноды надо удалить
    while (this.head && this.head.value === value) {
      deletedNode = this.head;
      this.head = this.head.next;
    }

    let currentNode = this.head;

    // Если у головы не нашли, проверяем остальные значения в списке
    if (currentNode !== null) {
      while (currentNode.next) {
        if (currentNode.next.value === value) {
          deletedNode = currentNode.next;
          currentNode.next = currentNode.next.next;
        } else {
          currentNode = currentNode.next;
        }
      }
    }

    // Проверяе хвост
    if (this.tail.value === value) {
      this.tail = currentNode;
    }

    return deletedNode;
  }

  find(value) {
    if (!this.head) {
      return null;
    }

    let currentNode = this.head;

    // Перебираем список с головы, первое найденное значение возвращаем
    while (currentNode) {
      if (value !== undefined && currentNode.value === value) {
        return currentNode;
      }

      // Делаем текущей следующий элемент списка
      currentNode = currentNode.next;
    }

    return null;
  }

  isEmpty() {
    return this.head === undefined && this.tail === undefined;
  }

  toArray() {
    const result = [];

    if (!this.head) {
      return result;
    }

    let currentNode = this.head;

    while (currentNode) {
      if (currentNode.value !== undefined) {
        result.push(currentNode.value);
      }

      currentNode = currentNode.next;
    }

    return result;
  }
}

</code>

<details>

<summary>python</summary>

<code python>
from lists.LinkedListNode import LinkedListNode


class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def prepend(self, value):
        # Делаем новый узел головой
        new_node = LinkedListNode(value, self.head)
        self.head = new_node

        # Если нет хвоста, этот узел будет и хвостом
        if not self.tail:
            self.tail = new_node

        return self

    def append(self, value):
        new_node = LinkedListNode(value)

        # Если нет головы, этот узел будет головой
        if not self.head:
            self.head = new_node
            self.tail = new_node
            return self

        # Присоеденяем новый узел к концу, делаем его хвостом
        self.tail.next = new_node
        self.tail = new_node
        return self

    def delete(self, value):  # noqa: C901
        if not self.head:
            return None

        deleted_node = None
        # Проверяем с головы какие ноды надо удалять
        while self.head and self.head.value == value:
            deleted_node = self.head
            self.head = self.head.next

        current_node = self.head

        # Если у головы не нашли, проверяем остальные значения в списке
        if current_node is not None:
            while current_node.next:
                if current_node.next.value == value:
                    deleted_node = current_node.next
                    current_node.next = current_node.next.next
                else:
                    current_node = current_node.next

        # Проверяем хвост
        if self.tail.value == value:
            self.tail == current_node

        return deleted_node

    def find(self, value):
        if not self.head:
            return None

        current_node = self.head

        # Перебираем список с головы, первое найденное значение возвращаем
        while current_node:
            if current_node.value is not None and current_node.value == value:
                return current_node

            # Делаем текущей следующий элемент списка
            current_node = current_node.next

        return None

    def is_empty(self):
        return self.head is None and self.tail is None

    def to_array(self):
        result = []
        if self.head is None:
            return result
        current_node = self.head
        while current_node:
            if current_node.value is not None:
                result.append(current_node.value)
            current_node = current_node.next
        return result



</code>

</details>

<details>
<summary>php</summary>

<code php>
<?php

require_once(__DIR__ . '/LinkedListNode.php');

class LinkedList
{
    public function __construct()
    {
        $this->head = null;
        $this->tail = null;
    }

    public function prepend($value)
    {
        // Делаем новый узел головой
        $newNode = new LinkedListNode($value, $this->head);
        $this->head = $newNode;

        // Если нет хвоста, этот узел будет и хвостом
        if (!$this->tail) {
            $this->tail = $newNode;
        }

        return $this;
    }

    public function append($value)
    {
        $newNode = new LinkedListNode($value);

        // Если нет головы, этот узел будет головой
        if (!$this->head) {
            $this->head = $newNode;
            $this->tail = $newNode;

            return $this;
        }

        // Присоединяем новый узел к концу, делаем его хвостом
        $this->tail->next = $newNode;
        $this->tail = $newNode;

        return $this;
    }

    public function delete($value)
    {
        if (!$this->head) {
            return null;
        }

        $deletedNode = null;
        // Проверяем с головы какие ноды надо удалить
        while ($this->head && $this->head->value === $value) {
            $deletedNode = $this->head;
            $this->head = $this->head->next;
        }

        $currentNode = $this->head;

        // Если у головы не нашли, проверяем остальные значения в списке
        if ($currentNode !== null) {
            while ($currentNode->next) {
                if ($currentNode->next->value === $value) {
                    $deletedNode = $currentNode->next;
                    $currentNode->next = $currentNode->next->next;
                } else {
                    $currentNode = $currentNode->next;
                }
            }
        }

        // Проверяем хвост
        if ($this->tail->value === $value) {
            $this->tail = $currentNode;
        }

        return $deletedNode;
    }

    public function find($value)
    {
        if (!$this->head) {
            return null;
        }

        $currentNode = $this->head;

        // Перебираем список с головы, первое найденное значение возвращаем
        while ($currentNode) {
            if ($value !== null && $currentNode->value === $value) {
                return $currentNode;
            }

            // Делаем текущей следующий элемент списка
            $currentNode = $currentNode->next;
        }

        return null;
    }

    public function isEmpty()
    {
        return $this->head === null && $this->tail === null;
    }

    public function toArray()
    {
        $result = [];

        if (!$this->head) {
            return $result;
        }

        $currentNode = $this->head;

        while ($currentNode) {
            if ($currentNode->value !== null) {
                $result[] = $currentNode->value;
            }

            $currentNode = $currentNode->next;
        }

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

<details>

<summary>java</summary>

<code java>
package lists;

import java.util.ArrayList;
import java.util.List;

public class LinkedList {

    public LinkedListNode head = null;
    public LinkedListNode tail = null;

    public LinkedList prepend(Object value) {
        LinkedListNode newNode = new LinkedListNode(value, head);
        head = newNode;

        if (tail == null) {
            tail = newNode;
        }

        return this;
    }

    public LinkedList append(Object value) {
        LinkedListNode newNode = new LinkedListNode(value);

        if (head == null) {
            head = newNode;
            tail = newNode;

            return this;
        }

        tail.next = newNode;
        tail = newNode;

        return this;
    }

    public LinkedListNode delete(Object value) {

        if (head == null) {
            return null;
        }

        LinkedListNode deletedNode = null;

        while (head != null && head.value == value) {
            deletedNode = head;
            head = head.next;
        }

        LinkedListNode currentNode = head;

        if (currentNode != null) {
            while (currentNode.next != null) {
                if (currentNode.next.value == value) {
                    deletedNode = currentNode.next;
                    currentNode.next = currentNode.next.next;
                } else {
                    currentNode = currentNode.next;
                }
            }
        }

        if (tail.value == value) {
            tail = currentNode;
        }

        return deletedNode;
    }

    public LinkedListNode find(Object value)
    {
        if (head == null) {
            return null;
        }

        LinkedListNode currentNode = head;

        while (currentNode != null) {
            if (value != null && currentNode.value == value) {
                return currentNode;
            }

            currentNode = currentNode.next;
        }

        return null;
    }

    public boolean isEmpty()
    {
        return head == null && tail == null;
    }

    public List<Object> toList()
    {
        List<Object> result = new ArrayList<>();

        if (head == null) {
            return result;
        }

        LinkedListNode currentNode = head;

        while (currentNode != null) {
            if (currentNode.value != null) {
                result.add(currentNode.value);
            }

            currentNode = currentNode.next;
        }

        return result;
    }
}

</code>

</details>

----


**helpers.js**
<code javascript>
import LinkedList from '../lists/LinkedList.js';

const getListFromArray = (collection) => {
  const linkedList = new LinkedList();

  // eslint-disable-next-line
  for (const item of collection) {
    linkedList.append(item);
  }

  return linkedList;
};

export default getListFromArray;

</code>

<details>

<summary>python</summary>

<code python>
from lists.LinkedList import LinkedList


def get_linked_list_from_array(items):
    linked_list = LinkedList()

    for value in items:
        linked_list.append(value)

    return linked_list

</code>

</details>

<details>
<summary>php</summary>

<code php>
<?php

require_once(__DIR__ . '/../lists/LinkedList.php');

function getListFromArray($collection)
{
    $linkedList = new LinkedList();

    foreach ($collection as $item) {
        $linkedList->append($item);
    }

    return $linkedList;
}


</code>
</details>

<details>

<summary>java</summary>

<code java>
package helpers;

import lists.LinkedList;
import java.util.List;
import solutions.Solution;

public class Helpers {
    public static LinkedList getLinkedList(List<Object> collection) {

        LinkedList list = new LinkedList();

        for (Object item : collection) {
            list.append(item);
        }

        return list;
    }

    public static List<Object> run(List<Object> coll) {
        LinkedList list = Helpers.getLinkedList(coll);
        LinkedList reversed = Solution.reverse(list);
        return reversed.toList();
    }
}

</code>

</details>

----


**solution.js**
<code javascript>
import LinkedList from '../lists/LinkedList.js';
import getListFromArray from '../helpers/helpers.js';

export default (collection) => {
  const list = getListFromArray(collection);

  const reversedList = new LinkedList();

  if (!list.head) {
    return reversedList.toArray();
  }

  reversedList.prepend(list.head.value);
  let nextNode = list.head.next;
  while (nextNode !== null) {
    reversedList.prepend(nextNode.value);
    nextNode = nextNode.next;
  }

  return reversedList.toArray();
};

</code>

<details>

<summary>python</summary>

<code python>
import os
import sys

sys.path.append(os.path.abspath('/usr/src/app/'))

from lists.LinkedList import LinkedList  # noqa: E402
from helpers.helpers import get_linked_list_from_array  # noqa: E402


def solution(items):
    linked_list = get_linked_list_from_array(items)
    reversed_list = LinkedList()

    if not linked_list.head:
        return reversed_list.to_array()

    reversed_list.prepend(linked_list.head.value)
    next_node = linked_list.head.next
    while next_node:
        reversed_list.prepend(next_node.value)
        next_node = next_node.next
    return reversed_list.to_array()

</code>

</details>

<details>
<summary>php</summary>

<code php>
<?php

require_once(__DIR__ . '/../lists/LinkedList.php');
require_once(__DIR__ . '/../helpers/helpers.php');

function solution($collection)
{
    $list = getListFromArray($collection);
    $reversedList = new LinkedList();

    if ($list->head === null) {
        return $reversedList->toArray();
    }

    $reversedList->prepend($list->head->value);
    $nextNode = $list->head->next;
    while ($nextNode !== null) {
        $reversedList->prepend($nextNode->value);
        $nextNode = $nextNode->next;
    }

    return $reversedList->toArray();
}

</code>
</details>

<details>

<summary>java</summary>

<code java>
package solutions;

import lists.LinkedList;
import lists.LinkedListNode;

public class Solution {
    public static LinkedList reverse(LinkedList coll) {

        LinkedList reversed = new LinkedList();

        if (coll.head == null) {
            return reversed;
        }

        reversed.prepend(coll.head.value);
        LinkedListNode nextNode = coll.head.next;

        while(nextNode != null) {
            reversed.prepend(nextNode.value);
            nextNode = nextNode.next;
        }

        return reversed;
    }

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

</code>

</details>
Инструменты пользователя

Инструменты сайта

Инструменты страницы
