Односвязный список

Что такое связный список?

Связный список — это структура данных, где каждый элемент (узел) хранит значение и ссылку на следующий узел. В отличие от массива, элементы не лежат в памяти подряд.

Массив:
[10|20|30|40|50]  <- непрерывная память

Связный список:
[10|->] -> [20|->] -> [30|->] -> [40|->] -> [50|null]
  head                                        tail

Структура узла

class ListNode
{
    public function __construct(
        public int $val = 0,
        public ?ListNode $next = null,
    ) {}
}

type ListNode struct {
    Val  int
    Next *ListNode
}

func NewListNode(val int) *ListNode {
    return &ListNode{Val: val}
}

public class ListNode(int val = 0, ListNode? next = null)
{
    public int Val { get; set; } = val;
    public ListNode? Next { get; set; } = next;
}

from __future__ import annotations

from dataclasses import dataclass

@dataclass
class ListNode:
    val: int = 0
    next: ListNode | None = None

## Создание списка

// Manual creation
$node1 = new ListNode(1);
$node2 = new ListNode(2);
$node3 = new ListNode(3);
$node1->next = $node2;
$node2->next = $node3;
// 1 -> 2 -> 3 -> null

// Create from array (helper)
function createList(array $arr): ?ListNode
{
    if (empty($arr)) {
        return null;
    }
    $head = new ListNode($arr[0]);
    $current = $head;
    for ($i = 1; $i < count($arr); $i++) {
        $current->next = new ListNode($arr[$i]);
        $current = $current->next;
    }
    return $head;
}

$head = createList([1, 2, 3, 4, 5]);

// Manual creation
node1 := &ListNode{Val: 1}
node2 := &ListNode{Val: 2}
node3 := &ListNode{Val: 3}
node1.Next = node2
node2.Next = node3
// 1 -> 2 -> 3 -> nil

// Create from slice (helper)
func createList(arr []int) *ListNode {
    if len(arr) == 0 {
        return nil
    }
    head := &ListNode{Val: arr[0]}
    current := head
    for i := 1; i < len(arr); i++ {
        current.Next = &ListNode{Val: arr[i]}
        current = current.Next
    }
    return head
}

// head := createList([]int{1, 2, 3, 4, 5})

// Manual creation
var node1 = new ListNode(1);
var node2 = new ListNode(2);
var node3 = new ListNode(3);
node1.Next = node2;
node2.Next = node3;
// 1 -> 2 -> 3 -> null

// Create from array (helper)
static ListNode? CreateList(int[] arr)
{
    if (arr.Length == 0)
    {
        return null;
    }
    var head = new ListNode(arr[0]);
    var current = head;
    for (var i = 1; i < arr.Length; i++)
    {
        current.Next = new ListNode(arr[i]);
        current = current.Next;
    }
    return head;
}

var head = CreateList([1, 2, 3, 4, 5]);

# Manual creation
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node1.next = node2
node2.next = node3
# 1 -> 2 -> 3 -> None

# Create from list (helper)
def create_list(values: list[int]) -> ListNode | None:
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for value in values[1:]:
        current.next = ListNode(value)
        current = current.next
    return head

head = create_list([1, 2, 3, 4, 5])

## Обход списка

function printList(?ListNode $head): void
{
    $current = $head;
    while ($current !== null) {
        echo $current->val . ' -> ';
        $current = $current->next;
    }
    echo "null\n";
}
// 1 -> 2 -> 3 -> 4 -> 5 -> null

func printList(head *ListNode) {
    current := head
    for current != nil {
        fmt.Printf("%d -> ", current.Val)
        current = current.Next
    }
    fmt.Println("nil")
}
// 1 -> 2 -> 3 -> 4 -> 5 -> nil

static void PrintList(ListNode? head)
{
    var current = head;
    while (current is not null)
    {
        Console.Write($"{current.Val} -> ");
        current = current.Next;
    }
    Console.WriteLine("null");
}
// 1 -> 2 -> 3 -> 4 -> 5 -> null

