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

Код на:JavaC#PythonJavaScript

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

Проблем

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

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

emails = []
emails.append("фактура")
emails.append("бюлетин")
emails.append("отчет")
emails.insert(0, "парола")
next_email = emails.pop(0)
print("Изпращам: " + next_email)
print("Остават: " + ", ".join(emails))

Изход

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

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

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

Идеята

Възли, head и tail

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

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

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

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

Виж го

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

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

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class SimpleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def __len__(self):
        return self.size

    def add_first(self, value):
        node = Node(value)
        node.next = self.head
        self.head = node
        if self.tail is None:
            self.tail = node
        self.size += 1

    def add_last(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self.size += 1

    def remove_first(self):
        if self.head is None:
            raise IndexError("списъкът е празен")
        value = self.head.value
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.size -= 1
        return value

    def remove(self, value):
        prev = None
        n = self.head
        while n is not None and n.value != value:
            prev = n
            n = n.next
        if n is None:
            return False
        if prev is None:
            self.head = n.next
        else:
            prev.next = n.next
        if n is self.tail:
            self.tail = prev
        self.size -= 1
        return True

    def find(self, value):
        index = 0
        n = self.head
        while n is not None:
            if n.value == value:
                return index
            index += 1
            n = n.next
        return -1

    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError(f"index {index}, size {self.size}")
        n = self.head
        for _ in range(index):
            n = n.next
        return n.value

    def __str__(self):
        values = []
        n = self.head
        while n is not None:
            values.append(n.value)
            n = n.next
        return " → ".join(values)

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

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


def __init__(self):
    self.head = None
    self.tail = None
    self.size = 0

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

1. Три имейла, всеки в свой възел: стойността и next, стрелката към следващия. head сочи първия, tail последния.
2. add_first(„парола“): нов възел, неговият next сочи стария първи, и head минава на него. Две стрелки, нищо не се мести: O(1).
3. add_last(„покана“): tail вече знае последния, затова не се минава по списъка. Неговият next сочи новия, и tail се мести: O(1).
4. remove_first(): head минава на следващия възел. Към „парола“ вече не сочи нищо, и паметта му се освобождава сама.
5. remove(„бюлетин“): възлите нямат индекс. n тръгва от head и върви, докато го намери; prev остава един възел назад. Това е O(n).
6. prev.next = n.next: една стрелка заобикаля „бюлетин“. „отчет“ и „покана“ не помръдват.
7. В краищата: две стрелки, O(1). По средата: една стрелка, но до мястото се стига стъпка по стъпка, O(n).

emails = SimpleLinkedList()
emails.add_last("фактура")
emails.add_last("бюлетин")
emails.add_last("отчет")
emails.add_first("парола")
emails.add_last("покана")
print(emails)
print("Изпращам: " + str(emails.remove_first()))
emails.remove("бюлетин")
print(emails)
print("Място на отчет: " + str(emails.find("отчет")))
print("Имейли: " + str(len(emails)))

Изход

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

remove_first на празен списък хвърля IndexError, както deque.popleft. __str__ е това, което print(emails) печата. get е метод, а не [i]: така се вижда, че стига до елемента стъпка по стъпка.

Пробвай

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

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

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class SimpleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def __len__(self):
        return self.size

    def add_first(self, value):
        node = Node(value)
        node.next = self.head
        self.head = node
        if self.tail is None:
            self.tail = node
        self.size += 1

    def add_last(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self.size += 1

    def remove_first(self):
        if self.head is None:
            raise IndexError("списъкът е празен")
        value = self.head.value
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.size -= 1
        return value

    def remove(self, value):
        prev = None
        n = self.head
        while n is not None and n.value != value:
            prev = n
            n = n.next
        if n is None:
            return False
        if prev is None:
            self.head = n.next
        else:
            prev.next = n.next
        if n is self.tail:
            self.tail = prev
        self.size -= 1
        return True

    def find(self, value):
        index = 0
        n = self.head
        while n is not None:
            if n.value == value:
                return index
            index += 1
            n = n.next
        return -1

    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError(f"index {index}, size {self.size}")
        n = self.head
        for _ in range(index):
            n = n.next
        return n.value

    def __str__(self):
        values = []
        n = self.head
        while n is not None:
            values.append(n.value)
            n = n.next
        return " → ".join(values)


emails = SimpleLinkedList()
emails.add_first("отчет")
emails.add_first("фактура")
emails.add_last("покана")
emails.remove_first()
emails.add_first("парола")
emails.remove("покана")
emails.add_last("бюлетин")
print(emails)
print("Имейли: " + str(len(emails)))

Отговор

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

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

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

Провери

Идеята

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

Операция	Динамичен масив	Свързан списък
четене по индекс	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:
    def __init__(self, value):
        self.value = value
        self.next = None


class SimpleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def __len__(self):
        return self.size

    def add_first(self, value):
        node = Node(value)
        node.next = self.head
        self.head = node
        if self.tail is None:
            self.tail = node
        self.size += 1

    def add_last(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self.size += 1

    def remove_first(self):
        if self.head is None:
            raise IndexError("списъкът е празен")
        value = self.head.value
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.size -= 1
        return value

    def remove(self, value):
        prev = None
        n = self.head
        while n is not None and n.value != value:
            prev = n
            n = n.next
        if n is None:
            return False
        if prev is None:
            self.head = n.next
        else:
            prev.next = n.next
        if n is self.tail:
            self.tail = prev
        self.size -= 1
        return True

    def find(self, value):
        index = 0
        n = self.head
        while n is not None:
            if n.value == value:
                return index
            index += 1
            n = n.next
        return -1

    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError(f"index {index}, size {self.size}")
        n = self.head
        for _ in range(index):
            n = n.next
        return n.value

    def __str__(self):
        values = []
        n = self.head
        while n is not None:
            values.append(n.value)
            n = n.next
        return " → ".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:
    def __init__(self, value):
        self.value = value
        self.next = None


class SimpleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def __len__(self):
        return self.size

    def add_first(self, value):
        node = Node(value)
        node.next = self.head
        self.head = node
        if self.tail is None:
            self.tail = node
        self.size += 1

    def add_last(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self.size += 1

    def remove_first(self):
        if self.head is None:
            raise IndexError("списъкът е празен")
        value = self.head.value
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.size -= 1
        return value

    def remove(self, value):
        prev = None
        n = self.head
        while n is not None and n.value != value:
            prev = n
            n = n.next
        if n is None:
            return False
        if prev is None:
            self.head = n.next
        else:
            prev.next = n.next
        if n is self.tail:
            self.tail = prev
        self.size -= 1
        return True

    def find(self, value):
        index = 0
        n = self.head
        while n is not None:
            if n.value == value:
                return index
            index += 1
            n = n.next
        return -1

    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError(f"index {index}, size {self.size}")
        n = self.head
        for _ in range(index):
            n = n.next
        return n.value

    def __str__(self):
        values = []
        n = self.head
        while n is not None:
            values.append(n.value)
            n = n.next
        return " → ".join(values)

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

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

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

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class SimpleLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0
        self.writes = 0
        self.steps = 0

    def __len__(self):
        return self.size

    def add_first(self, value):
        node = Node(value)
        self.writes += 1
        node.next = self.head
        self.head = node
        if self.tail is None:
            self.tail = node
        self.size += 1

    def add_last(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = node
        else:
            self.tail.next = node
        self.tail = node
        self.size += 1

    def remove_first(self):
        if self.head is None:
            raise IndexError("списъкът е празен")
        value = self.head.value
        self.head = self.head.next
        if self.head is None:
            self.tail = None
        self.size -= 1
        return value

    def remove(self, value):
        prev = None
        n = self.head
        while n is not None and n.value != value:
            prev = n
            n = n.next
        if n is None:
            return False
        if prev is None:
            self.head = n.next
        else:
            prev.next = n.next
        if n is self.tail:
            self.tail = prev
        self.size -= 1
        return True

    def find(self, value):
        index = 0
        n = self.head
        while n is not None:
            if n.value == value:
                return index
            index += 1
            n = n.next
        return -1

    def get(self, index):
        if index < 0 or index >= self.size:
            raise IndexError(f"index {index}, size {self.size}")
        n = self.head
        self.steps += 1
        for _ in range(index):
            n = n.next
            self.steps += 1
        return n.value

    def __str__(self):
        values = []
        n = self.head
        while n is not None:
            values.append(n.value)
            n = n.next
        return " → ".join(values)


for n in [10, 1000, 100000]:
    list_ = SimpleLinkedList()
    for i in range(n):
        list_.add_first(str(1001 + i))
    print(f"отпред, n = {n}: {list_.writes} записа")
for n in [10, 1000]:
    list_ = SimpleLinkedList()
    for i in range(n):
        list_.add_last(str(1001 + i))
    for i in range(n):
        list_.get(i)
    print(f"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 брои операции, не време. По часовник разликата при обхождане е още по-голяма в полза на масива заради кеша: масивът е един блок, а възлите са разпръснати и всеки следващ може да не е в кеша. Тук това не е измерено, само е обяснено в урока за динамичния масив.

Пробвай

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

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

emails = SimpleLinkedList()
emails.add_last("фактура")
emails.add_last("бюлетин")
emails.add_last("отчет")
print(emails)
print("Имейли: " + str(len(emails)))

Изход

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

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

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

1class Node:2 def __init__(self, value):3 self.value = value4 self.next = None567class SimpleLinkedList:8 def __init__(self):9 self.head = None10 self.tail = None11 self.size = 01213 def __len__(self):14 return self.size1516 def add_first(self, value):17 node = Node(value)18 node.next = self.head19 self.head = node20 if self.tail is None:21 self.tail = node22 self.size += 12324 def add_last(self, value):25 node = Node(value)26 if self.tail is None:27 self.head = node28 else:29 self.head.next = node30 self.tail = node31 self.size += 13233 def remove_first(self):34 if self.head is None:35 raise IndexError("списъкът е празен")36 value = self.head.value37 self.head = self.head.next38 if self.head is None:39 self.tail = None40 self.size -= 141 return value4243 def remove(self, value):44 prev = None45 n = self.head46 while n is not None and n.value != value:47 prev = n48 n = n.next49 if n is None:50 return False51 if prev is None:52 self.head = n.next53 else:54 prev.next = n.next55 if n is self.tail:56 self.tail = prev57 self.size -= 158 return True5960 def find(self, value):61 index = 062 n = self.head63 while n is not None:64 if n.value == value:65 return index66 index += 167 n = n.next68 return -16970 def get(self, index):71 if index < 0 or index >= self.size:72 raise IndexError(f"index {index}, size {self.size}")73 n = self.head74 for _ in range(index):75 n = n.next76 return n.value7778 def __str__(self):79 values = []80 n = self.head81 while n is not None:82 values.append(n.value)83 n = n.next84 return " → ".join(values)

Провери

Пробвай

Попълни

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

def remove(self, value):
    prev = None
    n = self.head
    while n is not None and n.value != value:
        prev = n
        n = n.next
    if n is None:
        return False
    if prev is None:
        self.head = n.next
    else:
        prev.next = 
    if n is self.tail:
        self.tail = prev
    self.size -= 1
    return True

Провери

Идеята

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

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

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

collections.deque в Python е двусвързан, но всеки възел е блок от 64 елемента. Така е бърз и в двата края, а паметта за стрелки е по-малко.

Идеята

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

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

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

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

from collections import OrderedDict


class Recent:
    def __init__(self, limit):
        self.limit = limit
        self.items = OrderedDict()

    def open(self, product):
        if product in self.items:
            self.items.move_to_end(product)
        else:
            if len(self.items) == self.limit:
                self.items.popitem(last=False)
            self.items[product] = True

    def __str__(self):
        return ", ".join(self.items)


recent = Recent(3)
for product in ["лаптоп", "мишка", "монитор", "лаптоп", "клавиатура"]:
    recent.open(product)
    print(recent)

Изход

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

OrderedDict пази ключовете в двусвързан списък. move_to_end мести продукта най-отзад, а popitem(last=False) изхвърля най-стария.

Упражнение

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

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

Махане от двата края. Направи DoublyLinkedList: възелът има и prev. Напиши add_first, add_last, remove_first и remove_last, всички за O(1). Пази двата края верни: когато списъкът стане празен, и head, и tail са None.

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

Изход

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

Още задачи

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

Тест

Провери се

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 таблица, която намира възела, и двусвързан списък, в който възелът се мести най-отзад

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Най-добър, среден и най-лош случай · Сложност по памет · Амортизирана сложност · Динамичен масив отвътре
• Продължава в: Хеш таблица · Двоично дърво за търсене
• Задачи по темата: Структури от данни