def display(self):
    elements = []  # Список для сбора данных
    current_node = self.head  # Начинаем с головы
    
    # Идем по цепочке, пока не дойдем до конца
    while current_node:
        elements.append(current_node.data)  # Собираем данные
        current_node = current_node.next    # Переходим к следующему
    
    return elements

Этот обход работает так:

head → [10|•]→[20|•]→[30|×]
       ↑
    current_node
    elements = []

Шаг 1:
current_node указывает на [10]
elements = [10]
current_node = current_node.next

Шаг 2:
head → [10|•]→[20|•]→[30|×]
              ↑
           current_node
elements = [10, 20]
current_node = current_node.next

Шаг 3:
head → [10|•]→[20|•]→[30|×]
                     ↑
                  current_node
elements = [10, 20, 30]
current_node = current_node.next

Шаг 4:
current_node = None (конец списка)
Выходим из цикла

Полная реализация простого связного списка с методами добавления и отображения объединяет все вышесказанное.

Пример 1

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

def prepend(self, data):
    new_node = Node(data)
    new_node.next = self.head  # Новый узел указывает на старую голову
    self.head = new_node       # Новый узел становится головой

Визуализируя это:

Было:
head → [10|•]→[20|×]

Добавляем 5 в начало:
new_node = [5|×]

new_node.next = head:
[5|•]→[10|•]→[20|×]

head = new_node:
head → [5|•]→[10|•]→[20|×]

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

def find(self, data):
    current_node = self.head
    position = 0
    
    while current_node:
        if current_node.data == data:
            return position  # Нашли!
        current_node = current_node.next
        position += 1
    
    return -1  # Не нашли

Пример поиска:

ll = LinkedList()
ll.append(10)
ll.append(20)
ll.append(30)

print(ll.find(20))  # Вывод: 1 (индекс элемента 20)
print(ll.find(99))  # Вывод: -1 (элемент не найден)

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

# Добавить в начало связного списка
def prepend(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node
# Всего 3 операции - очень быстро!

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

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

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

Удаление узла по заданному значению требует обработки нескольких случаев: пустой список, удаление головы или элемента из середины или конца списка.