def print_list(head: ListNode | None) -> None:
    parts: list[str] = []
    current = head
    while current is not None:
        parts.append(str(current.val))
        current = current.next
    print(" -> ".join([*parts, "None"]))

# 1 -> 2 -> 3 -> 4 -> 5 -> None

## Операции и их сложность

Операция	Сложность	Пояснение
Доступ по индексу	O(n)	Нужно пройти с начала
Поиск значения	O(n)	Линейный обход
Вставка в начало	O(1)	Просто перенаправить head
Вставка в конец	O(n)*	Нужно дойти до конца
Вставка после узла	O(1)	Перенаправить указатели
Удаление из начала	O(1)	Сдвинуть head
Удаление конкретного	O(n)	Нужно найти предыдущий
Длина	O(n)	Пройти весь список

* O(1) если хранить ссылку на tail

Вставка в начало — O(1)

function insertAtHead(?ListNode $head, int $val): ListNode
{
    $newNode = new ListNode($val);
    $newNode->next = $head;
    return $newNode; // New head
}

// Before: 1 -> 2 -> 3
// insertAtHead($head, 0)
// After:  0 -> 1 -> 2 -> 3

func insertAtHead(head *ListNode, val int) *ListNode {
    newNode := &ListNode{Val: val}
    newNode.Next = head
    return newNode // New head
}

// Before: 1 -> 2 -> 3
// insertAtHead(head, 0)
// After:  0 -> 1 -> 2 -> 3

static ListNode InsertAtHead(ListNode? head, int val)
{
    var newNode = new ListNode(val);
    newNode.Next = head;
    return newNode; // New head
}

// Before: 1 -> 2 -> 3
// InsertAtHead(head, 0)
// After:  0 -> 1 -> 2 -> 3

def insert_at_head(head: ListNode | None, val: int) -> ListNode:
    new_node = ListNode(val)
    new_node.next = head
    return new_node  # New head

# Before: 1 -> 2 -> 3
# insert_at_head(head, 0)
# After:  0 -> 1 -> 2 -> 3

Визуализация:

До:
head -> [1] -> [2] -> [3] -> null

Создаём новый узел:
[0] -> ???

Перенаправляем:
[0] -> [1] -> [2] -> [3] -> null
  ^
  head (новый)

Вставка в конец — O(n)

function insertAtTail(?ListNode $head, int $val): ListNode
{
    $newNode = new ListNode($val);
    if ($head === null) {
        return $newNode;
    }

    $current = $head;
    while ($current->next !== null) { // Go to last node
        $current = $current->next;
    }
    $current->next = $newNode; // Attach

    return $head;
}

func insertAtTail(head *ListNode, val int) *ListNode {
    newNode := &ListNode{Val: val}
    if head == nil {
        return newNode
    }

    current := head
    for current.Next != nil { // Go to last node
        current = current.Next
    }
    current.Next = newNode // Attach

    return head
}

static ListNode InsertAtTail(ListNode? head, int val)
{
    var newNode = new ListNode(val);
    if (head is null)
    {
        return newNode;
    }

    var current = head;
    while (current.Next is not null) // Go to last node
    {
        current = current.Next;
    }
    current.Next = newNode; // Attach

    return head;
}

def insert_at_tail(head: ListNode | None, val: int) -> ListNode:
    new_node = ListNode(val)
    if head is None:
        return new_node

    current = head
    while current.next is not None:  # Go to last node
        current = current.next
    current.next = new_node  # Attach

    return head

### Удаление узла по значению

function deleteNode(?ListNode $head, int $val): ?ListNode
{
    // If deleting head
    if ($head !== null && $head->val === $val) {
        return $head->next;
    }

    $current = $head;
    while ($current !== null && $current->next !== null) {
        if ($current->next->val === $val) {
            $current->next = $current->next->next; // Skip node
            return $head;
        }
        $current = $current->next;
    }

    return $head;
}

