Свързан списък в C#

Проблем

Опашката, която спира изпращането

Сървърът изпраща имейли от опашка. Новите влизат отзад, спешните (смяна на парола) отпред, а работникът взима винаги първия. Кодът ползва обикновения списък:

var emails = new List<string>();
emails.Add("фактура");
emails.Add("бюлетин");
emails.Add("отчет");
emails.Insert(0, "парола");
string next = emails[0];
emails.RemoveAt(0);
Console.WriteLine("Изпращам: " + next);
Console.WriteLine("Остават: " + string.Join(", ", emails));

Изпращам: парола
Остават: фактура, бюлетин, отчет

В понеделник сутрин бюлетинът за всички клиенти пълни опашката със 100 000 имейла. Работникът изпраща по-бавно от обикновено, после почти спира, а имейлите за смяна на парола закъсняват с минути.

Причината: списъкът е динамичен масив. Взимането на първия мести всички останали с едно място напред, а спешният отпред мести всички назад. Да изпратиш 100 000 имейла един след друг са 99 999 + 99 998 + … + 1 = 4 999 950 000 премествания, само за да вземеш първия.

Идеята

Възли, head и tail

Възелът и вмъкването отпред вече ги видя в урока „Стек, опашка и свързан списък“: всеки елемент е отделен обект със стойност и стрелка Next към следващия. Тук правиш целия клас и смяташ колко струва всяка операция.

Списъкът пази три неща:

head: първият възел. Оттам почва всяко обхождане.
tail: последният възел. С него добавянето в края не минава през целия списък.
размерът, за да не се брои всеки път.

Двата края трябва да са верни след всяка операция. Празният списък има head и tail null. Списък с един възел има head и tail, които сочат същия възел. Почти всяка грешка в свързан списък е забравен край: махаш последния, а tail още сочи него.

Виж го

Свой свързан списък

Ето целия клас. Възлите не се местят никога: всяка операция сменя само стрелки.

class Node
{
    public string Value;
    public Node Next;

    public Node(string value)
    {
        Value = value;
    }
}

class SimpleLinkedList
{
    private Node head;
    private Node tail;
    private int size;

    public int Count => size;

    public void AddFirst(string value)
    {
        var node = new Node(value);
        node.Next = head;
        head = node;
        if (tail == null)
        {
            tail = node;
        }
        size++;
    }

    public void AddLast(string value)
    {
        var node = new Node(value);
        if (tail == null)
        {
            head = node;
        }
        else
        {
            tail.Next = node;
        }
        tail = node;
        size++;
    }

    public string RemoveFirst()
    {
        if (head == null)
        {
            throw new InvalidOperationException("списъкът е празен");
        }
        string value = head.Value;
        head = head.Next;
        if (head == null)
        {
            tail = null;
        }
        size--;
        return value;
    }

    public bool Remove(string value)
    {
        Node prev = null;
        Node n = head;
        while (n != null && n.Value != value)
        {
            prev = n;
            n = n.Next;
        }
        if (n == null)
        {
            return false;
        }
        if (prev == null)
        {
            head = n.Next;
        }
        else
        {
            prev.Next = n.Next;
        }
        if (n == tail)
        {
            tail = prev;
        }
        size--;
        return true;
    }

    public int Find(string value)
    {
        int index = 0;
        for (Node n = head; n != null; n = n.Next)
        {
            if (n.Value == value)
            {
                return index;
            }
            index++;
        }
        return -1;
    }

    public string Get(int index)
    {
        if (index < 0 || index >= size)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
        Node n = head;
        for (int i = 0; i < index; i++)
        {
            n = n.Next;
        }
        return n.Value;
    }

    public override string ToString()
    {
        var values = new List<string>();
        for (Node n = head; n != null; n = n.Next)
        {
            values.Add(n.Value);
        }
        return string.Join(" → ", values);
    }
}

Гледай кои стрелки се сменят при всяка операция:

class Node
{
    public string Value;
    public Node Next;

    public Node(string value)
    {
        Value = value;
    }
}

private Node head;
private Node tail;
private int size;

