Связные списки

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

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

 Доступ к элементу O(n). Поиск по списку - O(n). O(n)- так как приходится перебирать весь список что бы получить доступ к нужному. 

 Вставка и удаление элемента - O(1) - не нужно перемещать другие элементы достаточно переписать информацию о следующем элементе не трогая его.

Пример кода:

class Node:
    def __init__(self, data, next= None):
        self.data= data
        self.next = next
class LinkedList:
    def __init__(self):
        self.head = None
        
    def append(self, data):
        if not self.head:
            self.head = Node(data)
            return 
        current = self.head
        while current.next:
            current = current.next
        current.next = Node(data)
        
    def remove(self, target):
        if self.head == target:
            self.head = self.head.next
            return 
        current = self.head
        previos = None
        while current:
            if current.data == target:
                previos.next = current.next
            previos = current
            current = current.next
            
    def search(self, target):
        current = self.head
        while current.next:
            if current.data == target:
                return True
            else:
                current = current.next
        return False
    
    def reverse(self):
        current = self.head
        previos = None
        while current:
            next = current.next
            current.next = previos
            previos = current
            current = next
        self.head = previos
        
    def check_cycle(self):
        slow = self.head
        fast = self.head
        while True:
            try:
                slow = slow.next
                fast = fast.next.next
                if slow is fast:
                    return True
            except:
                return False
        
    def __str__(self):
        node = self.head
        while node is not None:
            print(node)
            node = node.next