func deleteNode(head *ListNode, val int) *ListNode {
    // If deleting head
    if head != nil && head.Val == val {
        return head.Next
    }

    current := head
    for current != nil && current.Next != nil {
        if current.Next.Val == val {
            current.Next = current.Next.Next // Skip node
            return head
        }
        current = current.Next
    }

    return head
}

static ListNode? DeleteNode(ListNode? head, int val)
{
    // If deleting head
    if (head is not null && head.Val == val)
    {
        return head.Next;
    }

    var current = head;
    while (current?.Next is not null)
    {
        if (current.Next.Val == val)
        {
            current.Next = current.Next.Next; // Skip node
            return head;
        }
        current = current.Next;
    }

    return head;
}

def delete_node(head: ListNode | None, val: int) -> ListNode | None:
    # If deleting head
    if head is not None and head.val == val:
        return head.next

    current = head
    while current is not None and current.next is not None:
        if current.next.val == val:
            current.next = current.next.next  # Skip node
            return head
        current = current.next

    return head

Визуализация удаления:

До:  [1] -> [2] -> [3] -> [4] -> null
           удаляем ^

current = [1]
current->next = [2], [2]->val == 2

Перенаправляем:
[1] -> [3] -> [4] -> null
       ^
  current->next = current->next->next

Вставка после данного узла — O(1)

function insertAfter(ListNode $node, int $val): void
{
    $newNode = new ListNode($val);
    $newNode->next = $node->next;
    $node->next = $newNode;
}

func insertAfter(node *ListNode, val int) {
    newNode := &ListNode{Val: val}
    newNode.Next = node.Next
    node.Next = newNode
}

static void InsertAfter(ListNode node, int val)
{
    var newNode = new ListNode(val);
    newNode.Next = node.Next;
    node.Next = newNode;
}

def insert_after(node: ListNode, val: int) -> None:
    new_node = ListNode(val)
    new_node.next = node.next
    node.next = new_node

``` До: [A] -> [C] -> ... Вставляем B после A:

Шаг 1: newNode->next = A->next (= C) [A] -> [C] -> ... [B] -> [C]

Шаг 2: A->next = newNode [A] -> [B] -> [C] -> ...


## Техника Dummy Node

Dummy node (фиктивный узел) упрощает обработку **edge cases** с head.

<div class="code-group" data-languages="php,go,csharp,python"><div class="code-group-tabs"><button class="code-tab active" data-lang="php" data-index="0">PHP</button><button class="code-tab" data-lang="go" data-index="1">Go</button><button class="code-tab" data-lang="csharp" data-index="2">C#</button><button class="code-tab" data-lang="python" data-index="3">Python</button></div><div class="code-block" data-lang="php" data-index="0">

```php
function removeElements(?ListNode $head, int $val): ?ListNode
{
    // Remove ALL nodes with given value
    $dummy = new ListNode(0);    // Dummy node before head
    $dummy->next = $head;
    $current = $dummy;

    while ($current->next !== null) {
        if ($current->next->val === $val) {
            $current->next = $current->next->next;
        } else {
            $current = $current->next;
        }
    }

    return $dummy->next; // New head (may be null)
}

// Without dummy, we'd need to separately handle:
// - deleting head
// - deleting multiple heads in a row
// - empty list

func removeElements(head *ListNode, val int) *ListNode {
    // Remove ALL nodes with given value
    dummy := &ListNode{Next: head} // Dummy node before head
    current := dummy

    for current.Next != nil {
        if current.Next.Val == val {
            current.Next = current.Next.Next
        } else {
            current = current.Next
        }
    }

    return dummy.Next // New head (may be nil)
}

// Without dummy, we'd need to separately handle:
// - deleting head
// - deleting multiple heads in a row
// - empty list

