Перейти к содержанию

Связный список

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

Связный список (linked list) - это линейная структура данных, в которой каждый элемент представляет собой объект-узел, а сами узлы соединены между собой с помощью ссылок. Ссылка хранит адрес памяти следующего узла, благодаря чему из текущего узла можно перейти к следующему.

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

Определение связного списка и способ хранения

Как видно на рисунке выше, базовой единицей связного списка является объект узел (node). Каждый узел содержит две части данных: значение узла и ссылку на следующий узел.

  • Первый узел связного списка называется головным узлом, а последний - хвостовым узлом.
  • Хвостовой узел указывает на пустое значение, что в Java, C++ и Python обозначается как null , nullptr и None соответственно.
  • В языках, поддерживающих указатели, таких как C, C++, Go и Rust, упомянутую выше ссылку следует заменить на указатель.

Как показано в коде ниже, узел связного списка ListNode хранит не только значение, но и дополнительную ссылку (указатель). Поэтому при одинаковом объеме данных связный список занимает больше памяти, чем массив.

class ListNode:
    """Класс узла связного списка"""
    def __init__(self, val: int):
        self.val: int = val               # Значение узла
        self.next: ListNode | None = None # Ссылка на следующий узел

/* Структура узла связного списка */
struct ListNode {
    int val;         // Значение узла
    ListNode *next;  // Указатель на следующий узел
    ListNode(int x) : val(x), next(nullptr) {}  // Конструктор
};

/* Класс узла связного списка */
class ListNode {
    int val;        // Значение узла
    ListNode next;  // Ссылка на следующий узел
    ListNode(int x) { val = x; }  // Конструктор
}

/* Класс узла связного списка */
class ListNode(int x) {  // Конструктор
    int val = x;         // Значение узла
    ListNode? next;      // Ссылка на следующий узел
}

/* Структура узла связного списка */
type ListNode struct {
    Val  int       // Значение узла
    Next *ListNode // Указатель на следующий узел
}

// NewListNode Конструктор, создает новый узел
func NewListNode(val int) *ListNode {
    return &ListNode{
        Val:  val,
        Next: nil,
    }
}

/* Класс узла связного списка */
class ListNode {
    var val: Int // Значение узла
    var next: ListNode? // Ссылка на следующий узел

    init(x: Int) { // Конструктор
        val = x
    }
}

/* Класс узла связного списка */
class ListNode {
    constructor(val, next) {
        this.val = (val === undefined ? 0 : val);       // Значение узла
        this.next = (next === undefined ? null : next); // Ссылка на следующий узел
    }
}

/* Класс узла связного списка */
class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;        // Значение узла
        this.next = next === undefined ? null : next;  // Ссылка на следующий узел
    }
}

/* Класс узла связного списка */
class ListNode {
  int val; // Значение узла
  ListNode? next; // Ссылка на следующий узел
  ListNode(this.val, [this.next]); // Конструктор
}

use std::rc::Rc;
use std::cell::RefCell;
/* Класс узла связного списка */
#[derive(Debug)]
struct ListNode {
    val: i32, // Значение узла
    next: Option<Rc<RefCell<ListNode>>>, // Указатель на следующий узел
}

/* Структура узла связного списка */
typedef struct ListNode {
    int val;               // Значение узла
    struct ListNode *next; // Указатель на следующий узел
} ListNode;

