Связный список — Основы алгоритмов и структур данных
Связный список — Основы алгоритмов и структур данных
В этом уроке мы начнем изучать структуры данных и связанные с ними алгоритмы. Чтобы разобраться во всех деталях, мы рассмотрим два примера из реальной жизни — склад и библиотеку.
На складе кладовщик записывает все пришедшие товары в специальный журнал. Рабочий день кладовщика состоит из приема и выдачи товаров. Очень важно записывать прием и выдачу как можно быстрее, поэтому кладовщик просто пишет все операции друг за другом, подряд.
Из-за специфики работы склада кладовщик составляет базу данных, в которой:
- Сложно найти товар на складе
- Просто сделать новую запись в журнале
Ситуация в библиотеке совсем другая. Основная работа библиотекаря — поиск книг по фамилии автора, по названию книги или по тематике. Для быстрого поиска книг библиотекари используют картотеку. Для каждой книги заводятся несколько карточек и размещаются в разных ящиках. В одном они упорядочены по фамилии автора, в другом — по названию. Благодаря порядку карточки ищутся очень быстро.
Так в библиотеке составляется база данных с совсем другими свойствами:
- Просто найти книгу в библиотеке
- Сложно сделать новую запись в картотеке
И на складе, и в библиотеке нам приходится записывать и искать похожую информацию, однако скорость записи и поиска получается разная:
| Журнал | Картотека | |
| Запись | Быстро | Медленно |
| Поиск | Медленно | Быстро |
Как видите, мы не можем выбрать один универсальный способ записи, который подойдет для всех случаев. Для склада больше подходит Журнал, а для библиотеки — Картотека.
В обоих примерах своя структура данных — то есть способ хранения данных в памяти компьютера. Для каждой структуры существует набор основных операций — добавление, поиск, удаление. Из-за особенностей структуры, добавление и поиск могут быть быстрыми или медленными.
Программисты изучают основные структуры данных и запоминают скорость основных операций. Это помогает им выбирать самые подходящие структуры для решения задач пользователя. В этом уроке мы познакомимся со связным списком и сравним его с массивом.
Как устроен массив
Чтобы освоиться с понятием структуры данных и ее операциями, давайте исследуем структуру, которая нам хорошо известна — массив.
В 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
current.next = LinkedListNode(value, current.next)
<?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();
}
}
solution.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);
}
}