Rivalry2

HTML Diff

1 added 97 removed

Original 2026-01-01

Modified 2026-02-26

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

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

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

4 <ul><li>Сложно найти товар на складе</li>

5 <li>Просто сделать новую запись в журнале</li>

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

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

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

8 <ul><li>Просто найти книгу в библиотеке</li>

9 <li>Сложно сделать новую запись в картотеке</li>

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

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

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

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

14 <h2>Как устроен массив</h2>

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

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

17 - Javascript

18 - Python

19 - PHP

20 - Java

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

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

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

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

23 - Javascript

24 - Python

25 - PHP

26 - Java

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

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

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

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

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

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

30 - Javascript

31 - Python

32 - PHP

33 - Java

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

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

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

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

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

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

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

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

38 - Javascript

39 - Python

40 - PHP

41 - Java

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

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

43 - Javascript

44 - Python

45 - PHP

46 - Java

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

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

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

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

49 - Javascript

50 - Python

51 - PHP

52 - Java

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

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

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

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

55 <h2>Связный список</h2>

31 <h2>Связный список</h2>

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

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

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

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

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

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

59 - Javascript

60 - Python

61 - PHP

62 - Java

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

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

64 - Javascript

65 - Python

66 - PHP

67 - Java

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

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

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

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

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

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

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

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

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

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

73 - Javascript

74 - Python

75 - PHP

76 - Java

77 <h2>Вставка элемента в начало списка</h2>

41 <h2>Вставка элемента в начало списка</h2>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

86 - Javascript

87 - Python

88 - PHP

89 - Java

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

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

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

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

92 - Javascript

93 - Python

94 - PHP

95 - Java

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

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

97 - Javascript

98 - Python

99 - PHP

100 - Java

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

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

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

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

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

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

104 <h2>Вставка элемента в середину или конец списка</h2>

56 <h2>Вставка элемента в середину или конец списка</h2>

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

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

106 - Javascript

107 - Python

108 - PHP

109 - Java

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

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

111 - Javascript

112 - Python

113 - PHP

114 - Java

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

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

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

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

117 - Javascript

118 - Python

119 - PHP

120 - Java

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

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

122 - Javascript

123 - Python

124 - PHP

125 - Java

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

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

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

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

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

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

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

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

130 - Javascript

131 - Python

132 - PHP

133 - Java

134 <h2>Поиск элемента</h2>

66 <h2>Поиск элемента</h2>

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

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

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

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

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

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

138 - Javascript

139 - Python

140 - PHP

141 - Java

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

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

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

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

144 - Javascript

145 - Python

146 - PHP

147 - Java

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

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

149 - Javascript

150 - Python

151 - PHP

152 - Java

153 <h2>Определение длины списка</h2>

73 <h2>Определение длины списка</h2>

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

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

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

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

156 - Javascript

157 - Python

158 - PHP

159 - Java

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

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

161 <h2>Удаление элемента из начала списка</h2>

77 <h2>Удаление элемента из начала списка</h2>

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

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

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

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

164 - Javascript

165 - Python

166 - PHP

167 - Java

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

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

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

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

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

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

171 <h2>Удаление элемента из середины или конца списка</h2>

83 <h2>Удаление элемента из середины или конца списка</h2>

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

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

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

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

174 - Javascript

175 - Python

176 - PHP

177 - Java

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

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

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

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

180 - Javascript

181 - Python

182 - PHP

183 - Java

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

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

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

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

186 <h2>Сравнение массива и связного списка</h2>

90 <h2>Сравнение массива и связного списка</h2>

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

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

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

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

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

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

190 <h2>Выводы</h2>

94 <h2>Выводы</h2>

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

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

192 <ul><li>Структура данных - это способ хранения данных в памяти компьютера. Одни и те же операции могут быть быстрыми для одних структур и медленными для других</li>

96 <ul><li>Структура данных - это способ хранения данных в памяти компьютера. Одни и те же операции могут быть быстрыми для одних структур и медленными для других</li>

193 <li>Сложные структуры данных - объекты и массивы - хранятся в куче.</li>

97 <li>Сложные структуры данных - объекты и массивы - хранятся в куче.</li>

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

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

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

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

196 </ul>

100 </ul>