static ListNode? RemoveElements(ListNode? head, int val)
{
    // Remove ALL nodes with given value
    var dummy = new ListNode(0, head); // Dummy node before head
    var current = dummy;

    while (current.Next is not null)
    {
        if (current.Next.Val == val)
        {
            current.Next = current.Next.Next;
        }
        else
        {
            current = current.Next;
        }
    }

    return dummy.Next; // New head (may be null)
}

// Without dummy, we'd need to separately handle:
// - deleting head
// - deleting multiple heads in a row
// - empty list

def remove_elements(head: ListNode | None, val: int) -> ListNode | None:
    # Remove ALL nodes with given value
    dummy = ListNode(0, head)  # Dummy node before head
    current = dummy

    while current.next is not None:
        if current.next.val == val:
            current.next = current.next.next
        else:
            current = current.next

    return dummy.next  # New head (may be None)

# Without dummy, we'd need to separately handle:
# - deleting head
# - deleting multiple heads in a row
# - empty list

## Разворот списка

Одна из самых классических задач на интервью.

function reverseList(?ListNode $head): ?ListNode
{
    $prev = null;
    $current = $head;

    while ($current !== null) {
        $nextTemp = $current->next;  // Save next
        $current->next = $prev;      // Reverse pointer
        $prev = $current;            // Move prev
        $current = $nextTemp;        // Move current
    }

    return $prev; // New head
}

// Steps for [1 -> 2 -> 3]:
// prev=null, curr=1
//   1->next=null, prev=1, curr=2     null <- 1   2 -> 3
// prev=1, curr=2
//   2->next=1, prev=2, curr=3        null <- 1 <- 2   3
// prev=2, curr=3
//   3->next=2, prev=3, curr=null     null <- 1 <- 2 <- 3
// return 3 (new head)

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    current := head

    for current != nil {
        nextTemp := current.Next  // Save next
        current.Next = prev       // Reverse pointer
        prev = current            // Move prev
        current = nextTemp        // Move current
    }

    return prev // New head
}

// Steps for [1 -> 2 -> 3]:
// prev=nil, curr=1
//   1.Next=nil, prev=1, curr=2      nil <- 1   2 -> 3
// prev=1, curr=2
//   2.Next=1, prev=2, curr=3        nil <- 1 <- 2   3
// prev=2, curr=3
//   3.Next=2, prev=3, curr=nil      nil <- 1 <- 2 <- 3
// return 3 (new head)

static ListNode? ReverseList(ListNode? head)
{
    ListNode? prev = null;
    var current = head;

    while (current is not null)
    {
        var nextTemp = current.Next; // Save next
        current.Next = prev;         // Reverse pointer
        prev = current;              // Move prev
        current = nextTemp;          // Move current
    }

    return prev; // New head
}

// Steps for [1 -> 2 -> 3]:
// prev=null, curr=1
//   1.Next=null, prev=1, curr=2     null <- 1   2 -> 3
// prev=1, curr=2
//   2.Next=1, prev=2, curr=3        null <- 1 <- 2   3
// prev=2, curr=3
//   3.Next=2, prev=3, curr=null     null <- 1 <- 2 <- 3
// return 3 (new head)

def reverse_list(head: ListNode | None) -> ListNode | None:
    prev: ListNode | None = None
    current = head

    while current is not None:
        # Tuple assignment: right side is evaluated first,
        # so all four moves happen in a single statement
        current.next, prev, current = prev, current, current.next

    return prev  # New head

# Steps for [1 -> 2 -> 3]:
# prev=None, curr=1
#   1.next=None, prev=1, curr=2     None <- 1   2 -> 3
# prev=1, curr=2
#   2.next=1, prev=2, curr=3        None <- 1 <- 2   3
# prev=2, curr=3
#   3.next=2, prev=3, curr=None     None <- 1 <- 2 <- 3
# return 3 (new head)