public string RemoveFirst()
{
    if (head == null)
    {
        throw new InvalidOperationException("списъкът е празен");
    }
    string value = head.Value;
    head = head.Next;
    if (head == null)
    {
        tail = null;
    }
    size--;
    return value;
}

public bool Remove(string value)
{
    Node prev = null;
    Node n = head;
    while (n != null && n.Value != value)
    {
        prev = n;
        n = n.Next;
    }
    if (n == null)
    {
        return false;
    }
    if (prev == null)
    {
        head = n.Next;
    }
    else
    {
        prev.Next = n.Next;
    }
    if (n == tail)
    {
        tail = prev;
    }
    size--;
    return true;
}

Стъпка по стъпка, с думи

Три имейла, всеки в свой възел: стойността и Next, стрелката към следващия. head сочи първия, tail последния.
AddFirst(„парола“): нов възел, неговият Next сочи стария първи, и head минава на него. Две стрелки, нищо не се мести: O(1).
AddLast(„покана“): tail вече знае последния, затова не се минава по списъка. Неговият Next сочи новия, и tail се мести: O(1).
RemoveFirst(): head минава на следващия възел. Към „парола“ вече не сочи нищо, и паметта му се освобождава сама.
Remove(„бюлетин“): възлите нямат индекс. n тръгва от head и върви, докато го намери; prev остава един възел назад. Това е O(n).
prev.Next = n.Next: една стрелка заобикаля „бюлетин“. „отчет“ и „покана“ не помръдват.
В краищата: две стрелки, O(1). По средата: една стрелка, но до мястото се стига стъпка по стъпка, O(n).

var emails = new SimpleLinkedList();
emails.AddLast("фактура");
emails.AddLast("бюлетин");
emails.AddLast("отчет");
emails.AddFirst("парола");
emails.AddLast("покана");
Console.WriteLine(emails);
Console.WriteLine("Изпращам: " + emails.RemoveFirst());
emails.Remove("бюлетин");
Console.WriteLine(emails);
Console.WriteLine("Място на отчет: " + emails.Find("отчет"));
Console.WriteLine("Имейли: " + emails.Count);

парола → фактура → бюлетин → отчет → покана
Изпращам: парола
фактура → отчет → покана
Място на отчет: 1
Имейли: 3

RemoveFirst на празен списък хвърля InvalidOperationException, както LinkedList<T>.RemoveFirst. ToString с override е това, което Console.WriteLine(emails) печата. Get е метод, а не индексатор [i]: така се вижда, че стига до елемента стъпка по стъпка. Затова и LinkedList<T> няма индексатор.

Пробвай

Предвиди изхода

Седем операции подред. Внимавай кой е последният след махането:

class Node
{
    public string Value;
    public Node Next;

    public Node(string value)
    {
        Value = value;
    }
}

class SimpleLinkedList
{
    private Node head;
    private Node tail;
    private int size;

    public int Count => size;

    public void AddFirst(string value)
    {
        var node = new Node(value);
        node.Next = head;
        head = node;
        if (tail == null)
        {
            tail = node;
        }
        size++;
    }

    public void AddLast(string value)
    {
        var node = new Node(value);
        if (tail == null)
        {
            head = node;
        }
        else
        {
            tail.Next = node;
        }
        tail = node;
        size++;
    }

    public string RemoveFirst()
    {
        if (head == null)
        {
            throw new InvalidOperationException("списъкът е празен");
        }
        string value = head.Value;
        head = head.Next;
        if (head == null)
        {
            tail = null;
        }
        size--;
        return value;
    }

    public bool Remove(string value)
    {
        Node prev = null;
        Node n = head;
        while (n != null && n.Value != value)
        {
            prev = n;
            n = n.Next;
        }
        if (n == null)
        {
            return false;
        }
        if (prev == null)
        {
            head = n.Next;
        }
        else
        {
            prev.Next = n.Next;
        }
        if (n == tail)
        {
            tail = prev;
        }
        size--;
        return true;
    }

