Linked list (связанный список) — это одна из самых важных структур данных в компьютерной науке. Он представляет собой коллекцию элементов, где каждый элемент ссылается на следующий, образуя цепочку связанных узлов. В Python можно легко реализовать свой собственный linked list с помощью классов и указателей.
В этой статье мы рассмотрим несколько примеров создания linked list в Python и объясним основные понятия, связанные с этой структурой данных. Мы покажем, как добавлять и удалять узлы, а также как выполнять другие операции, такие как поиск элементов и обход списка.
Linked list может быть очень полезен во многих случаях, особенно в ситуациях, когда требуется частое добавление или удаление элементов в середине списка. Он также экономит память, поскольку размер списка может быть динамическим и не требовать сразу выделения большого блока памяти, как это происходит, например, при использовании массивов. При использовании связанного списка необходимо обратить внимание на производительность, поскольку время доступа к элементам может быть медленнее по сравнению с массивами.
Создание начального элемента linkedlist
Linked list в Python представляет структуру данных, состоящую из узлов, связанных между собой. Каждый узел содержит как само значение, так и ссылку на следующий узел.
Для начала создания linked list необходимо создать первый узел, который называется начальным элементом или «головой» списка. Для этого мы можем создать класс Node, который будет представлять узел:
«`python
class Node:
def __init__(self, data):
self.data = data
self.next = None
В конструкторе класса Node мы инициализируем два атрибута: data (данные узла) и next (ссылка на следующий узел). В данном случае мы устанавливаем ссылку на None, так как мы пока не добавили следующий узел.
После создания класса Node, мы можем создать объект, представляющий начальный элемент linked list:
«`python
head = Node(5)
В данном примере, мы создаем объект head, который является начальным элементом linked list. Значение данного элемента равно 5. Отныне, мы можем использовать объект head, чтобы добавлять новые элементы в linked list или выполнять другие операции над ним.
Таким образом, создание начального элемента linked list является первым и важным шагом при работе с этой структурой данных.
Добавление элементов в linkedlist
Добавление элементов в linkedlist осуществляется путем создания нового узла и установки ссылки на него из последнего узла списка.
Вот пример кода на Python, который демонстрирует добавление элементов в linkedlist:
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def add_element(self, data):
new_node = Node(data)
if self.head is None:
self.head = new_node
else:
current = self.head
while current.next:
current = current.next
current.next = new_node
В этом коде определены два класса: Node и LinkedList. Класс Node представляет узел linkedlist, а класс LinkedList представляет сам список и содержит метод add_element, который добавляет новый элемент в конец списка.
Первоначально голова списка (self.head) установлена на None, что означает, что список пуст. При добавлении нового элемента сначала создается новый узел (new_node) с указанными данными. Затем проверяется, является ли голова списка None. Если да, то голова списка устанавливается на новый узел. Если нет, то создается переменная current, которая используется для обхода списка до последнего узла. Затем указатель next последнего узла устанавливается на новый узел.
Таким образом, при каждом вызове метода add_element узел добавляется в конец списка.
Пример использования:
linked_list = LinkedList()
linked_list.add_element(1)
linked_list.add_element(2)
linked_list.add_element(3)
current = linked_list.head
while current:
print(current.data)
current = current.next
1
2
3
Удаление элементов из linkedlist
pop(): Методpop()позволяет удалить последний элемент из linkedlist и вернуть его значение. Пример:
linkedlist = LinkedList()
linkedlist.append(1)
linkedlist.append(2)
linkedlist.append(3)
print(linkedlist.pop()) # 3
remove(): Метод remove() позволяет удалить первое вхождение указанного элемента из linkedlist. Пример:
linkedlist = LinkedList()
linkedlist.append(1)
linkedlist.append(2)
linkedlist.append(3)
linkedlist.remove(2)
print(linkedlist) # LinkedList(1, 3)
delete(): Метод delete() позволяет удалить все вхождения указанного элемента из linkedlist. Пример:
linkedlist = LinkedList()
linkedlist.append(1)
linkedlist.append(2)
linkedlist.append(2)
linkedlist.append(3)
linkedlist.delete(2)
print(linkedlist) # LinkedList(1, 3)
Таким образом, использование этих методов позволяет удалять элементы из linkedlist в нужной нам точке и с нужными условиями.
Получение элементов linkedlist
- Установить текущий узел в начало linkedlist.
- Перейти к следующему узлу указанное количество раз, чтобы достичь нужного индекса.
- Вернуть значение узла с заданным индексом.
Пример кода:
def get_element(linkedlist, index):
if index < 0 or index >= len(linkedlist):
raise IndexError("Index out of range")
current = linkedlist.head
for _ in range(index):
current = current.next
return current.value
Эта функция получает linkedlist и индекс в качестве параметров и возвращает значение узла с заданным индексом. Если индекс выходит за границы допустимого диапазона, функция выбрасывает исключение IndexError.
Пример использования:
my_list = LinkedList()
my_list.add(1)
my_list.add(2)
my_list.add(3)
my_list.add(4)
my_list.add(5)
Получение элементов linkedlist по индексу позволяет нам получать доступ к определенным элементам в списке и выполнять с ними нужные операции.
Изменение элементов linkedlist
Для изменения элементов связного списка в Python можно использовать несколько подходов:
- Изменение значения по индексу: Чтобы изменить значение элемента по определенному индексу, сначала необходимо перейти к этому индексу, а затем изменить значение. Например, если есть список «linked», и нужно изменить значение второго элемента, можно использовать следующий код:
linked[1] = новое_значение
- Добавление элемента в середину списка: Чтобы добавить новый элемент в середину списка, необходимо создать новый узел, установить его ссылку на следующий узел равной ссылке текущего узла (следующего за требуемой позицией), а затем установить ссылку текущего узла на новый узел. Например, если требуется добавить новый элемент после второго элемента списка «linked», можно использовать следующий код:
новый_узел = Node(новое_значение)
текущий = linked.head
счетчик = 0
while счетчик != 2:
текущий = текущий.next
счетчик += 1
новый_узел.next = текущий.next
текущий.next = новый_узел
- Удаление элемента по индексу: Чтобы удалить элемент по определенному индексу, необходимо перейти к этому индексу, установить ссылку предыдущего узла на следующий узел после удаляемого элемента. Например, если требуется удалить второй элемент из списка «linked», можно использовать следующий код:
текущий = linked.head
счетчик = 0
while счетчик != 1:
предыдущий = текущий
текущий = текущий.next
счетчик += 1
предыдущий.next = текущий.next
Это только некоторые примеры того, как можно изменять элементы связного списка в Python. Важно помнить, что при изменении элементов нужно учитывать логику списка, чтобы не нарушить его структуру и связи между узлами.