### Рекурсивный разворот

function reverseListRecursive(?ListNode $head): ?ListNode
{
    if ($head === null || $head->next === null) {
        return $head;
    }

    $newHead = reverseListRecursive($head->next);
    $head->next->next = $head;  // Reverse link
    $head->next = null;          // Old head becomes tail

    return $newHead;
}

func reverseListRecursive(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    newHead := reverseListRecursive(head.Next)
    head.Next.Next = head  // Reverse link
    head.Next = nil        // Old head becomes tail

    return newHead
}

static ListNode? ReverseListRecursive(ListNode? head)
{
    if (head?.Next is null)
    {
        return head;
    }

    var newHead = ReverseListRecursive(head.Next);
    head.Next.Next = head; // Reverse link
    head.Next = null;      // Old head becomes tail

    return newHead;
}

def reverse_list_recursive(head: ListNode | None) -> ListNode | None:
    if head is None or head.next is None:
        return head

    new_head = reverse_list_recursive(head.next)
    head.next.next = head  # Reverse link
    head.next = None       # Old head becomes tail

    return new_head

## Поиск середины списка

function findMiddle(?ListNode $head): ?ListNode
{
    $slow = $head;
    $fast = $head;

    while ($fast !== null && $fast->next !== null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
    }

    return $slow; // slow is at the middle
}

// [1, 2, 3, 4, 5]
// slow: 1, 2, 3    <- stops at 3
// fast: 1, 3, 5

// [1, 2, 3, 4]
// slow: 1, 2, 3    <- stops at 3 (second middle)
// fast: 1, 3, null

func findMiddle(head *ListNode) *ListNode {
    slow := head
    fast := head

    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    return slow // slow is at the middle
}

// [1, 2, 3, 4, 5]
// slow: 1, 2, 3    <- stops at 3
// fast: 1, 3, 5

// [1, 2, 3, 4]
// slow: 1, 2, 3    <- stops at 3 (second middle)
// fast: 1, 3, nil

static ListNode? FindMiddle(ListNode? head)
{
    var slow = head;
    var fast = head;

    while (fast?.Next is not null)
    {
        slow = slow!.Next;
        fast = fast.Next.Next;
    }

    return slow; // slow is at the middle
}

// [1, 2, 3, 4, 5]
// slow: 1, 2, 3    <- stops at 3
// fast: 1, 3, 5

// [1, 2, 3, 4]
// slow: 1, 2, 3    <- stops at 3 (second middle)
// fast: 1, 3, null

def find_middle(head: ListNode | None) -> ListNode | None:
    slow = head
    fast = head

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

    return slow  # slow is at the middle

# [1, 2, 3, 4, 5]
# slow: 1, 2, 3    <- stops at 3
# fast: 1, 3, 5

# [1, 2, 3, 4]
# slow: 1, 2, 3    <- stops at 3 (second middle)
# fast: 1, 3, None

## Сравнение с массивом

Операция	Массив	Связный список
Доступ по индексу	O(1)	O(n)
Вставка в начало	O(n)	O(1)
Вставка в конец	O(1)*	O(n)**
Вставка в середину	O(n)	O(1)***
Удаление из начала	O(n)	O(1)
Поиск	O(n)	O(n)
Память	Компактная	Больше (указатели)

* амортизированно; ** O(1) с tail; *** если есть ссылка на узел

Запомни: Связный список выигрывает у массива в операциях вставки/удаления в начале (O(1) vs O(n)). Проигрывает в доступе по индексу (O(n) vs O(1)). Используй dummy node для упрощения edge cases. Разворот списка — must-know для интервью.

Итоги

Узел = значение + ссылка на следующий
Вставка/удаление в начале — O(1), доступ по индексу — O(n)
Dummy node решает проблемы с edge cases (удаление head, пустой список)
Разворот списка: запомни паттерн prev/current/next
Поиск середины: fast/slow pointers