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

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

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

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

Рисунок 4-5 Определение и способ хранения связного списка

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

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

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

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

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          // Значение узла
    var 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

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

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

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

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

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

Визуализация выполнения

Во весь экран >

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

2. Вставка узла¶

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

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

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

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

linked_list.py

def insert(n0: ListNode, P: ListNode):
    """Вставка узла P в связный список после узла n0"""
    n1 = n0.next
    P.next = n1
    n0.next = P

linked_list.cpp

/* Вставка узла P в связный список после узла n0 */
void insert(ListNode *n0, ListNode *P) {
    ListNode *n1 = n0->next;
    P->next = n1;
    n0->next = P;
}

linked_list.java

/* Вставка узла P в связный список после узла n0 */
void insert(ListNode n0, ListNode P) {
    ListNode n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

linked_list.cs

/* Вставка узла P в связный список после узла n0 */
void Insert(ListNode n0, ListNode P) {
    ListNode? n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

linked_list.go

/* Вставка узла P в связный список после узла n0 */
func insertNode(n0 *ListNode, P *ListNode) {
    n1 := n0.Next
    P.Next = n1
    n0.Next = P
}

linked_list.swift

/* Вставка узла P в связный список после узла n0 */
func insert(n0: ListNode, P: ListNode) {
    let n1 = n0.next
    P.next = n1
    n0.next = P
}

linked_list.js

/* Вставка узла P в связный список после узла n0 */
function insert(n0, P) {
    const n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

linked_list.ts

/* Вставка узла P в связный список после узла n0 */
function insert(n0: ListNode, P: ListNode): void {
    const n1 = n0.next;
    P.next = n1;
    n0.next = P;
}

linked_list.dart

/* Вставка узла P в связный список после узла n0 */
void insert(ListNode n0, ListNode P) {
  ListNode? n1 = n0.next;
  P.next = n1;
  n0.next = P;
}

linked_list.rs

/* Вставка узла P в связный список после узла n0 */
#[allow(non_snake_case)]
pub fn insert<T>(n0: &Rc<RefCell<ListNode<T>>>, P: Rc<RefCell<ListNode<T>>>) {
    let n1 = n0.borrow_mut().next.take();
    P.borrow_mut().next = n1;
    n0.borrow_mut().next = Some(P);
}

linked_list.c

/* Вставка узла P в связный список после узла n0 */
void insert(ListNode *n0, ListNode *P) {
    ListNode *n1 = n0->next;
    P->next = n1;
    n0->next = P;
}

linked_list.kt

/* Вставка узла P в связный список после узла n0 */
fun insert(n0: ListNode?, p: ListNode?) {
    val n1 = n0?.next
    p?.next = n1
    n0?.next = p
}

linked_list.rb

### Вставка узла _p в связный список после узла n0 ###
# В Ruby `p` является встроенной функцией, а `P` — константой, поэтому вместо них можно использовать `_p`
def insert(n0, _p)
  n1 = n0.next
  _p.next = n1
  n0.next = _p
end

Визуализация кода

Во весь экран >

3. Удаление узла¶

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

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

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

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

linked_list.py

def remove(n0: ListNode):
    """Удаление первого узла после узла n0 из связного списка"""
    if not n0.next:
        return
    # n0 -> P -> n1
    P = n0.next
    n1 = P.next
    n0.next = n1

linked_list.cpp

/* Удаление первого узла после узла n0 из связного списка */
void remove(ListNode *n0) {
    if (n0->next == nullptr)
        return;
    // n0 -> P -> n1
    ListNode *P = n0->next;
    ListNode *n1 = P->next;
    n0->next = n1;
    // Освободить память
    delete P;
}

linked_list.java

/* Удаление первого узла после узла n0 из связного списка */
void remove(ListNode n0) {
    if (n0.next == null)
        return;
    // n0 -> P -> n1
    ListNode P = n0.next;
    ListNode n1 = P.next;
    n0.next = n1;
}

linked_list.cs

/* Удаление первого узла после узла n0 из связного списка */
void Remove(ListNode n0) {
    if (n0.next == null)
        return;
    // n0 -> P -> n1
    ListNode P = n0.next;
    ListNode? n1 = P.next;
    n0.next = n1;
}

linked_list.go

/* Удаление первого узла после узла n0 из связного списка */
func removeItem(n0 *ListNode) {
    if n0.Next == nil {
        return
    }
    // n0 -> P -> n1
    P := n0.Next
    n1 := P.Next
    n0.Next = n1
}

linked_list.swift

/* Удаление первого узла после узла n0 из связного списка */
func remove(n0: ListNode) {
    if n0.next == nil {
        return
    }
    // n0 -> P -> n1
    let P = n0.next
    let n1 = P?.next
    n0.next = n1
}

linked_list.js

/* Удаление первого узла после узла n0 из связного списка */
function remove(n0) {
    if (!n0.next) return;
    // n0 -> P -> n1
    const P = n0.next;
    const n1 = P.next;
    n0.next = n1;
}

linked_list.ts

/* Удаление первого узла после узла n0 из связного списка */
function remove(n0: ListNode): void {
    if (!n0.next) {
        return;
    }
    // n0 -> P -> n1
    const P = n0.next;
    const n1 = P.next;
    n0.next = n1;
}

linked_list.dart

/* Удаление первого узла после узла n0 из связного списка */
void remove(ListNode n0) {
  if (n0.next == null) return;
  // n0 -> P -> n1
  ListNode P = n0.next!;
  ListNode? n1 = P.next;
  n0.next = n1;
}

linked_list.rs

/* Удаление первого узла после узла n0 из связного списка */
#[allow(non_snake_case)]
pub fn remove<T>(n0: &Rc<RefCell<ListNode<T>>>) {
    // n0 -> P -> n1
    let P = n0.borrow_mut().next.take();
    if let Some(node) = P {
        let n1 = node.borrow_mut().next.take();
        n0.borrow_mut().next = n1;
    }
}

linked_list.c

/* Удаление первого узла после узла n0 из связного списка */
// Внимание: stdio.h уже использует ключевое слово remove
void removeItem(ListNode *n0) {
    if (!n0->next)
        return;
    // n0 -> P -> n1
    ListNode *P = n0->next;
    ListNode *n1 = P->next;
    n0->next = n1;
    // Освободить память
    free(P);
}

linked_list.kt

/* Удаление первого узла после узла n0 из связного списка */
fun remove(n0: ListNode?) {
    if (n0?.next == null)
        return
    // n0 -> P -> n1
    val p = n0.next
    val n1 = p?.next
    n0.next = n1
}

linked_list.rb

### Удаление первого узла после узла n0 из связного списка ###
def remove(n0)
  return if n0.next.nil?

  # n0 -> remove_node -> n1
  remove_node = n0.next
  n1 = remove_node.next
  n0.next = n1
end

Визуализация кода

Во весь экран >

4. Доступ к узлу¶

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

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

linked_list.py

def access(head: ListNode, index: int) -> ListNode | None:
    """Доступ к узлу с индексом index в связном списке"""
    for _ in range(index):
        if not head:
            return None
        head = head.next
    return head

linked_list.cpp

/* Доступ к узлу с индексом index в связном списке */
ListNode *access(ListNode *head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == nullptr)
            return nullptr;
        head = head->next;
    }
    return head;
}

linked_list.java

/* Доступ к узлу с индексом index в связном списке */
ListNode access(ListNode head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == null)
            return null;
        head = head.next;
    }
    return head;
}