    public int Find(string value)
    {
        int index = 0;
        for (Node n = head; n != null; n = n.Next)
        {
            if (n.Value == value)
            {
                return index;
            }
            index++;
        }
        return -1;
    }

    public string Get(int index)
    {
        if (index < 0 || index >= size)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
        Node n = head;
        for (int i = 0; i < index; i++)
        {
            n = n.Next;
        }
        return n.Value;
    }

    public override string ToString()
    {
        var values = new List<string>();
        for (Node n = head; n != null; n = n.Next)
        {
            values.Add(n.Value);
        }
        return string.Join(" → ", values);
    }
}

var emails = new SimpleLinkedList();
emails.AddFirst("отчет");
emails.AddFirst("фактура");
emails.AddLast("покана");
emails.RemoveFirst();
emails.AddFirst("парола");
emails.Remove("покана");
emails.AddLast("бюлетин");
Console.WriteLine(emails);
Console.WriteLine("Имейли: " + emails.Count);

Отговор

парола → отчет
Имейли: 3

парола → отчет → бюлетин
Имейли: 3

парола → отчет → покана → бюлетин
Имейли: 4

Идеята

Кое колко струва: масив срещу свързан списък

Операция	Динамичен масив	Свързан списък
четене по индекс	O(1)	O(n)
добавяне отпред	O(n)	O(1)
добавяне отзад	O(1) амортизирано	O(1) с tail
махане на първия	O(n)	O(1)
махане на последния	O(1)	O(n), двусвързан: O(1)
по средата	O(n): местене	O(n): ходене до мястото

Последният ред е капанът. Самото пренасочване по средата е O(1), но до мястото се стига от head, стъпка по стъпка. Свързаният списък печели по средата само ако вече държиш възела, например защото току-що си го намерил с hash таблица.

Има и цена в паметта. Масивът пази стойностите (или референциите) една до друга. Всеки възел е отделен обект: стойността, стрелката и заглавката, която средата пази за всеки обект. При малки стойности възелът заема няколко пъти повече памет от мястото в масива.

Виж го

Измери го

Вмъкване отпред: динамичният масив от предишния урок срещу свързания списък. Броим записите на елементи: при масива новия и всяко преместване, при списъка само новия възел. Стрелките, които се сменят, са две за всяко вмъкване и не растат с n.

Вмъкване отпред O(n²)
Свързан списък: отпред O(n)

Алгоритъм	n = 10	n = 1000	n = 10 000	n = 100 000
Вмъкване отпред	63	501 516	50 021 376	≈ 5 002 137 600
Свързан списък: отпред	10	1000	10 000	100 000

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

class Node
{
    public string Value;
    public Node Next;

    public Node(string value)
    {
        Value = value;
    }
}

class SimpleLinkedList
{
    private Node head;
    private Node tail;
    private int size;

    public int Count => size;

    public void AddFirst(string value)
    {
        var node = new Node(value);
        node.Next = head;
        head = node;
        if (tail == null)
        {
            tail = node;
        }
        size++;
    }

    public void AddLast(string value)
    {
        var node = new Node(value);
        if (tail == null)
        {
            head = node;
        }
        else
        {
            tail.Next = node;
        }
        tail = node;
        size++;
    }

    public string RemoveFirst()
    {
        if (head == null)
        {
            throw new InvalidOperationException("списъкът е празен");
        }
        string value = head.Value;
        head = head.Next;
        if (head == null)
        {
            tail = null;
        }
        size--;
        return value;
    }

    public bool Remove(string value)
    {
        Node prev = null;
        Node n = head;
        while (n != null && n.Value != value)
        {
            prev = n;
            n = n.Next;
        }
        if (n == null)
        {
            return false;
        }
        if (prev == null)
        {
            head = n.Next;
        }
        else
        {
            prev.Next = n.Next;
        }
        if (n == tail)
        {
            tail = prev;
        }
        size--;
        return true;
    }

    public int Find(string value)
    {
        int index = 0;
        for (Node n = head; n != null; n = n.Next)
        {
            if (n.Value == value)
            {
                return index;
            }
            index++;
        }
        return -1;
    }

