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

Связанный список: Что это такое?

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

Список/массив:

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

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

Проблема:

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

Golang попытался решить эту проблему, введя динамический массив, известный как slice, python пошел дальше и не только имеет список, который растет и уменьшается по желанию, но и позволяет вставлять элементы разных типов в один список.

Давайте посмотрим на массив в коде:


#python list
my_list = ['milk', 'coffee', 'honey', 4, 6, 2, 4.6]

#check if an item exists
print('milk' in my_list)
#True

#add to a list
my_list.append('tea')

Вход в полноэкранный режим Выход из полноэкранного режима

Вот как используется список в python. Давайте посмотрим на массив в golang.

package main

import "fmt"

func main() {

// Creating an array of string type 
// Using var keyword
var myarr[3]string

// Elements are assigned using index
myarr[0] = "milk"
myarr[1] = "honey"
myarr[2] = "coffee"

// Accessing the elements of the array 
// Using index value
fmt.Println("Elements of Array:")
fmt.Println("Element 1: ", myarr[0])
fmt.Println("Element 2: ", myarr[1])
fmt.Println("Element 3: ", myarr[2])
}
Вход в полноэкранный режим Выход из полноэкранного режима

Теперь, если мы захотим добавить еще элемент в этот массив, мы столкнемся с проблемами, потому что, глядя на него, мы достигли нашей полной емкости размера 3.

Решение:

Хотя и вставка, и поиск в отсортированном массиве с известным индексом будут иметь постоянное время работы O(1). Но если массив будет расти и продолжать копировать элементы, вы можете столкнуться с проблемами, поэтому мы пытаемся найти лучший способ хранения и поиска элементов. Линклист частично решает эту проблему, но вводит совершенно новую проблему, о которой мы поговорим позже. Удаление и изменение размера массива обычно O(n), потому что это требует перестановки элементов.

Как связать список:

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

В связном списке вам не нужно сортировать элементы, так как вы не имеете никакого отношения к индексу, вы просто спрашиваете память, хранит ли она нужный вам элемент, и если она отвечает «нет», вы используете указатель для поиска следующей памяти и задаете аналогичный вопрос, пока не дойдете до точки, где элемент указывает на null или None.

Давайте посмотрим на это в действии:


from typing import Any
from dataclasses import dataclass


@dataclass
class Node:
    """
    Node class
    I love keeping a track of both the next and previous node,  
    in other words called doubly linked list. 
    """
    data: Any
    next: 'Node' = None
    prev: 'Node' = None

    def __str__(self):
        return str(self.data)


@dataclass
class LinkedList:
    """
    Linked List Class
    """
    head: Node = None
    tail: Node = None

    def __str__(self):
        """
        print linked list
        """
        if self.head is None:
            return "Empty Linked List"
        else:
            return f"Linked List: {self.head} -> {self.tail} has {self.size()} nodes"
     def __iter__(self):
        """
        iterate over linked list
        """
        current = self.head
        while current is not None:
            yield current
            current = current.next

    def size(self):
        """
        return size of linked list
        """
        if self.head is None:
            return 0
        current = self.head
        count = 0
        while current is not None:
            count += 1
            current = current.next
        return count

    def is_empty(self):
        """
        check if linked list is empty
        """
        return self.head is None

    def add_first(self, data):
        """
        add node to the beginning of the linked list
        """
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node

    def add_last(self, data):
        """
        add node to the end of the linked list
        """
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node

    def add_at(self, index, data):
        """
        add node at a specific index
        """
        if index == 0:
            self.add_first(data)
        elif index == self.size():
            self.add_last(data)
        else:
            new_node = Node(data)
            current = self.head
            count = 0
            while current is not None:
                if count == index:
                    new_node.next = current.next
                    current.next.prev = new_node
                    new_node.prev = current
                    current.next = new_node
                    break
                current = current.next
                count += 1

    def remove_first(self):
        """
        remove first node
        """
        if self.head is None:
            return None
        else:
            self.head = self.head.next
            if self.head is None:
                self.tail = None
            else:
                self.head.prev = None

    def remove_last(self):
        """
        remove last node
        """
        if self.head is None:
            return None
        else:
            self.tail = self.tail.prev
            if self.tail is None:
                self.head = None
            else:
                self.tail.next = None

    def remove_at(self, index):
        """
        remove node at a specific index
        """
        if index == 0:
            self.remove_first()
        elif index == self.size() - 1:
            self.remove_last()
        else:
            current = self.head
            count = 0
            while current is not None:
                if count == index:
                    current.prev.next = current.next
                    current.next.prev = current.prev
                    break
                current = current.next
                count += 1

    def insert_values(self, values):
        """
        insert values into linked list
        """
        for value in values:
            self.add_last(value)

    def print_ll(self):
        """
        print linked list
        """
        if self.head is None:
            print("Empty Linked List")
        else:
            current = self.head
            while current is not None:
                print(current, end="--> ")
                current = current.next
            # print()

    def reverse_ll(self):
        """
        reverse linked list
        """
        if self.head is None:
            return None
        else:
            current = self.head
            while current is not None:
                temp = current.prev
                current.prev = current.next
                current.next = temp
                current = current.prev
            self.head = current.prev