linked_list.cs

/* Доступ к узлу с индексом index в связном списке */
ListNode? Access(ListNode? head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == null)
            return null;
        head = head.next;
    }
    return head;
}

linked_list.go

/* Доступ к узлу с индексом index в связном списке */
func access(head *ListNode, index int) *ListNode {
    for i := 0; i < index; i++ {
        if head == nil {
            return nil
        }
        head = head.Next
    }
    return head
}

linked_list.swift

/* Доступ к узлу с индексом index в связном списке */
func access(head: ListNode, index: Int) -> ListNode? {
    var head: ListNode? = head
    for _ in 0 ..< index {
        if head == nil {
            return nil
        }
        head = head?.next
    }
    return head
}

linked_list.js

/* Доступ к узлу с индексом index в связном списке */
function access(head, index) {
    for (let i = 0; i < index; i++) {
        if (!head) {
            return null;
        }
        head = head.next;
    }
    return head;
}

linked_list.ts

/* Доступ к узлу с индексом index в связном списке */
function access(head: ListNode | null, index: number): ListNode | null {
    for (let i = 0; i < index; i++) {
        if (!head) {
            return null;
        }
        head = head.next;
    }
    return head;
}

linked_list.dart

/* Доступ к узлу с индексом index в связном списке */
ListNode? access(ListNode? head, int index) {
  for (var i = 0; i < index; i++) {
    if (head == null) return null;
    head = head.next;
  }
  return head;
}

linked_list.rs

/* Доступ к узлу с индексом index в связном списке */
pub fn access<T>(head: Rc<RefCell<ListNode<T>>>, index: i32) -> Option<Rc<RefCell<ListNode<T>>>> {
    fn dfs<T>(
        head: Option<&Rc<RefCell<ListNode<T>>>>,
        index: i32,
    ) -> Option<Rc<RefCell<ListNode<T>>>> {
        if index <= 0 {
            return head.cloned();
        }

        if let Some(node) = head {
            dfs(node.borrow().next.as_ref(), index - 1)
        } else {
            None
        }
    }

    dfs(Some(head).as_ref(), index)
}

linked_list.c

/* Доступ к узлу с индексом index в связном списке */
ListNode *access(ListNode *head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == NULL)
            return NULL;
        head = head->next;
    }
    return head;
}

linked_list.kt

/* Доступ к узлу с индексом index в связном списке */
fun access(head: ListNode?, index: Int): ListNode? {
    var h = head
    for (i in 0..<index) {
        if (h == null)
            return null
        h = h.next
    }
    return h
}

linked_list.rb

