Это старая версия документа!

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В 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;

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

Название «куча» когда-то было сленговым, но прижилось и сейчас используется как официальный термин. Каждая ячейка в куче — это обычная переменная, которая может хранить одно значение. У каждой ячейки есть адрес — ее порядковый номер. Когда мы создаем новый массив, интерпретатор 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};

На рисунке вы видите, как хранится массив в памяти. В ячейках с номерами 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);

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

Мы видим, что длина массива теперь равна шести, и в его конце появились числа 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);

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

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

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

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

Каждое значение хранится в отдельном объекте, который называется узлом. Помимо значения, объект хранит ссылку на следующий узел списка. В самом последнем узле вместо ссылки на следующий элемент хранится значение 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 может быть создан так:

const head = new LinkedListNode(5,
           new LinkedListNode(8,
           new LinkedListNode(12,
           new LinkedListNode(3, null))));

Python

head = LinkedListNode(
    5, LinkedListNode(
        8, LinkedListNode(
            12, LinkedListNode(
                3, None))))

PHP

<?php
 
$head = new LinkedListNode(5,
        new LinkedListNode(8,
        new LinkedListNode(12,
        new LinkedListNode(3, null))));

Java

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

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

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

На рисунке узлы списка занимают две ячейки. В первой хранится значение, а во второй — адрес следующего узла или 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:

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

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

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

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

Теперь 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 > 1) {
      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 > 1:
            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 > 1) {
            $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 > 1) {
                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 > 1) {
  current = current.next;
  index = index - 1;
}

Python

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

PHP

<?php
 
while ($current->next !== null && $index > 1) {
  $current = $current->next;
  $index = $index - 1;
}

Java

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

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

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

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

Перед вставкой в 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, что для нас означает пустой список.

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

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

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

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

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

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

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

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

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

Единственное нововведение по сравнению с предыдущим кодом заключается в том, что при удалении узла из середины, нам нужно просматривать список на два элемента вперед. Если мы хотим удалить последний узел в списке, нам придется вносить изменения в предпоследний — менять там значение ссылки 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. Иными словами, вместо ответа на вопрос «есть ли следующий узел в списке», мы отвечаем на вопрос «есть ли узел за следующим узлом».

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

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

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

	Массив	Список
Вставка в начало	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() следующим образом:

import LinkedList from "../lists/LinkedList.js";
import getListFromArray from "../helpers/helpers.js";

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

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

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

import solution from './solution.js';
 
const items = [[10, 20], 0, -1, ['hey']];
 
solution(items); // [['hey'], -1, 0, [10, 20]]
solution([]); // []

solutions/solution.py

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

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

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

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

import solution from solution
 
items = [[10, 20], 0, -1, ['hey']]
 
solution(items) # [['hey'], -1, 0, [10, 20]]
solution([]) # []

solutions/solution.php

Импортируйте в solution.php код из файлов LinkedList.php и helpers.php следующим образом:

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

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

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

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

solutions/Solution.java

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

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

Добавьте в класс Solution метод run() со следующим кодом:

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

LinkedListNode.js

export default class LinkedListNode {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

python

class LinkedListNode:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

php

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

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

LinkedList.js

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

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

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

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

helpers.js

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;

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

php

<?php
 
require_once(__DIR__ . '/../lists/LinkedList.php');
 
function getListFromArray($collection)
{
    $linkedList = new LinkedList();
 
    foreach ($collection as $item) {
        $linkedList->append($item);
    }
 
    return $linkedList;
}

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();
    }
}

helpers.js

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();
};

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()

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();
}

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);
    }
}

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

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

Боковая панель

Содержание

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

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

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

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

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

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

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

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

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

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

Выводы

Пример

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