Реализация связанного списка Python

День изучения Python

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

Узел

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

Узел — это структура данных, которая содержит две важные части информации: данные и одну или несколько ссылок на другие узлы.

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

__в этом__()

class LinkedList:
    def __init__(self):
        self.head = None

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

добавить (я, данные)

Добавляет новый узел с заданным data в конец связанного списка. Если список пуст, новый узел становится head.

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

def append(self, data):
    new_node = Node(data)
    if not self.head:
          self.head = new_node
     else:
          current = self.head
          while current.next:
              current = current.next
          current.next = new_node

добавить (я, данные)

Добавляет новый узел с заданным data в начало связанного списка. Он изменяет ссылку next нового узла на текущий узел head и обновляет ссылку head на новый узел.

def prepend(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node

удалить (себя, данные)

Удаляет первое вхождение узла с заданным data из связанного списка.

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

Затем он обновляет ссылку next на предыдущий узел, чтобы пропустить текущий узел.

def delete(self, data):
    current = self.head
    if current and current.data == data:
        self.head = current.next
        return
    prev = None
    while current and current data!= data:
        prev = current
        current = current.next
    if current is None:
        return
    prev.next = current.next

дисплей (я)

Отображает элементы связанного списка в порядке от head до конца.

def display(self):
    elements = []
    current = self.head
    while current:
        elements.append(current.data)
        current = current.next
    print(" -> ".join(map(str, elements))))

поиск(я, данные)

Ищет первое вхождение узла с заданным data в связанном списке. Если найдено, возвращаетTrue; в противном случае возвращается False.

def search(self, data):
    current = self.head
    while current:
        if current.data == data:
            return True
        current = current.next
    return False

Примеры кода

Create a new linked list
my_list = LinkedList()

# Append some elements
my_list.append(5)
my_list.append(10)
my_list.append(15)

Display the linked list
my_list.display()  # Output: 5 -> 10 -> 15

# Prepend an element
my_list.prepend(1)

Display the linked list
my_list.display()  # Output: 1 -> 5 -> 10 -> 15

Search for an element
print(my_list.search(10))  Output: True

# Delete an element
my_list.delete(5)

Display the linked list
my_list.display()  # Output: 1 -> 10 -> 15