Связный список

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

from dataclasses import dataclass
from typing import ClassVar


@dataclass(repr=False, eq=False)
class Node:
    data: int
    next: ClassVar = None


@dataclass(repr=False, eq=False)
class LinkedList:
    head: ClassVar = None
    last_node: ClassVar = None

    def append(self, data):
        '''Добавление элемента в список
        Если список пустой создает головной узел.'''
        if self.last_node is None:
            self.head = Node(data)
            self.last_node = self.head
        else:
            self.last_node.next = Node(data)
            self.last_node = self.last_node.next

    def display(self):
        '''вывод элементов списка'''
        current = self.head
        while current is not None:
            print(current.data, end=' ')
            current = current.next


if __name__ == '__main__':
    L = LinkedList()
    L.append(1)
    L.append(2)
    L.append(3)
    L.append(4)
    L.display()
Двухсвязный список
Двусвязный список — это список, который содержит указатель на следующий и предыдущий узел в последовательности. Это позволяет перемещаться по списку в двух направлениях.
Двухсвязный список

from dataclasses import dataclass
from typing import ClassVar


@dataclass(repr=False, eq=False)
class Node:
    data: int
    previous: ClassVar = None
    next: ClassVar = None


@dataclass(repr=False, eq=False)
class DoublyLinkedList:
    head: ClassVar = None
    start_node: ClassVar = None
    last_node: ClassVar = None

    def append(self, data):
        '''Добавление элемента в список
        Если список пустой создает головной узел.'''
        if self.last_node is None:
            self.head = Node(data)
            self.last_node = self.head
        else:
            new_node = Node(data)
            self.last_node.next = new_node
            new_node.previous = self.last_node
            new_node.next = None
            self.last_node = new_node

    def left_display(self):
        '''Обход списка с лева на право.'''
        current = self.head
        while current is not None:
            print(current.data, end=' ')
            current = current.next

    def right_display(self):
        '''Обход списка с права на лево.'''
        current = self.last_node
        while current is not None:
            print(current.data, end=' ')
            current = current.previous


if __name__ == '__main__':
    L = DoublyLinkedList()
    L.append(1)
    L.append(2)
    L.append(3)
    L.append(4)
    L.left_display()
    print()
    L.right_display()
Круговой связанный список
Круговой связанный список -то список, в котором последний узел содержит указатель на первый узел списка. Обходить круговой связанный список можно с любого узла и в любом направлении. Таким образом, круговой связанный список не имеет ни начала, ни конца.
Круговой список

from dataclasses import dataclass
from typing import ClassVar


@dataclass(repr=False, eq=False)
class Node:
    data: int
    next: ClassVar = None


@dataclass(repr=False, eq=False)
class CircularLinkedList:
    head: ClassVar = None
    last_node: ClassVar = None

    def append(self, data):
        '''Добавление элемента в список
        Если список пустой создает головной узел.'''
        if self.last_node is None:
            self.head = Node(data)
            self.last_node = self.head
        else:
            self.last_node.next = Node(data)
            self.last_node = self.last_node.next
            self.last_node.next = self.head

    def display(self):
        '''вывод элементов списка'''
        current = self.head
        while current is not None:
            print(current.data, end=' ')
            current = current.next
            if current == self.head:
                break


if __name__ == '__main__':
    L = CircularLinkedList()
    L.append(1)
    L.append(2)
    L.append(3)
    L.append(4)
    L.append(5)
    L.display()
КОГДА ЛУЧШЕ ИСПОЛЬЗОВАТЬ связный список
Преимущества перед массивами:

  1. Динамический массив.
  2. Легкость вставки/удаления.
Недостатки:

  1. Произвольный доступ не допускается. Нужно обращаться к элементам последовательно, начиная с первого узла.
  2. Для каждого элемента списка требуется дополнительное место в памяти для указателя или указателей.