/* Конструктор */
ListNode *newListNode(int val) {
    ListNode *node;
    node = (ListNode *) malloc(sizeof(ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

/* Класс узла связного списка */
// Конструктор
class ListNode(x: Int) {
    val _val: Int = x          // Значение узла
    val next: ListNode? = null // Ссылка на следующий узел
}

# Класс узла связного списка
class ListNode
  attr_accessor :val  # Значение узла
  attr_accessor :next # Ссылка на следующий узел

  def initialize(val=0, next_node=nil)
    @val = val
    @next = next_node
  end
end

Основные операции со связным списком

Инициализация связного списка

Построение связного списка состоит из двух шагов: сначала нужно инициализировать объекты всех узлов, затем установить ссылочные связи между ними. После завершения инициализации мы можем, начиная с головы списка, последовательно проходить все узлы по ссылке next.

linked_list.py
# Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4
# Инициализация отдельных узлов
n0 = ListNode(1)
n1 = ListNode(3)
n2 = ListNode(2)
n3 = ListNode(5)
n4 = ListNode(4)
# Построение ссылок между узлами
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4
linked_list.cpp
/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */
// Инициализация отдельных узлов
ListNode* n0 = new ListNode(1);
ListNode* n1 = new ListNode(3);
ListNode* n2 = new ListNode(2);
ListNode* n3 = new ListNode(5);
ListNode* n4 = new ListNode(4);
// Построение ссылок между узлами
n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;
linked_list.java
/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */
// Инициализация отдельных узлов
ListNode n0 = new ListNode(1);
ListNode n1 = new ListNode(3);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(5);
ListNode n4 = new ListNode(4);
// Построение ссылок между узлами
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
linked_list.cs
/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */
// Инициализация отдельных узлов
ListNode n0 = new(1);
ListNode n1 = new(3);
ListNode n2 = new(2);
ListNode n3 = new(5);
ListNode n4 = new(4);
// Построение ссылок между узлами
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
linked_list.go
/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */
// Инициализация отдельных узлов
n0 := NewListNode(1)
n1 := NewListNode(3)
n2 := NewListNode(2)
n3 := NewListNode(5)
n4 := NewListNode(4)
// Построение ссылок между узлами
n0.Next = n1
n1.Next = n2
n2.Next = n3
n3.Next = n4
linked_list.swift
/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */
// Инициализация отдельных узлов
let n0 = ListNode(x: 1)
let n1 = ListNode(x: 3)
let n2 = ListNode(x: 2)
let n3 = ListNode(x: 5)
let n4 = ListNode(x: 4)
// Построение ссылок между узлами
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4
linked_list.js
/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */
// Инициализация отдельных узлов
const n0 = new ListNode(1);
const n1 = new ListNode(3);
const n2 = new ListNode(2);
const n3 = new ListNode(5);
const n4 = new ListNode(4);
// Построение ссылок между узлами
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
linked_list.ts
/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */
// Инициализация отдельных узлов
const n0 = new ListNode(1);
const n1 = new ListNode(3);
const n2 = new ListNode(2);
const n3 = new ListNode(5);
const n4 = new ListNode(4);
// Построение ссылок между узлами
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
linked_list.dart
/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */\
// Инициализация отдельных узлов
ListNode n0 = ListNode(1);
ListNode n1 = ListNode(3);
ListNode n2 = ListNode(2);
ListNode n3 = ListNode(5);
ListNode n4 = ListNode(4);
// Построение ссылок между узлами
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
linked_list.rs
/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */
// Инициализация отдельных узлов
let n0 = Rc::new(RefCell::new(ListNode { val: 1, next: None }));
let n1 = Rc::new(RefCell::new(ListNode { val: 3, next: None }));
let n2 = Rc::new(RefCell::new(ListNode { val: 2, next: None }));
let n3 = Rc::new(RefCell::new(ListNode { val: 5, next: None }));
let n4 = Rc::new(RefCell::new(ListNode { val: 4, next: None }));

// Построение ссылок между узлами
n0.borrow_mut().next = Some(n1.clone());
n1.borrow_mut().next = Some(n2.clone());
n2.borrow_mut().next = Some(n3.clone());
n3.borrow_mut().next = Some(n4.clone());
linked_list.c
/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */
// Инициализация отдельных узлов
ListNode* n0 = newListNode(1);
ListNode* n1 = newListNode(3);
ListNode* n2 = newListNode(2);
ListNode* n3 = newListNode(5);
ListNode* n4 = newListNode(4);
// Построение ссылок между узлами
n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;
linked_list.kt
/* Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4 */
// Инициализация отдельных узлов
val n0 = ListNode(1)
val n1 = ListNode(3)
val n2 = ListNode(2)
val n3 = ListNode(5)
val n4 = ListNode(4)
// Построение ссылок между узлами
n0.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
linked_list.rb
# Инициализация связного списка 1 -> 3 -> 2 -> 5 -> 4
# Инициализация отдельных узлов
n0 = ListNode.new(1)
n1 = ListNode.new(3)
n2 = ListNode.new(2)
n3 = ListNode.new(5)
n4 = ListNode.new(4)
# Построение ссылок между узлами
n0.next = n1
n1.next = n2
n2.next = n3
n3.next = n4
Визуализация выполнения

https://pythontutor.com/render.html#code=class%20ListNode%3A%0A%20%20%20%20%22%22%22%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D1%8B%D0%B9%20%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA%D1%83%D0%B7%D0%B5%D0%BB%D0%BA%D0%BB%D0%B0%D1%81%D1%81%22%22%22%0A%20%20%20%20def%20__init__%28self%2C%20val%3A%20int%29%3A%0A%20%20%20%20%20%20%20%20self.val%3A%20int%20%3D%20val%20%20%23%20%D0%97%D0%BD%D0%B0%D1%87%D0%B5%D0%BD%D0%B8%D0%B5%20%D1%83%D0%B7%D0%BB%D0%B0%0A%20%20%20%20%20%20%20%20self.next%3A%20ListNode%20%7C%20None%20%3D%20None%20%20%23%20%D0%A1%D1%81%D1%8B%D0%BB%D0%BA%D0%B0%20%D0%BD%D0%B0%20%D1%81%D0%BB%D0%B5%D0%B4%D1%83%D1%8E%D1%89%D0%B8%D0%B9%20%D1%83%D0%B7%D0%B5%D0%BB%0A%0A%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%D0%98%D0%BD%D0%B8%D1%86%D0%B8%D0%B0%D0%BB%D0%B8%D0%B7%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D1%82%D1%8C%20%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D1%8B%D0%B9%20%D1%81%D0%BF%D0%B8%D1%81%D0%BE%D0%BA%201%20-%3E%203%20-%3E%202%20-%3E%205%20-%3E%204%0A%20%20%20%20%23%20%D0%98%D0%BD%D0%B8%D1%86%D0%B8%D0%B0%D0%BB%D0%B8%D0%B7%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D1%82%D1%8C%20%D0%BA%D0%B0%D0%B6%D0%B4%D1%8B%D0%B9%20%D1%83%D0%B7%D0%B5%D0%BB%0A%20%20%20%20n0%20%3D%20ListNode%281%29%0A%20%20%20%20n1%20%3D%20ListNode%283%29%0A%20%20%20%20n2%20%3D%20ListNode%282%29%0A%20%20%20%20n3%20%3D%20ListNode%285%29%0A%20%20%20%20n4%20%3D%20ListNode%284%29%0A%20%20%20%20%23%20%D0%9F%D0%BE%D1%81%D1%82%D1%80%D0%BE%D0%B8%D1%82%D1%8C%20%D1%81%D1%81%D1%8B%D0%BB%D0%BA%D0%B8%20%D0%BC%D0%B5%D0%B6%D0%B4%D1%83%20%D1%83%D0%B7%D0%BB%D0%B0%D0%BC%D0%B8%0A%20%20%20%20n0.next%20%3D%20n1%0A%20%20%20%20n1.next%20%3D%20n2%0A%20%20%20%20n2.next%20%3D%20n3%0A%20%20%20%20n3.next%20%3D%20n4&cumulative=false&curInstr=3&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false

Массив в целом - это одна переменная: например, массив nums содержит элементы nums[0] , nums[1] и т.д. Связный список же состоит из множества независимых объектов-узлов. Обычно в качестве обозначения всего связного списка используют головной узел. Например, в приведенном выше коде связный список можно обозначить как n0 .

Вставка узла

Вставить узел в связный список очень легко. Как показано на рисунке ниже, предположим, что мы хотим вставить новый узел P между двумя соседними узлами n0 и n1. Для этого нужно изменить всего две ссылки (указателя), а временная сложность будет равна \(O(1)\) .

Для сравнения: временная сложность вставки элемента в массив составляет \(O(n)\) , и при большом объеме данных это менее эффективно.

Пример вставки узла в связный список

[file]{linked_list}-[class]{}-[func]{insert}

Удаление узла

Как показано на рисунке ниже, удалить узел из связного списка тоже очень просто: нужно изменить всего одну ссылку (указатель).

Стоит отметить, что хотя после завершения операции удаления узел P все еще указывает на n1 , при обходе связного списка до P уже нельзя добраться. Это означает, что P фактически больше не принадлежит данному списку.

Удаление узла из связного списка

[file]{linked_list}-[class]{}-[func]{remove}

Доступ к узлу

Доступ к узлам в связном списке менее эффективен. Как уже обсуждалось в предыдущем разделе, к любому элементу массива можно обратиться за \(O(1)\) времени. Со связным списком это не так: программе нужно начать с головного узла и последовательно двигаться дальше, пока не будет найден целевой узел. То есть для доступа к \(i\) -му узлу списка нужно выполнить \(i - 1\) итераций, а временная сложность составляет \(O(n)\) .

[file]{linked_list}-[class]{}-[func]{access}

Поиск узла

Поиск узла заключается в обходе связного списка, нахождении узла со значением target и возврате его индекса в списке. Этот процесс тоже относится к линейному поиску. Код выглядит следующим образом:

[file]{linked_list}-[class]{}-[func]{find}

Сравнение массива и связного списка

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

Таблица   Сравнение эффективности массива и связного списка

Массив Связный список
Способ хранения Непрерывная область памяти Разрозненная область памяти
Расширение емкости Длина неизменяема Гибкое расширение
Эффективность памяти Элементы занимают меньше памяти, но возможны потери пространства Элементы занимают больше памяти
Доступ к элементу \(O(1)\) \(O(n)\)
Добавление элемента \(O(n)\) \(O(1)\)
Удаление элемента \(O(n)\) \(O(1)\)

Основные типы связных списков

Как показано на рисунке ниже, существует три распространенных типа связных списков.

  • Односвязный список: это обычный связный список, рассмотренный выше. Узел односвязного списка содержит значение и ссылку на следующий узел. Первый узел называется головным, последний - хвостовым, и хвост указывает на None .
  • Циклический список: если заставить хвостовой узел односвязного списка указывать на головной, то есть соединить хвост с головой, получится циклический список. В циклическом списке любой узел можно рассматривать как головной.
  • Двусвязный список: по сравнению с односвязным списком двусвязный хранит ссылки в двух направлениях. Определение узла двусвязного списка включает как ссылку на следующий узел, так и ссылку на предыдущий узел. По сравнению с односвязным списком двусвязный более гибок и позволяет обходить список в обе стороны, но за это приходится платить дополнительной памятью.
class ListNode:
    """Класс узла двусвязного списка"""
    def __init__(self, val: int):
        self.val: int = val                # Значение узла
        self.next: ListNode | None = None  # Ссылка на следующий узел
        self.prev: ListNode | None = None  # Ссылка на предыдущий узел

/* Структура узла двусвязного списка */
struct ListNode {
    int val;         // Значение узла
    ListNode *next;  // Указатель на следующий узел
    ListNode *prev;  // Указатель на предыдущий узел
    ListNode(int x) : val(x), next(nullptr), prev(nullptr) {}  // Конструктор
};

/* Класс узла двусвязного списка */
class ListNode {
    int val;        // Значение узла
    ListNode next;  // Ссылка на следующий узел
    ListNode prev;  // Ссылка на предыдущий узел
    ListNode(int x) { val = x; }  // Конструктор
}

/* Класс узла двусвязного списка */
class ListNode(int x) {  // Конструктор
    int val = x;    // Значение узла
    ListNode next;  // Ссылка на следующий узел
    ListNode prev;  // Ссылка на предыдущий узел
}

/* Структура узла двусвязного списка */
type DoublyListNode struct {
    Val  int             // Значение узла
    Next *DoublyListNode // Указатель на следующий узел
    Prev *DoublyListNode // Указатель на предыдущий узел
}

// NewDoublyListNode Инициализация
func NewDoublyListNode(val int) *DoublyListNode {
    return &DoublyListNode{
        Val:  val,
        Next: nil,
        Prev: nil,
    }
}

/* Класс узла двусвязного списка */
class ListNode {
    var val: Int // Значение узла
    var next: ListNode? // Ссылка на следующий узел
    var prev: ListNode? // Ссылка на предыдущий узел

    init(x: Int) { // Конструктор
        val = x
    }
}

/* Класс узла двусвязного списка */
class ListNode {
    constructor(val, next, prev) {
        this.val = val  ===  undefined ? 0 : val;        // Значение узла
        this.next = next  ===  undefined ? null : next;  // Ссылка на следующий узел
        this.prev = prev  ===  undefined ? null : prev;  // Ссылка на предыдущий узел
    }
}

/* Класс узла двусвязного списка */
class ListNode {
    val: number;
    next: ListNode | null;
    prev: ListNode | null;
    constructor(val?: number, next?: ListNode | null, prev?: ListNode | null) {
        this.val = val  ===  undefined ? 0 : val;        // Значение узла
        this.next = next  ===  undefined ? null : next;  // Ссылка на следующий узел
        this.prev = prev  ===  undefined ? null : prev;  // Ссылка на предыдущий узел
    }
}

/* Класс узла двусвязного списка */
class ListNode {
    int val;        // Значение узла
    ListNode? next;  // Ссылка на следующий узел
    ListNode? prev;  // Ссылка на предыдущий узел
    ListNode(this.val, [this.next, this.prev]);  // Конструктор
}

use std::rc::Rc;
use std::cell::RefCell;

/* Тип узла двусвязного списка */
#[derive(Debug)]
struct ListNode {
    val: i32, // Значение узла
    next: Option<Rc<RefCell<ListNode>>>, // Указатель на следующий узел
    prev: Option<Rc<RefCell<ListNode>>>, // Указатель на предыдущий узел
}

/* Конструктор */
impl ListNode {
    fn new(val: i32) -> Self {
        ListNode {
            val,
            next: None,
            prev: None,
        }
    }
}

/* Структура узла двусвязного списка */
typedef struct ListNode {
    int val;               // Значение узла
    struct ListNode *next; // Указатель на следующий узел
    struct ListNode *prev; // Указатель на предыдущий узел
} ListNode;

/* Конструктор */
ListNode *newListNode(int val) {
    ListNode *node;
    node = (ListNode *) malloc(sizeof(ListNode));
    node->val = val;
    node->next = NULL;
    node->prev = NULL;
    return node;
}

/* Класс узла двусвязного списка */
// Конструктор
class ListNode(x: Int) {
    val _val: Int = x           // Значение узла
    val next: ListNode? = null  // Ссылка на следующий узел
    val prev: ListNode? = null  // Ссылка на предыдущий узел
}

# Класс узла двусвязного списка
class ListNode
  attr_accessor :val    # Значение узла
  attr_accessor :next   # Ссылка на следующий узел
  attr_accessor :prev   # Ссылка на предыдущий узел

  def initialize(val=0, next_node=nil, prev_node=nil)
    @val = val
    @next = next_node
    @prev = prev_node
  end
end

Распространенные типы связных списков

Типичные применения связных списков

Односвязные списки обычно используются для реализации стеков, очередей, хеш-таблиц и графов.

  • Стеки и очереди: если операции вставки и удаления выполняются на одном конце связного списка, он проявляет свойства LIFO, соответствующие стеку. Если вставка происходит на одном конце, а удаление на другом, он проявляет свойства FIFO, соответствующие очереди.
  • Хеш-таблицы: метод цепочек - один из основных способов разрешения коллизий в хеш-таблицах. В этом подходе все конфликтующие элементы помещаются в связный список.
  • Графы: список смежности - это распространенный способ представления графа, при котором каждой вершине графа соответствует связный список, а каждый элемент этого списка представляет другую вершину, соединенную с данной.

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

  • Продвинутые структуры данных: например, в красно-черных деревьях и B-деревьях нам нужен доступ к родительскому узлу. Этого можно добиться, сохранив в узле ссылку на родителя, по аналогии с двусвязным списком.
  • История браузера: когда пользователь в браузере нажимает кнопки «вперед» или «назад», браузеру нужно знать предыдущую и следующую посещенные страницы. Свойства двусвязного списка делают такую операцию простой.
  • Алгоритм LRU: в алгоритмах вытеснения из кэша (LRU) нужно быстро находить наименее недавно использованные данные, а также быстро добавлять и удалять узлы. Для этого двусвязный список подходит очень хорошо.

Циклические списки часто применяются в сценариях, требующих циклических операций, например при планировании ресурсов в операционной системе.

  • Алгоритм циклического распределения кванта времени: в операционных системах round-robin scheduling - это распространенный алгоритм планирования CPU, который циклически обходит набор процессов. Каждому процессу выделяется квант времени, и когда он исчерпан, CPU переключается на следующий процесс. Такую циклическую операцию удобно реализовать с помощью кольцевого списка.
  • Буферы данных: в некоторых реализациях буферов данных также могут использоваться циклические списки. Например, в аудио- и видеоплеерах поток данных может делиться на несколько буферных блоков и помещаться в кольцевой список для обеспечения непрерывного воспроизведения.