### Доступ к узлу с индексом index в связном списке ###
def access(head, index)
  for i in 0...index
    return nil if head.nil?
    head = head.next
  end

  head
end

Визуализация кода

Во весь экран >

5. Поиск узла¶

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

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

linked_list.py

def find(head: ListNode, target: int) -> int:
    """Поиск первого узла со значением target в связном списке"""
    index = 0
    while head:
        if head.val == target:
            return index
        head = head.next
        index += 1
    return -1

linked_list.cpp

/* Поиск первого узла со значением target в связном списке */
int find(ListNode *head, int target) {
    int index = 0;
    while (head != nullptr) {
        if (head->val == target)
            return index;
        head = head->next;
        index++;
    }
    return -1;
}

linked_list.java

/* Поиск первого узла со значением target в связном списке */
int find(ListNode head, int target) {
    int index = 0;
    while (head != null) {
        if (head.val == target)
            return index;
        head = head.next;
        index++;
    }
    return -1;
}

linked_list.cs

/* Поиск первого узла со значением target в связном списке */
int Find(ListNode? head, int target) {
    int index = 0;
    while (head != null) {
        if (head.val == target)
            return index;
        head = head.next;
        index++;
    }
    return -1;
}

linked_list.go

/* Поиск первого узла со значением target в связном списке */
func findNode(head *ListNode, target int) int {
    index := 0
    for head != nil {
        if head.Val == target {
            return index
        }
        head = head.Next
        index++
    }
    return -1
}

linked_list.swift

/* Поиск первого узла со значением target в связном списке */
func find(head: ListNode, target: Int) -> Int {
    var head: ListNode? = head
    var index = 0
    while head != nil {
        if head?.val == target {
            return index
        }
        head = head?.next
        index += 1
    }
    return -1
}

linked_list.js

/* Поиск первого узла со значением target в связном списке */
function find(head, target) {
    let index = 0;
    while (head !== null) {
        if (head.val === target) {
            return index;
        }
        head = head.next;
        index += 1;
    }
    return -1;
}

linked_list.ts

/* Поиск первого узла со значением target в связном списке */
function find(head: ListNode | null, target: number): number {
    let index = 0;
    while (head !== null) {
        if (head.val === target) {
            return index;
        }
        head = head.next;
        index += 1;
    }
    return -1;
}

linked_list.dart

/* Поиск первого узла со значением target в связном списке */
int find(ListNode? head, int target) {
  int index = 0;
  while (head != null) {
    if (head.val == target) {
      return index;
    }
    head = head.next;
    index++;
  }
  return -1;
}

linked_list.rs

/* Поиск первого узла со значением target в связном списке */
pub fn find<T: PartialEq>(head: Rc<RefCell<ListNode<T>>>, target: T) -> i32 {
    fn find<T: PartialEq>(head: Option<&Rc<RefCell<ListNode<T>>>>, target: T, idx: i32) -> i32 {
        if let Some(node) = head {
            if node.borrow().val == target {
                return idx;
            }
            return find(node.borrow().next.as_ref(), target, idx + 1);
        } else {
            -1
        }
    }

    find(Some(head).as_ref(), target, 0)
}

linked_list.c

/* Поиск первого узла со значением target в связном списке */
int find(ListNode *head, int target) {
    int index = 0;
    while (head) {
        if (head->val == target)
            return index;
        head = head->next;
        index++;
    }
    return -1;
}

linked_list.kt

/* Поиск первого узла со значением target в связном списке */
fun find(head: ListNode?, target: Int): Int {
    var index = 0
    var h = head
    while (h != null) {
        if (h._val == target)
            return index
        h = h.next
        index++
    }
    return -1
}

linked_list.rb

### Поиск первого узла со значением target в связном списке ###
def find(head, target)
  index = 0
  while head
    return index if head.val == target
    head = head.next
    index += 1
  end

  -1
end

Визуализация кода

Во весь экран >

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

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

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

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

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

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

Односвязный список: это обычный связный список, рассмотренный выше. Узел односвязного списка содержит значение и ссылку на следующий узел. Первый узел называется головным, последний - хвостовым, и хвост указывает на None .
Кольцевой (циклический) список: если заставить хвостовой узел односвязного списка указывать на головной, то есть соединить хвост с головой, получится циклический список. В циклическом списке любой узел можно рассматривать как головной.
Двусвязный список: по сравнению с односвязным списком двусвязный хранит ссылки в двух направлениях. Определение узла двусвязного списка включает как ссылку на следующий узел, так и ссылку на предыдущий узел. По сравнению с односвязным списком двусвязный более гибок и позволяет обходить список в обе стороны, но за это приходится платить дополнительной памятью.

PythonC++JavaC#GoSwiftJSTSDartRustCKotlinRuby

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           // Значение узла
    var next: ListNode? = null  // Ссылка на следующий узел
    var 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

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

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

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

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

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

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

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

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

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

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

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

2. Вставка узла¶

3. Удаление узла¶

4. Доступ к узлу¶

5. Поиск узла¶

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

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

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

Оставляйте свои идеи, вопросы и предложения в комментариях