    public string Get(int index)
    {
        if (index < 0 || index >= size)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
        Node n = head;
        for (int i = 0; i < index; i++)
        {
            n = n.Next;
        }
        return n.Value;
    }

    public override string ToString()
    {
        var values = new List<string>();
        for (Node n = head; n != null; n = n.Next)
        {
            values.Add(n.Value);
        }
        return string.Join(" → ", values);
    }
}

При 10 000 имейла масивът прави 50 021 376 записа, а свързаният списък 10 000.

Сега обратното: прочитане на всеки елемент по индекс, get(0), get(1) и така до края. Броим местата, до които стигаш: в масива get(i) е един скок, а в списъка минава i + 1 възела.

Масив: get(i) за всяко i O(n)
Свързан списък: get(i) за всяко i O(n²)

Алгоритъм	n = 10	n = 1000	n = 10 000	n = 100 000
Масив: get(i) за всяко i	10	1000	10 000	100 000
Свързан списък: get(i) за всяко i	55	500 500	50 005 000	≈ 5 000 500 000

Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.

class Node
{
    public string Value;
    public Node Next;

    public Node(string value)
    {
        Value = value;
    }
}

class SimpleLinkedList
{
    private Node head;
    private Node tail;
    private int size;

    public int Count => size;

    public void AddFirst(string value)
    {
        var node = new Node(value);
        node.Next = head;
        head = node;
        if (tail == null)
        {
            tail = node;
        }
        size++;
    }

    public void AddLast(string value)
    {
        var node = new Node(value);
        if (tail == null)
        {
            head = node;
        }
        else
        {
            tail.Next = node;
        }
        tail = node;
        size++;
    }

    public string RemoveFirst()
    {
        if (head == null)
        {
            throw new InvalidOperationException("списъкът е празен");
        }
        string value = head.Value;
        head = head.Next;
        if (head == null)
        {
            tail = null;
        }
        size--;
        return value;
    }

    public bool Remove(string value)
    {
        Node prev = null;
        Node n = head;
        while (n != null && n.Value != value)
        {
            prev = n;
            n = n.Next;
        }
        if (n == null)
        {
            return false;
        }
        if (prev == null)
        {
            head = n.Next;
        }
        else
        {
            prev.Next = n.Next;
        }
        if (n == tail)
        {
            tail = prev;
        }
        size--;
        return true;
    }

    public int Find(string value)
    {
        int index = 0;
        for (Node n = head; n != null; n = n.Next)
        {
            if (n.Value == value)
            {
                return index;
            }
            index++;
        }
        return -1;
    }

    public string Get(int index)
    {
        if (index < 0 || index >= size)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
        Node n = head;
        for (int i = 0; i < index; i++)
        {
            n = n.Next;
        }
        return n.Value;
    }

    public override string ToString()
    {
        var values = new List<string>();
        for (Node n = head; n != null; n = n.Next)
        {
            values.Add(n.Value);
        }
        return string.Join(" → ", values);
    }
}

При 10 000 елемента масивът прави 10 000 скока, а свързаният списък 50 005 000 стъпки. Цикъл по индекс върху свързан списък е O(n²). Обхождай го с цикъла по стрелките (или с for-each), както прави ToString: това е O(n).

По-точно, за любопитните

Същите числа на твоя език, с броячи в класа:

class Node
{
    public string Value;
    public Node Next;

    public Node(string value)
    {
        Value = value;
    }
}

class SimpleLinkedList
{
    private Node head;
    private Node tail;
    private int size;
    public long Writes { get; private set; }
    public long Steps { get; private set; }

    public int Count => size;

    public void AddFirst(string value)
    {
        var node = new Node(value);
        Writes++;
        node.Next = head;
        head = node;
        if (tail == null)
        {
            tail = node;
        }
        size++;
    }

    public void AddLast(string value)
    {
        var node = new Node(value);
        if (tail == null)
        {
            head = node;
        }
        else
        {
            tail.Next = node;
        }
        tail = node;
        size++;
    }

