Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

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

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

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

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

  • Сложно найти товар на складе

  • Просто сделать новую запись в журнале

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

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

  • Просто найти книгу в библиотеке

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

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

Журнал

Картотека

Запись

Быстро

Медленно

Поиск

Медленно

Быстро

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

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

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

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

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

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

let a = 1;
let b = false;
Python
a = 1
b = False
PHP
<?php

$a = 1;
$b = false;
Java
var a = 1;
var b = false;
200

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

eyJpZCI6IjQxYzAxYTBjNTM5NGM1MGI3ZTIxNjA5NjFhNGIwYWU3LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=abb69606c5a375edd9f4b8d24326147598904a192a6c0ba2e649563df28ef6a1

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

let items = [5, 8, 12, 3];
Python
items = [5, 8, 12, 3]
PHP
<?php

$items = [5, 8, 12, 3];
Java
int[] items = {5, 8, 12, 3};
eyJpZCI6ImVhZmVmYTJlYzZlYTZmZTExOWYxYzJkMGJiMGUzZDY2LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=7580a04180968c2872959d09286051b305e9195d0c58983224244d9abc747f61

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

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

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

console.log(items[2]); // => 12
Python
print(items[2]) # => 12
PHP
<?php

print_r($items[2]) // => 12
Java
System.out.println(items[2]); // => 12

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

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

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

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

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
Python
def sum(items):
    result = 0

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

    return result

sum([1, 2, 3, 4]) # 10
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
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;
    }
}

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

items.push(7);
items.push(20);
Python
items.append(7)
items.append(20)
PHP
<?php

$items[] = 7;
$items[] = 20;
Java
// В Java массивы имеют фиксированную длину, которая задается при создании массива.
// Если в процессе работы нужно расширять массив, можно использовать
// класс ArrayList, который представляет реализацию динамического массива

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

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

eyJpZCI6IjcyYmJlOGE3NzYzOGM1MzIzYWE1ZTkyNjYxMGY4NjA1LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=dafe9436eae99d690354ff0fd566f707f5d8a662fa6e7834c0e66de2195a08b8

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

let items = [5, 8, 12, 3];
let point = { x: -5, y: 7 };
items.push(7);
items.push(20);
Python
items = [5, 8, 12, 3];
point = {'x': -5, 'y': 7};
items.append(7);
items.append(20);
PHP
<?php

$items = [5, 8, 12, 3];
$point = ['x' => -5, 'y' => 7];
$items[] = 7;
$items[] = 20;
Java
List<Object> items = new ArraList<>();
Map<String, Integer> point = Map.of("x", -5, "y", 7);
items.add(7);
items.add(20);
eyJpZCI6IjJkNmE2ZDE4OWJiODZhM2I5MTMwMTA4NzI4NTRlMTdhLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=a541399cc09b680fa24834436e1250072c60b6782041415168aba7775178b297

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

eyJpZCI6IjZkYjBkZTNhZTFmYjZlYmY2OWFiM2M1ZmM0MzUwZTU2LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=a6b078dfbce3f28c1d4c42c77d3417dc84d470906c876010db5ec9b846269ee3

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

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

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

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

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

class LinkedListNode {
  constructor(value, next) {
    this.value = value;
    this.next = next;
  }
}
Python
class LinkedListNode:
    def __init__(self, value, next):
        self.value = value
        self.next = next
PHP
<?php

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

    public Object value;
    public LinkedListNode next;

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

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

var head = new LinkedList(5,
           new LinkedList(8,
           new LinkedList(12,
           new LinkedList(3, null))));
Python
head = LinkedList(
    5, LinkedList(
        8, LinkedList(
            12, LinkedList(
                3, None))))
PHP
<?php

$head = new LinkedList(5,
        new LinkedList(8,
        new LinkedList(12,
        new LinkedList(3, null))));
Java
var head = new LinkedListNode(5,
    new LinkedListNode(8,
        new LinkedListNode(12,
            new LinkedListNode(3, null)
        )
    )
);

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

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

