Что такое linked list?
На этой странице
Linked list - структура данных из узлов, где каждый узел хранит значение и ссылку на следующий узел. В отличие от массива, она не дает быстрого доступа по индексу, но позволяет эффективно вставлять и удалять узлы, если ссылка на место уже известна.
Вопрос
Что такое linked list, чем он отличается от массива и как его разворачивать?
Узел списка
type ListNode<T> = {
value: T
next: ListNode<T> | null
}Пример:
10 -> 20 -> 30 -> nullОбход
function toArray<T>(head: ListNode<T> | null): T[] {
const result: T[] = []
let current = head
while (current) {
result.push(current.value)
current = current.next
}
return result
}Time O(n).
Разворот linked list
function reverse<T>(head: ListNode<T> | null): ListNode<T> | null {
let prev: ListNode<T> | null = null
let current = head
while (current) {
const next = current.next
current.next = prev
prev = current
current = next
}
return prev
}Главная опасность - потерять хвост списка. Поэтому перед current.next = prev мы сохраняем next. Проследим для 1 -> 2 -> 3 -> null:
| Шаг | prev | current | Что сделали | Состояние |
|---|---|---|---|---|
| старт | null | 1 | - | 1 -> 2 -> 3 |
| 1 | 1 | 2 | 1 теперь указывает на null | null <- 1 2 -> 3 |
| 2 | 2 | 3 | 2 теперь указывает на 1 | null <- 1 <- 2 3 |
| 3 | 3 | null | 3 теперь указывает на 2 | null <- 1 <- 2 <- 3 |
Цикл закончился, prev указывает на новую голову - узел 3. Time O(n), space O(1).
Вставка после известного узла
function insertAfter<T>(node: ListNode<T>, value: T): void {
node.next = { value, next: node.next }
}Ничего не сдвигается - меняются только две ссылки, поэтому O(1). В массиве для такой вставки пришлось бы сдвинуть все элементы правее.
Linked list vs array
| Операция | Array | Linked list |
|---|---|---|
| access by index | O(1) | O(n) |
| search | O(n) | O(n) |
| insert after known node | O(n) shift | O(1) |
| insert at head | O(n) (unshift) | O(1) |
| extra memory | меньше | ссылки на узлы |
Что отвечать на собеседовании?
Linked list состоит из узлов, где каждый хранит значение и ссылку на следующий узел. Доступ по индексу медленный, O(n), потому что нужно идти от головы. Зато вставка/удаление после известного узла может быть O(1). На интервью часто спрашивают reverse list, detect cycle, merge two sorted lists.
Что важно помнить: частые ошибки
- Потерять
nextпри развороте списка. - Не обработать
head = null. - Забыть обновить tail.
- Путать node и value.
- Делать рекурсивное решение на очень длинном списке без учета stack.
Мини-шпаргалка
- Node = value + next.
- Head - первый узел.
- Tail - последний узел.
- Access by index -
O(n). - Insert after node -
O(1). - Reverse требует
prev/current/next.