    public string RemoveFirst()
    {
        if (head == null)
        {
            throw new InvalidOperationException("списъкът е празен");
        }
        string value = head.Value;
        head = head.Next;
        if (head == null)
        {
            tail = null;
        }
        size--;
        return value;
    }

    public bool Remove(string value)
    {
        Node prev = null;
        Node n = head;
        while (n != null && n.Value != value)
        {
            prev = n;
            n = n.Next;
        }
        if (n == null)
        {
            return false;
        }
        if (prev == null)
        {
            head = n.Next;
        }
        else
        {
            prev.Next = n.Next;
        }
        if (n == tail)
        {
            tail = prev;
        }
        size--;
        return true;
    }

    public int Find(string value)
    {
        int index = 0;
        for (Node n = head; n != null; n = n.Next)
        {
            if (n.Value == value)
            {
                return index;
            }
            index++;
        }
        return -1;
    }

    public string Get(int index)
    {
        if (index < 0 || index >= size)
        {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
        Node n = head;
        Steps++;
        for (int i = 0; i < index; i++)
        {
            n = n.Next;
            Steps++;
        }
        return n.Value;
    }

    public override string ToString()
    {
        var values = new List<string>();
        for (Node n = head; n != null; n = n.Next)
        {
            values.Add(n.Value);
        }
        return string.Join(" → ", values);
    }
}

foreach (int n in new[] { 10, 1000, 100000 })
{
    var list = new SimpleLinkedList();
    for (int i = 0; i < n; i++)
    {
        list.AddFirst((1001 + i).ToString());
    }
    Console.WriteLine($"отпред, n = {n}: {list.Writes} записа");
}
foreach (int n in new[] { 10, 1000 })
{
    var list = new SimpleLinkedList();
    for (int i = 0; i < n; i++)
    {
        list.AddLast((1001 + i).ToString());
    }
    for (int i = 0; i < n; i++)
    {
        list.Get(i);
    }
    Console.WriteLine($"get(i) за всяко i, n = {n}: {list.Steps} стъпки");
}

отпред, n = 10: 10 записа
отпред, n = 1000: 1000 записа
отпред, n = 100000: 100000 записа
get(i) за всяко i, n = 10: 55 стъпки
get(i) за всяко i, n = 1000: 500500 стъпки

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

Пробвай

Намери грешката

Колега е писал AddLast. Три имейла отзад, а списъкът излиза така:

var emails = new SimpleLinkedList();
emails.AddLast("фактура");
emails.AddLast("бюлетин");
emails.AddLast("отчет");
Console.WriteLine(emails);
Console.WriteLine("Имейли: " + emails.Count);

фактура → отчет
Имейли: 3

Размерът е 3, а имейлите са два. На кой ред е грешката?

Избери реда с грешката.

Пробвай

Попълни

Remove е намерил възела n и този преди него, prev. Накъде трябва да сочи prev сега?

public bool Remove(string value)
{
    Node prev = null;
    Node n = head;
    while (n != null && n.Value != value)
    {
        prev = n;
        n = n.Next;
    }
    if (n == null)
    {
        return false;
    }
    if (prev == null)
    {
        head = n.Next;
    }
    else
    {
        prev.Next = ;
    }
    if (n == tail)
    {
        tail = prev;
    }
    size--;
    return true;
}

Идеята

Двусвързан списък

Едносвързаният списък не може да маха последния бързо: трябва му предпоследният, а към него никой не сочи назад. Двусвързаният списък пази във всеки възел две стрелки, Next и Prev. Тогава и двата края са O(1), а възел, който вече държиш, се маха с четири стрелки, без да търсиш предишния.

Цената е още една стрелка във всеки възел и повече за пренасочване при всяка операция.

LinkedList<T> в C# е двусвързан. Възлите се виждат: AddLast връща LinkedListNode<T> с Next и Previous, а Remove(node) маха възела за O(1).

Идеята

Къде свързаният списък печели наистина

За обикновена опашка вграденото е по-добро. Queue<T> е масив, който пази и двата края без местене. Как работи, е в урока „Стек и опашка“. Свързаният списък печели, когато вече държиш възела и трябва да го извадиш или преместиш:

LRU кеш. Магазинът пази в паметта последните отворени продукти и изхвърля най-отдавна отворения. Hash таблица намира възела на продукта за O(1), а двусвързан списък го мести най-отзад. Най-старият е винаги отпред.
История с назад и напред. Браузърът и редакторът пазят стъпките в двусвързан списък: назад и напред са една стрелка.
Списъците в ядрото на операционната система. Процесите и буферите сами носят стрелките си и се вадят от списъка за O(1).

Ето LRU с вграденото, последните три отворени продукта:

class Recent
{
    private readonly int limit;
    private readonly LinkedList<string> order = new();
    private readonly Dictionary<string, LinkedListNode<string>> nodes = new();