if __name__ == "__main__":
    ll = LinkedList()
    ll.add_first(1)
    ll.add_first(2)
    ll.add_first(3)
    ll.add_last(4)
    ll.add_last(5)
    ll.add_at(2, 6)
    ll.insert_values([7, 8, 9])
    ll.print_ll()
    print("n")
    print(ll)

"""
if you run this code you will get.
3--> 2--> 1--> 6--> 4--> 5--> 7--> 8--> 9--> 
Linked List: 3 -> 9 has 9 nodes
"""


Вход в полноэкранный режим Выход из полноэкранного режима

Давайте посмотрим на код и объясним, что здесь происходит

  • Data содержит значение, которое будет храниться в узле.
  • Next содержит ссылку на следующий узел в списке
  • Prev содержит ссылку на предыдущий узел в списке.

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

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

Если присмотреться, то мы решили эту проблему с массивом, имеющим фиксированный размер.

Связанные списки служат для различных целей в реальном мире. Они могут использоваться для реализации (предупреждение спойлера!) очередей или стеков, а также графов. Они также полезны для гораздо более сложных задач, таких как управление жизненным циклом приложения операционной системы.

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

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

Обход — это просто более сложный способ сказать «итерация». Поэтому, помня об этом, создайте iter, чтобы добавить к связанным спискам то же поведение, которое вы ожидаете от обычного списка:

    def __iter__(self):
        """
        iterate over linked list
        """
        current = self.head
        while current is not None:
            yield current
            current = current.next
Войти в полноэкранный режим Выход из полноэкранного режима

Приведенный выше метод проходит через весь список и выдает каждый узел. Самое важное, что нужно помнить об этом методе, это то, что вам нужно всегда проверять, что текущий узел не является None. Если это условие равно True, это означает, что вы достигли конца вашего связного списка.

После выхода из текущего узла вы хотите перейти к следующему узлу в списке. Поэтому вы добавляете node = node.next. Вот пример обхода произвольного списка и печати каждого узла:

Как вставить новый узел

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

Вставка в начало

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

    def add_first(self, data):
        """
        add node to the beginning of the linked list
        """
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            new_node.next = self.head
            self.head.prev = new_node
            self.head = new_node
Вход в полноэкранный режим Выход из полноэкранного режима

В приведенном выше примере вы устанавливаете self.head в качестве следующей ссылки нового узла, чтобы новый узел указывал на старый self.head. После этого необходимо указать, что новая глава списка является вставленным узлом.