eyJpZCI6ImEwZjZlNzU3YTk1ZjA0OTdjOGE3Y2Y0Y2FhM2Q5MGM4LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=790c683576f83456ee4dc40d58d5f786bb00b9b72266e59354fb570dde57119f

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

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

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

class LinkedList {
  head = null;
}
Python
class LinkedList:
    def __init__(self):
        self.head = None
PHP
<?php

class LinkedList
{
    public $head = null;
}
Java
class LinkedList {
    public LinkedListNode head = null;
}

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

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

200

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

eyJpZCI6IjQwYTVjZTMyYWViNTdmM2NjMzY0MjI3MDk4MDJlMDI0LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=404a2e480d66be0469d6272baf08717d6cbe0665dd2d83b130fe71aeacd866b1

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

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

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

eyJpZCI6IjFhNTJiYmUxNTBhNmNlMmQxMDFmNWVjYjViYWIwMjc3LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=f7c724c1c699b514e92d1e2ff9dcff933439667af0acb4bf7eedef6ac46db0d8

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

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

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

class LinkedList {
  head = null;

  add(value) {
    this.head = new LinkedListNode(value, this.head);
  }
}
Python
class LinkedList:
    def __init__(self):
        self.head = None

    def add(self, value):
        self.head = LinkedListNode(value, self.head)
PHP
<?php

class LinkedList
{
    public $head = null;

    public function add($value)
    {
      $this->head = new LinkedListNode($value, $this->head);
    }
}
Java
class LinkedList {
    public LinkedListNode head = null;

    public void add(Object value) {
        head = new LinkedListNode(value, head);
    }
}

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

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

this.head = new LinkedListNode(value, this.head);
Python
self.head = LinkedListNode(value, self.head)
PHP
<?php

$this->head = new LinkedListNode($value, $this->head);
Java
head = new LinkedListNode(value, head);

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

let node = new LinkedListNode(value, this.head);
this.head = node;
Python
node = LinkedListNode(value, self.head);
self.head = node;
PHP
<?php

$node = new LinkedListNode($value, $this->head);
$this->head = $node;
Java
LinkedListNode node = new LinkedListNode(value, head);
head = node;

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

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

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

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

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

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 > 0) {
      current = current.next;
      index = index - 1;
    }

    current.next = new LinkedListNode(value, current.next);
  }
}
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 > 0:
            current = current.next
            index = index - 1

        current.next = LinkedListNode(value, current.next)
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 > 0) {
            $current = $current->next;
            $index = $index - 1;
        }

        $current->next = new LinkedListNode($value, $current->next);
    }
}
Java
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 > 0) {
                current = current.next;
                index = index - 1;
            }

            current.next = new LinkedListNode(value, current.next);
        }
    }
}

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

if (index === 0) {
  add(value);
}
Python
elif index == 0:
    self.add(value)
PHP
<?php

if ($index === 0) {
  $this->add($value);
}
Java
else if (index == 0) {
    add(value);
}

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

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

if (this.head === null) {
  this.head = new LinkedListNode(value, null);
}
Python
if self.head is None:
    self.head = LinkedListNode(value, None)
PHP
<?php

if ($this->head === null) {
    $this->head = new LinkedListNode($value, null);
}
Java
if (head == null) {
    head = new LinkedListNode(value, null);
}

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

while (current.next !== null && index > 0) {
  current = current.next;
  index = index - 1;
}
Python
while current.next is not None and index > 0:
    current = current.next
    index = index - 1
PHP
<?php

while ($current->next !== null && $index > 0) {
  $current = $current->next;
  $index = $index - 1;
}
Java
while (current.next != null && index > 0) {
    current = current.next;
    index = index - 1;
}

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

eyJpZCI6Ijk3MGM1MTA5ZjRlZDZjZTJiMmFhOTg0OWJhMTQ5MzJmLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=1ae3800f0da9bf0daf881be6a3b0c2b48b00570703911ec0fcb2f42370f8e672

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

eyJpZCI6IjA3ZTIzNmUyMGIxYjU3YTc5YTYyMzgwY2NmOTU2ZmI4LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=74d20663b9b6b5a346352db806e6bea8730315ac1f1ad0d3f7b32df71c812ad7

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

eyJpZCI6IjQwYTVjZTMyYWViNTdmM2NjMzY0MjI3MDk4MDJlMDI0LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=404a2e480d66be0469d6272baf08717d6cbe0665dd2d83b130fe71aeacd866b1

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

current.next = new LinkedListNode(value, current.next);
Python
current.next = LinkedListNode(value, current.next)
PHP
<?php

$current->next = new LinkedListNode($value, $current->next);
Java
current.next = new LinkedListNode(value, current.next);

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

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

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

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

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

    current = current.next;
  }

  return false;
}
Python
def contains(self, value):
    current = self.head
    while current is not None:
        if current.value == value:
            return True
        current = current.next
    return False
PHP
<?php

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

        $current = $current->next;
    }

    return false;
}
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;
    }
}

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

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

if (current.value === value) {
  return true;
}
Python
if current.value == value:
    return True
PHP
<?php

if ($current->value === $value) {
    return true;
}
Java
if (current.value.equals(value)) {
    return true;
}

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

current = current.next;
Python
current = current.next
PHP
<?php

$current = $current->next;
Java
current = current.next;

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

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

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

length() {
  let result = 0;
  let current = this.head;

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

  return result;
}
Python
def length(self):
    result = 0
    current = self.head

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

    return result
PHP
<?php

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

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

    return result;
}
Java
class LinkedList {
    // ...
    public int length() {
        var result = 0;
        var current = this.head;

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

        return result;
    }
}

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

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

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

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

remove() {
  if (this.head === null) {
    return undefined;
  }

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

  return value;
}
Python
def remove(self):
    if self.head is None:
        return None

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

    return value
PHP
<?php

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

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

    return $value;
}
Java
class LinkedList {
    // ...
    public Object remove() {
        if (head == null) {
            return null;
        }

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

        return value;
    }
}

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

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

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

eyJpZCI6IjFhNTJiYmUxNTBhNmNlMmQxMDFmNWVjYjViYWIwMjc3LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=f7c724c1c699b514e92d1e2ff9dcff933439667af0acb4bf7eedef6ac46db0d8
eyJpZCI6ImU2YWUyMTM0ZTVmZmZlYjU3NmNmODA5YjJlMTQ3MWQ4LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=341480630649f8c95f8e3c23abbc2358faa64abb376ed141519aeea3c52dd3f1
200

Удаление элемента из середины или конца списка

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

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

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 > 0) {
      current = current.next;
      index = index - 1;
    }

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

    return value;
  }
}
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 > 0:
            current = current.next
            index -= 1

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

        return value
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 > 0) {
            $current = $current->next;
            $index = $index - 1;
        }

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

        return $value;
    }
}
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 > 0) {
            current = current.next;
            index = index - 1;
            }

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

            return value;
        }
    }
}

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

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

if (index === 0 || this.head.next === null) {
  return remove();
}
Python
elif index == 0 or self.head.next is None:
    return self.remove()
PHP
<?php

if ($index === 0 || $this->head.next === null) {
    return $this->remove();
}
Java
else if (index == 0 || head.next == null) {
    return remove();
}

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

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

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

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

Массив

Список

Вставка в начало

Вставка в середину

Вставка в конец

Доступ по индексу

Удаление из начала

Удаление из середины

Удаление из конца

Поиск

Длина

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

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

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

Выводы

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

  • Структура данных — это способ хранения данных в памяти компьютера Одни и те же операции могут быть быстрыми для одних структур и медленными для других

  • Сложные структуры данных — объекты и массивы — хранятся в куче.

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

  • Определение длины и поиск элемента по индексу быстрее в массиве. Массив и связный список похожи на ежедневник и дневник


Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты.

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»