Ответ
Связный список — это линейная структура данных, состоящая из последовательности узлов (Nodes), где каждый узел хранит:
- Данные (value).
- Ссылку (указатель) на следующий узел (
next).
Реализация узла на Swift:
class Node<T> {
var value: T
var next: Node? // Ссылка на следующий узел
init(value: T, next: Node? = nil) {
self.value = value
self.next = next
}
}
// Создание списка: 1 -> 2 -> 3
let node3 = Node(value: 3)
let node2 = Node(value: 2, next: node3)
let head = Node(value: 1, next: node2) // Голова спискаОсновные виды связных списков:
- Односвязный (Singly Linked): Узел ссылается только на следующий.
- Двусвязный (Doubly Linked): Узел содержит ссылки на
nextиprevious. - Кольцевой (Circular): Последний узел ссылается на первый.
| Сравнение с массивом (Array): | Операция | Связный список | Массив |
|---|---|---|---|
| Доступ по индексу | O(n) (медленно) | O(1) (быстро) | |
| Вставка в начало | O(1) (быстро) | O(n) (медленно) | |
| Удаление из начала | O(1) (быстро) | O(n) (медленно) | |
| Использование памяти | Больше (хранит ссылки) | Меньше (только данные) |
Когда использовать? Связные списки эффективны для реализации стеков, очередей или в сценариях с частыми вставками/удалениями в начале последовательности, где не требуется быстрый произвольный доступ.
Ответ 18+ 🔞
А, связный список, ну это ж классика, блядь! Представь себе цепочку, где каждый звенышко — это как отдельный чувак, который держит в одной руке свою ценную хуйню (данные), а другой рукой хватает следующего такого же чувака за шкирку. Вот и вся структура, ёпта!
Каждый узел — это просто бандит с двумя карманами:
- В одном — его ценность (
value), что он там хранит, похуй. - Во втором — адресок на следующего такого же бандита (
next). А если он последний в цепочке, то в кармане пусто,nil, пиздец и точка.
Вот как это на Swift выглядит, смотри не обосрись:
class Node<T> {
var value: T
var next: Node? // Вот эта ссылочка, которая тянется к следующему
init(value: T, next: Node? = nil) {
self.value = value
self.next = next
}
}
// Собираем цепочку: 1 -> 2 -> 3
let node3 = Node(value: 3) // Третий, ему не за кого хвататься, он крайний
let node2 = Node(value: 2, next: node3) // Второй, хватает третьего
let head = Node(value: 1, next: node2) // Голова, главный, он цепляет второгоА ещё эти списки бывают разные, как люди в подъезде:
- Односвязный — как скромняга, знает только того, кто перед ним. Только
next. - Двусвязный — уже похуистичнее, знает и того, кто перед ним, и того, кто сзади (
nextиprevious). Удобно, если надо дать назад. - Кольцевой — это вообще ебушки-воробушки, когда последний хватает за шкирку первого, и они все по кругу бегают, пиздец.
А теперь главное: чем это лучше или хуже обычного массива? Сейчас разберём, блядь.
| Что делаем | Связный список | Массив (Array) |
|---|---|---|
| Найти по номеру | O(n) — иди по цепочке, всех перещупай, медленно. | O(1) — прыгнул сразу на нужную ячейку, быстро! |
| Впихнуть в начало | O(1) — взял нового чувака, дал ему адресок старой головы, и всё, ты теперь голова! Быстро! | O(n) — блядь, всем остальным придётся сдвигаться, чтобы место освободить. Медленно! |
| Выкинуть из начала | O(1) — сказал голове: "Ты свободен!", и назначил головой второго. Быстро! | O(n) — опять всех двигать, медленно! |
| Память | Больше — каждый чувак хранит ещё и ссылку, лишний байтик. | Меньше — хранят только свои данные, компактно. |
Так когда эту хуйню использовать? Да когда тебе похуй на быстрый поиск по индексу, но надо часто в начале цепочки что-то пихать или выкидывать! Очереди, стеки — их родная стихия. А если тебе надо постоянно прыгать туда-сюда по индексам — иди нахуй с твоим списком, бери массив.