Реализация связанного списка с примерами и анимацией

связный список — одна из самых основных структур данных в информатике. В этой статье мы рассмотрим следующие темы:

• Преимущества и недостатки связанного списка по сравнению с массивами.
• Что такое связанный список?
• Вставка в связанный список (вставка узла).
• Удаление из связанного списка (удаление узла).

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

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

class Node:
    def __init__(self, data: int, next_node: 'Node' = None):
        self.data = data
        self.next = next_node

Вставка в связанный список (вставка узла)

Существует три способа вставки узла в связанный список:

1. Вставить в начало списка.
2. Вставить в конец списка.
3. Вставить в указанную позицию.

Вставить в начало списка

Начнем с самого простого. Мы вставим узел в начало списка. Алгоритм состоит из следующих шагов:

• Создайте новый узел.
• Установите следующий указатель нового узла так, чтобы он указывал на голову.
• Установите голову так, чтобы она указывала на новый узел.
• Верните новую головку.

def insert_at_beginning(head: Node, data: int) -> Node:
    new_node = Node(data)
    new_node.next = head

    return new_node

Давайте создадим список из 4 узлов с помощью этого метода:

head = None
for i in range(4):
    head = insert_at_beginning(head, i + 1)

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

https://youtu.be/o3QSIpwbnWA

Вставить в конец списка

Этот алгоритм немного сложнее, но все равно прост. Мы вставим узел в конец списка.

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

def insert_at_end(head: Node, data: int) -> Node:
    new_node = Node(data)

    if head is None:
        return new_node

    current = head
    while current.next is not None:
        current = current.next

    current.next = new_node

    return head

head = None
for i in range(5):
    head = insert_at_end(head, i + 1)

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

https://youtu.be/My9EhWutFLA

Вставить в указанную позицию.

Мы вставим узел в заданную позицию. Алгоритм состоит из следующих шагов:

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

def insert_at_position(head: Node, data: int, position: int) -> Node:
    new_node = Node(data)

    if position == 0:
        new_node.next = head
        return new_node

    current = head
    current_position = 0
    while current is not None and current_position < position - 1:
        current = current.next
        current_position += 1

    if current is None:
        return head

    new_node.next = current.next
    current.next = new_node

    return head

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

Вставить узел в позицию 0:

https://youtu.be/M6arY_grcQk

Вставить узел в позицию, превышающую длину списка:

https://youtu.be/WV0Yg2V7uwQ

Вставить узел в позицию между 0 и длиной списка:

https://youtu.be/Erj15RJKbWA

Удаление из связанного списка

Есть три способа удалить узел из связанного списка:

1. Удалить первый узел.
2. Удалить последний узел.
3. Удалить узел в указанной позиции.

Удалить первый узел

Алгоритм состоит из следующих шагов:

• Настройте голову так, чтобы она указывала на второй узел.
• Верните новую головку.

def delete_first(head: Node) -> Node:
    if head is None:
        return None

    return head.next

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

https://youtu.be/CO9y3i2KdGM

Удалить последний узел

Алгоритм состоит из следующих шагов:

• Проходим по списку, пока не найдем предпоследний узел.
• Установите следующий указатель предпоследнего узла равным нулю.
• Вернуть голову.

def delete_last(head: Node) -> Node:
    if head is None:
        return None

    if head.next is None:
        return None

    current = head
    while current.next.next is not None:
        current = current.next

    current.next = None

    return head

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

https://youtu.be/E0qOO7bcyBY

Удалить узел в заданной позиции

Алгоритм состоит из следующих шагов:

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

def delete_at_position(head: Node, position: int) -> Node:
    if position == 0:
        return head.next

    current = head
    current_position = 0
    while current is not None and current_position < position - 1:
        current = current.next
        current_position += 1

    if current is None or current.next is None:
        return head

    current.next = current.next.next

    return head

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

https://youtu.be/-Za3ox3H2sk

Заключение

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