    public Recent(int limit)
    {
        this.limit = limit;
    }

    public void Open(string product)
    {
        if (nodes.TryGetValue(product, out var node))
        {
            order.Remove(node);
        }
        else if (order.Count == limit)
        {
            nodes.Remove(order.First.Value);
            order.RemoveFirst();
        }
        nodes[product] = order.AddLast(product);
    }

    public override string ToString()
    {
        return string.Join(", ", order);
    }
}

var recent = new Recent(3);
foreach (string product in new[] { "лаптоп", "мишка", "монитор", "лаптоп", "клавиатура" })
{
    recent.Open(product);
    Console.WriteLine(recent);
}

лаптоп
лаптоп, мишка
лаптоп, мишка, монитор
мишка, монитор, лаптоп
монитор, лаптоп, клавиатура

Тук е класическият начин на ръка: Dictionary намира възела, а LinkedList<string> го вади и закача най-отзад. И двете са O(1).

Упражнение

Двусвързан списък

Реши задачата в редактора си.

Махане от двата края. Направи DoublyLinkedList: възелът има и Prev. Напиши AddFirst, AddLast, RemoveFirst и RemoveLast, всички за O(1). Пази двата края верни: когато списъкът стане празен, и head, и tail са null.

Добави трите имейла отзад и паролата отпред. Отпечатай списъка, махни последния и първия, отпечатай пак. Махни още два отзад, отпечатай размера, после добави поканата отзад:

парола → фактура → бюлетин → отчет
Последен: отчет
Първи: парола
фактура → бюлетин
Имейли: 0
покана

Още задачи

Средата с два указателя. Намери средния възел с едно минаване: единият указател върви по една стъпка, другият по две. Когато бързият стигне края, бавният е по средата.
Цикъл в списъка. Грешка е закачила последния възел към някой от предишните. Открий го със същите два указателя: ако има цикъл, бързият настига бавния.
Махни всички срещания. RemoveAll(string value) маха всеки възел с тази стойност с едно минаване и връща колко е махнал. Не забравяй tail.
LRU на ръка. Направи LRU кеша от картата горе със свой двусвързан списък и Dictionary от продукт към възел.

Тест

Провери се

1. Свързан списък има 1000 възела, а пазиш само head. Колко възела минаваш, за да прочетеш елемента с индекс 999?1000: от head по стрелките до него1: адресът се смята500 средно, независимо от индекса

2. Защо е нужен tail, ако head вече държи целия списък?Без него добавянето в края минава през всички възли: O(n) вместо O(1)За да се знае размерътБез него не може да се маха първият

3. В едносвързан списък с head и tail колко струва махането на последния?O(n): трябва ти предпоследният, а до него се стига от headO(log n)O(1): tail го знае

4. Bench показва, че вмъкването отпред в свързан списък прави n операции, а в динамичен масив около n²/2. Защо въпреки това масивът често е по-бърз при обхождане?Масивът се компилира по-добреСвързаният списък прави повече сравненияМасивът е един блок в паметта и кешът го чете на редове; възлите са разпръснати

5. LRU кеш пази последните 1000 отворени продукта и изхвърля най-отдавна отворения. Какво го прави O(1) за всяко отваряне?Сортиран масив по времеСамо hash таблицаHash таблица, която намира възела, и двусвързан списък, в който възелът се мести най-отзад

Свързан списък

Бисквитки