Вставка в конец

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

   def add_last(self, data):
        """
        add node to the end of the linked list
        """
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            self.tail = new_node
        else:
            self.tail.next = new_node
            new_node.prev = self.tail
            self.tail = new_node
Вход в полноэкранный режим Выход из полноэкранного режима

Вставка между двумя узлами
Вставка между двумя узлами добавляет еще один уровень сложности к и без того сложным вставкам связанного списка, потому что существует два различных подхода, которые вы можете использовать:

Вставка после существующего узла

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

    def add_at(self, index, data):
        """
        add node at a specific index
        """
        if index == 0:
            self.add_first(data)
        elif index == self.size():
            self.add_last(data)
        else:
            new_node = Node(data)
            current = self.head
            count = 0
            while current is not None:
                if count == index:
                    new_node.next = current.next
                    current.next.prev = new_node
                    new_node.prev = current
                    current.next = new_node
                    break
                current = current.next
                count += 1
Вход в полноэкранный режим Выход из полноэкранного режима

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

Как удалить узел

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

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

    def remove_first(self):
        """
        remove first node
        """
        if self.head is None:
            return None
        else:
            self.head = self.head.next
            if self.head is None:
                self.tail = None
            else:
                self.head.prev = None

    def remove_last(self):
        """
        remove last node
        """
        if self.head is None:
            return None
        else:
            self.tail = self.tail.prev
            if self.tail is None:
                self.head = None
            else:
                self.tail.next = None

    def remove_at(self, index):
        """
        remove node at a specific index
        """
        if index == 0:
            self.remove_first()
        elif index == self.size() - 1:
            self.remove_last()
        else:
            current = self.head
            count = 0
            while current is not None:
                if count == index:
                    current.prev.next = current.next
                    current.next.prev = current.prev
                    break
                current = current.next
                count += 1
Вход в полноэкранный режим Выход из полноэкранного режима

В приведенном выше коде мы используем размер в своих интересах. remove_first пытается удалить первый узел связанного списка.
remove_last пытается удалить последний узел, remove_at использует нужный индекс и удаляет его из списка. сначала вы проверяете, что ваш список не пуст. Если он пуст, вы можете выдать исключение или вернуть None. После этого вы проверяете, является ли удаляемый узел текущей главой списка. Если это так, то вы хотите, чтобы следующий узел в списке стал новой главой.

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

Обратите внимание, что в приведенном выше коде вы используете previous_node для отслеживания предыдущего узла. Это гарантирует, что весь процесс будет намного проще, когда вы найдете нужный узел для удаления.

Сравнение производительности: Списки против связанных списков

В большинстве языков программирования существуют четкие различия в том, как связанные списки и массивы хранятся в памяти. В Python, однако, списки являются динамическими массивами. Это означает, что использование памяти как списками, так и связанными списками очень похоже.

Вставка и удаление элементов

В Python вы можете вставлять элементы в список с помощью .insert() или .append(). Для удаления элементов из списка можно использовать их аналоги: .remove() и .pop().

Основное различие между этими методами заключается в том, что вы используете .insert() и .remove() для вставки или удаления элементов на определенной позиции в списке, а .append() и .pop() используются только для вставки или удаления элементов в конце списка.

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

Учитывая все это, даже если вставка элементов в конец списка с помощью .append() или .insert() будет иметь постоянное время, O(1), когда вы попытаетесь вставить элемент ближе к началу списка или в начале списка, средняя временная сложность будет расти вместе с размером списка: O(n).

Связанные списки, с другой стороны, гораздо более просты, когда речь идет о вставке и удалении элементов в начале или конце списка, их временная сложность всегда постоянна: O(1).

По этой причине связанные списки имеют преимущество в производительности перед обычными списками при реализации очереди (FIFO), в которой элементы непрерывно вставляются и удаляются в начале списка. Но они работают аналогично спискам при реализации стека (LIFO), в котором элементы вставляются и удаляются в конце списка.

Извлечение элементов

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

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

Оставьте комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *