Към съдържанието
wannacode

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

Накратко: Свързаният списък е верига от възли, всеки с връзка към следващия: с head и tail добавянето в двата края и махането отпред са O(1), а достъпът по индекс е O(n).

Проблем

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

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

List<String> emails = new ArrayList<>();
emails.add("фактура");
emails.add("бюлетин");
emails.add("отчет");
emails.add(0, "парола");
String next = emails.remove(0);
System.out.println("Изпращам: " + next);
System.out.println("Остават: " + 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 {
    String value;
    Node next;


    Node(String value) {
        this.value = value;
    }
}


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


    int size() {
        return size;
    }


    void addFirst(String value) {
        Node node = new Node(value);
        node.next = head;
        head = node;
        if (tail == null) {
            tail = node;
        }
        size++;
    }


    void addLast(String value) {
        Node node = new Node(value);
        if (tail == null) {
            head = node;
        } else {
            tail.next = node;
        }
        tail = node;
        size++;
    }


    String removeFirst() {
        if (head == null) {
            throw new NoSuchElementException("списъкът е празен");
        }
        String value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return value;
    }


    boolean remove(String value) {
        Node prev = null;
        Node n = head;
        while (n != null && !n.value.equals(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;
    }


    int find(String value) {
        int index = 0;
        for (Node n = head; n != null; n = n.next) {
            if (n.value.equals(value)) {
                return index;
            }
            index++;
        }
        return -1;
    }


    String get(int index) {
        Objects.checkIndex(index, size);
        Node n = head;
        for (int i = 0; i < index; i++) {
            n = n.next;
        }
        return n.value;
    }


    @Override
    public String toString() {
        List<String> values = new ArrayList<>();
        for (Node n = head; n != null; n = n.next) {
            values.add(n.value);
        }
        return String.join(" → ", values);
    }
}

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

class Node {
    String value;
    Node next;


    Node(String value) {
        this.value = value;
    }
}


private Node head;
private Node tail;
private int size;
Стъпка по стъпка, с думи
  1. Три имейла, всеки в свой възел: стойността и next, стрелката към следващия. head сочи първия, tail последния.
  2. addFirst(„парола“): нов възел, неговият next сочи стария първи, и head минава на него. Две стрелки, нищо не се мести: O(1).
  3. addLast(„покана“): tail вече знае последния, затова не се минава по списъка. Неговият next сочи новия, и tail се мести: O(1).
  4. removeFirst(): head минава на следващия възел. Към „парола“ вече не сочи нищо, и паметта му се освобождава сама.
  5. remove(„бюлетин“): възлите нямат индекс. n тръгва от head и върви, докато го намери; prev остава един възел назад. Това е O(n).
  6. prev.next = n.next: една стрелка заобикаля „бюлетин“. „отчет“ и „покана“ не помръдват.
  7. В краищата: две стрелки, O(1). По средата: една стрелка, но до мястото се стига стъпка по стъпка, O(n).
SimpleLinkedList emails = new SimpleLinkedList();
emails.addLast("фактура");
emails.addLast("бюлетин");
emails.addLast("отчет");
emails.addFirst("парола");
emails.addLast("покана");
System.out.println(emails);
System.out.println("Изпращам: " + emails.removeFirst());
emails.remove("бюлетин");
System.out.println(emails);
System.out.println("Място на отчет: " + emails.find("отчет"));
System.out.println("Имейли: " + emails.size());
Изход
парола → фактура → бюлетин → отчет → покана
Изпращам: парола
фактура → отчет → покана
Място на отчет: 1
Имейли: 3
removeFirst на празен списък хвърля NoSuchElementException, както LinkedList.removeFirst. Методът toString с @Override е това, което System.out.println(emails) печата.

Пробвай

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

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

class Node {
    String value;
    Node next;


    Node(String value) {
        this.value = value;
    }
}


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


    int size() {
        return size;
    }


    void addFirst(String value) {
        Node node = new Node(value);
        node.next = head;
        head = node;
        if (tail == null) {
            tail = node;
        }
        size++;
    }


    void addLast(String value) {
        Node node = new Node(value);
        if (tail == null) {
            head = node;
        } else {
            tail.next = node;
        }
        tail = node;
        size++;
    }


    String removeFirst() {
        if (head == null) {
            throw new NoSuchElementException("списъкът е празен");
        }
        String value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return value;
    }


    boolean remove(String value) {
        Node prev = null;
        Node n = head;
        while (n != null && !n.value.equals(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;
    }


    int find(String value) {
        int index = 0;
        for (Node n = head; n != null; n = n.next) {
            if (n.value.equals(value)) {
                return index;
            }
            index++;
        }
        return -1;
    }


    String get(int index) {
        Objects.checkIndex(index, size);
        Node n = head;
        for (int i = 0; i < index; i++) {
            n = n.next;
        }
        return n.value;
    }


    @Override
    public String toString() {
        List<String> values = new ArrayList<>();
        for (Node n = head; n != null; n = n.next) {
            values.add(n.value);
        }
        return String.join(" → ", values);
    }
}


SimpleLinkedList emails = new SimpleLinkedList();
emails.addFirst("отчет");
emails.addFirst("фактура");
emails.addLast("покана");
emails.removeFirst();
emails.addFirst("парола");
emails.remove("покана");
emails.addLast("бюлетин");
System.out.println(emails);
System.out.println("Имейли: " + emails.size());
Отговор

Идеята

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

Операция Динамичен масив Свързан списък
четене по индекс 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 = 10n = 1000n = 10 000n = 100 000
Вмъкване отпред63501 51650 021 376≈ 5 002 137 600
Свързан списък: отпред10100010 000100 000
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.
class Node {
    String value;
    Node next;


    Node(String value) {
        this.value = value;
    }
}


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


    int size() {
        return size;
    }


    void addFirst(String value) {
        Node node = new Node(value);
        node.next = head;
        head = node;
        if (tail == null) {
            tail = node;
        }
        size++;
    }


    void addLast(String value) {
        Node node = new Node(value);
        if (tail == null) {
            head = node;
        } else {
            tail.next = node;
        }
        tail = node;
        size++;
    }


    String removeFirst() {
        if (head == null) {
            throw new NoSuchElementException("списъкът е празен");
        }
        String value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return value;
    }


    boolean remove(String value) {
        Node prev = null;
        Node n = head;
        while (n != null && !n.value.equals(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;
    }


    int find(String value) {
        int index = 0;
        for (Node n = head; n != null; n = n.next) {
            if (n.value.equals(value)) {
                return index;
            }
            index++;
        }
        return -1;
    }


    String get(int index) {
        Objects.checkIndex(index, size);
        Node n = head;
        for (int i = 0; i < index; i++) {
            n = n.next;
        }
        return n.value;
    }


    @Override
    public String toString() {
        List<String> values = new ArrayList<>();
        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 = 10n = 1000n = 10 000n = 100 000
Масив: get(i) за всяко i10100010 000100 000
Свързан списък: get(i) за всяко i55500 50050 005 000≈ 5 000 500 000
Кодът се пуска в твоя браузър на JavaScript. Броят операции е същият на всеки език, защото алгоритъмът е същият. Времето зависи от машината, затова е само за сравнение. „≈“ е оценка по кривата: толкова голямо n не пускаме, за да не замръзне страницата.
class Node {
    String value;
    Node next;


    Node(String value) {
        this.value = value;
    }
}


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


    int size() {
        return size;
    }


    void addFirst(String value) {
        Node node = new Node(value);
        node.next = head;
        head = node;
        if (tail == null) {
            tail = node;
        }
        size++;
    }


    void addLast(String value) {
        Node node = new Node(value);
        if (tail == null) {
            head = node;
        } else {
            tail.next = node;
        }
        tail = node;
        size++;
    }


    String removeFirst() {
        if (head == null) {
            throw new NoSuchElementException("списъкът е празен");
        }
        String value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return value;
    }


    boolean remove(String value) {
        Node prev = null;
        Node n = head;
        while (n != null && !n.value.equals(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;
    }


    int find(String value) {
        int index = 0;
        for (Node n = head; n != null; n = n.next) {
            if (n.value.equals(value)) {
                return index;
            }
            index++;
        }
        return -1;
    }


    String get(int index) {
        Objects.checkIndex(index, size);
        Node n = head;
        for (int i = 0; i < index; i++) {
            n = n.next;
        }
        return n.value;
    }


    @Override
    public String toString() {
        List<String> values = new ArrayList<>();
        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 {
    String value;
    Node next;


    Node(String value) {
        this.value = value;
    }
}


class SimpleLinkedList {
    private Node head;
    private Node tail;
    private int size;
    long writes = 0;
    long steps = 0;


    int size() {
        return size;
    }


    void addFirst(String value) {
        Node node = new Node(value);
        writes++;
        node.next = head;
        head = node;
        if (tail == null) {
            tail = node;
        }
        size++;
    }


    void addLast(String value) {
        Node node = new Node(value);
        if (tail == null) {
            head = node;
        } else {
            tail.next = node;
        }
        tail = node;
        size++;
    }


    String removeFirst() {
        if (head == null) {
            throw new NoSuchElementException("списъкът е празен");
        }
        String value = head.value;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return value;
    }


    boolean remove(String value) {
        Node prev = null;
        Node n = head;
        while (n != null && !n.value.equals(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;
    }


    int find(String value) {
        int index = 0;
        for (Node n = head; n != null; n = n.next) {
            if (n.value.equals(value)) {
                return index;
            }
            index++;
        }
        return -1;
    }


    String get(int index) {
        Objects.checkIndex(index, size);
        Node n = head;
        steps++;
        for (int i = 0; i < index; i++) {
            n = n.next;
            steps++;
        }
        return n.value;
    }


    @Override
    public String toString() {
        List<String> values = new ArrayList<>();
        for (Node n = head; n != null; n = n.next) {
            values.add(n.value);
        }
        return String.join(" → ", values);
    }
}


for (int n : new int[] {10, 1000, 100000}) {
    SimpleLinkedList list = new SimpleLinkedList();
    for (int i = 0; i < n; i++) {
        list.addFirst(String.valueOf(1001 + i));
    }
    System.out.println("отпред, n = " + n + ": " + list.writes + " записа");
}
for (int n : new int[] {10, 1000}) {
    SimpleLinkedList list = new SimpleLinkedList();
    for (int i = 0; i < n; i++) {
        list.addLast(String.valueOf(1001 + i));
    }
    for (int i = 0; i < n; i++) {
        list.get(i);
    }
    System.out.println("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. Три имейла отзад, а списъкът излиза така:

SimpleLinkedList emails = new SimpleLinkedList();
emails.addLast("фактура");
emails.addLast("бюлетин");
emails.addLast("отчет");
System.out.println(emails);
System.out.println("Имейли: " + emails.size());
Изход
фактура → отчет
Имейли: 3

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

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

Пробвай

Попълни

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

boolean remove(String value) {
    Node prev = null;
    Node n = head;
    while (n != null && !n.value.equals(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 в Java е двусвързан. Има addFirst, addLast, removeFirst, removeLast, а get(i) ходи от по-близкия край.

Идеята

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

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

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

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

class Recent {
    private final int limit;
    private final LinkedHashSet<String> items = new LinkedHashSet<>();


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


    void open(String product) {
        if (items.contains(product)) {
            items.remove(product);
        } else if (items.size() == limit) {
            items.removeFirst();
        }
        items.add(product);
    }


    @Override
    public String toString() {
        return String.join(", ", items);
    }
}


Recent recent = new Recent(3);
for (String product : new String[] {"лаптоп", "мишка", "монитор", "лаптоп", "клавиатура"}) {
    recent.open(product);
    System.out.println(recent);
}
Изход
лаптоп
лаптоп, мишка
лаптоп, мишка, монитор
мишка, монитор, лаптоп
монитор, лаптоп, клавиатура
LinkedHashSet е точно hash таблица плюс двусвързан списък през елементите, затова пази реда на добавяне. remove и add местят продукта най-отзад, а removeFirst изхвърля най-стария.

Упражнение

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

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

Махане от двата края. Направи DoublyLinkedList: възелът има и prev. Напиши addFirst, addLast, removeFirst и removeLast, всички за O(1). Пази двата края верни: когато списъкът стане празен, и head, и tail са null.

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

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

Още задачи

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

Тест

Провери се

1. Свързан списък има 1000 възела, а пазиш само head. Колко възела минаваш, за да прочетеш елемента с индекс 999?
2. Защо е нужен tail, ако head вече държи целия списък?
3. В едносвързан списък с head и tail колко струва махането на последния?
4. Bench показва, че вмъкването отпред в свързан списък прави n операции, а в динамичен масив около n²/2. Защо въпреки това масивът често е по-бърз при обхождане?
5. LRU кеш пази последните 1000 отворени продукта и изхвърля най-отдавна отворения. Какво го прави O(1) за всяко отваряне?

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·