Недавно я попытался преобразовать односвязный список из программы C в мою собственную программу на Python. Я сам протестировал код, но все еще не уверен, правильно ли преобразована программа. Я хотел бы, чтобы кто-нибудь проверил мой код, чтобы увидеть, есть ли какие-либо ошибки в методологии, слишком много методов, какие-либо отсутствующие методы и т. Д.
Я попытался реализовать некоторые из моих собственных операций с односвязными списками на основе рекомендаций этого веб-сайта: https://afteracademy.com/blog/types-of-linked-list-and-operation-on-linked-list
Исходная программа на C: https://people.eng.unimelb.edu.au/ammoffat/ppsaa/c/listops.c
Мой собственный код на Python:
class Node():
# Node for a single linked list
def __init__(self, data):
self.data = data
self.next = None
class LinkedList():
def __init__(self):
self.head = None
self.foot = None
def length(self):
'''Returns the length of a linked list.'''
current_node = self.head
node_total = 0
while (current_node != None):
node_total += 1
current_node = current_node.next
return node_total
def is_empty_list(self):
'''Checks if a linked list is empty.'''
return self.head == None
def stack_insert(self, data):
'''Inserts a node at the HEAD of the list;
LIFO (Last In, First Out).'''
new_node = Node(data)
# Makes new_node.next point to next node (defualt None if 1st insertion)
new_node.next = self.head
# Makes the HEAD of linked list point to new node
self.head = new_node
if (self.foot == None):
# First insertion into linked list; node becomes HEAD & FOOT
self.foot = new_node
def queue_append(self, data):
'''Appends a node at the FOOT of the list;
FIFO (First In, First Out).'''
new_node = Node(data)
if (self.head == None):
# First insertion into linked list; node becomes HEAD & FOOT
self.head = self.foot = new_node
else:
# Makes the original last node point to the newly appended node
self.foot.next = new_node
# Makes the newly appended list as the official FOOT of the linked list
self.foot = new_node
def insert_after(self, data, index):
'''Inserts a NEW node AFTER a specific node indicated by index.'''
# Need to ensure provided index is within range
if (index < 0):
print("ERROR: 'insert_after' Index cannot be negative!")
return
elif (index > (self.length() -1)):
print("ERROR: 'insert_after' Index exceeds linked list range!")
return
# Use stack_insert to insert as first item
elif (self.is_empty_list()) or (index == 0):
self.stack_insert(data)
return
# Use queue_insert to append as last item
elif (index == (self.length() -1)):
self.queue_append(data)
return
new_node = Node(data)
prior_node = self.head
current_node = self.head
search_index = 0
# Keep traversering through nodes until desired node
while (search_index != index):
prior_node = current_node
current_node = current_node.next
search_index += 1
# Makes prior node is point to target node
prior_node = current_node
# Makes current node point to the node AFTER target node (default None of last node)
current_node = current_node.next
# Makes target node point to newly added node
prior_node.next = new_node
# Makes newly added node point to original node that WAS AFTER target node
new_node.next = current_node
def delete_head(self):
'''Deletes the HEAD node.'''
# Linked list is empty
if self.is_empty_list():
return
old_head = self.head
# Adjusts the head pointer to step past original HEAD
self.head = self.head.next
if (self.head == None):
# The only node just got deleted
self.foot = None
def delete_foot(self):
'''Deletes the FOOT node.'''
# Linked list is empty
if self.is_empty_list():
return
old_foot = self.foot
prior_node = self.head
current_node = self.head
# Need to keep cycling until final node is reached
while (current_node.next != None):
prior_node = current_node
current_node = current_node.next
# Adjust newly FOOT node to point to nothing
prior_node.next = None
# Makes linked list forget about original FOOT node
self.foot = prior_node
def delete_node(self, index):
'''Deletes a target node via index.'''
# Linked list is empty
if self.is_empty_list():
return
# Need to ensure index is within proper range
elif (index < 0):
print("ERROR: 'delete_node' Index cannot be negative!")
return
elif (index > (self.length() -1)):
print("ERROR: 'delete_node' Index exceeds linked list range")
return
prior_node = self.head
current_node = self.head
search_index = 0
# Keep travsersing though nodes until desired node
while (search_index != index):
prior_node = current_node
current_node = current_node.next
search_index += 1
# Adjusts node PRIOR to target node to point to the node the AFTER target node
prior_node.next = current_node.next
def update_node(self, new_data, index):
'''Updates target node data via index.'''
# Linked list is empty
if self.is_empty_list():
print("ERROR: 'update_node' Linked list is empty; no node data to update!")
return
# Need to ensure index is within proper range
elif (index < 0):
print("ERROR: 'update_node' Index cannot be negative!")
return
elif (index > (self.length() -1)):
print("ERROR: 'update_node' Index exceeds linked list range!")
current_node = self.head
search_index = 0
# Keep traversing through nodes until desired node
while (search_index != index):
current_node = current_node.next
search_index += 1
# Can now change data
current_node.data = new_data
def get_node_data(self, index):
'''Extracts that data from a specific node via index.'''
# Linked list is empty
if self.is_empty_list():
print("ERROR: 'update_node' Linked list is empty; no node data to update!")
return
# Need to ensure index is within proper range
elif (index < 0):
print("ERROR: 'update_node' Index cannot be negative!")
return
elif (index > (self.length() -1)):
print("ERROR: 'update_node' Index exceeds linked list range!")
# Index matches HEAD or FOOT
if (index == 0):
return self.head.data
elif (index == (self.length() -1)):
return self.foot.data
current_node = self.head
search_index = 0
# Keep traversing though nodes until desired node
while (search_index != index):
current_node = current_node.next
search_index += 1
return current_node.data
1 ответ
Ваш код выглядит не-Pythonic, потому что вы используете такие методы, как length
довольно глупые методы, такие как __len__
.
Узел
Перед этим мы можем изменить Node
использовать dataclasses
. dataclasses
автоматически предоставит вашему классу шаблон, например __init__
и __repr__
. Использовать dataclasses.dataclass
вам нужно ввести свой класс. Для ввода атрибутов мы можем использовать attr: type
.
from typing import Any
class Node:
data: Any
next: "Node"
# ...
Следует отметить две важные части;
- ты должен постараться не использовать
Any
при этом уничтожается информация о типе. Вместо этого мы можем использоватьtyping.TypeVar
иtyping.Generic
. И - мы заключили тип
Node
в строке. До того, как аннотации типов Python 3.10 будут активно оцениваться. Поскольку мы используем имяNode
передNode
был назначен, если бы мы этого не сделали, тип не разрешился бы. Мы можем использоватьfrom __future__ import annotations
чтобы Python автоматически использовал ленивую оценку из Python 3.7+.
from __future__ import annotations
from typing import Generic, TypeVar
T = TypeVar("T")
class Node(Generic[T]):
data: T
next: Node
# ...
Теперь мы можем изменить класс, чтобы использовать dataclasses.dataclass
. Поскольку мы хотим не предоставлять next
в __init__
мы можем назначить None
к next
, так что next
по умолчанию None
если ничего не предусмотрено.
import dataclasses
@dataclasses.dataclass
class Node(Generic[T]):
data: T
next: Node = None
ll = Node(0, Node(1)) # example usage
print(ll)
Node(data=0, next=Node(data=1, next=None))
Хороший вывод помогает значительно упростить отладку, поскольку теперь мы можем просто напечатать self.head
(в LinkedList
), чтобы иметь возможность визуально отладить любые неправильные состояния. По умолчанию __repr__
также автоматически обрабатывает рекурсию, чтобы помочь при отладке.
ll.next.next = ll
print(ll)
Node(data=0, next=Node(data=1, next=...))
Примечание: ...
просто означает, что здесь есть рекурсия, мы бы получили тот же результат, если бы назначили ll.next
скорее, чем ll
.
Связанный список
Итерация
def length(self): '''Returns the length of a linked list.''' current_node = self.head node_total = 0 while (current_node != None): node_total += 1 current_node = current_node.next return node_total
Есть несколько способов length
не является Pythonic:
Для единообразия всегда используйте
"""triple double quotes"""
вокруг строк документации.Вы должны использовать
is
при сравнении с одиночками, такими какNone
.Пожалуйста, не используйте ненужные скобки.
while current_node is not None:
Имя вашего метода должно быть
__len__
как тогда вы можете использоватьlen(obj)
скорее, чемobj.length()
. Это может помочь сделатьLinkedList
капля на замену скажемlist
.Я бы определил функция генератора для перебора связанного списка. Использование функции генератора может значительно упростить ваш код. Затем мы можем использовать стандартные итераторы Python, например
for
иsum
вместо.
def __iter__(self):
curr = self.head
while curr is not None:
yield curr.data
curr = curr.next
def __len__(self):
"""Returns the length of a linked list."""
return sum(1 for _ in self)
Вставка
Вместо дефолта head
, и foot
, к None
мы можем по умолчанию Node(None)
. Затем мы можем упростить ваш код, избавившись от всех if self.head is None
код.
def queue_append(self, data):
self.foot.next = Node(data)
self.foot = self.foot.next
Примечание: Если вы добавите заголовок по умолчанию, вам нужно будет изменить __iter__
чтобы не возвращать голову по умолчанию. Однако нам не нужно менять __len__
, потому что __len__
основан на __iter__
!
Вставка в голову также останется простой. Изменения, которые мы внесли в Node
также может упростить код.
def stack_insert(self, data):
self.head.next = Node(data, self.head.next)
if self.foot is self.head:
self.foot = self.head.next
Я бы внес некоторые изменения insert_after
:
Вместо того, чтобы использовать
stack_insert
иqueue_append
код будет намного проще строить с нуля.С
length
, или же__len__
, должен перебирать связанный список, вызов функции не слишком полезен.Любой прирост производительности от
queue_append
теряется при использованииlength
.Позвонив
stack_insert
при вводе 0 ваш код склонен к ошибкам.ll = LinkedList() ll.queue_append("a") ll.insert_after("b", 0) ll.insert_after("c", 1) print(ll.head)
Node(data="b", next=Node(data="a", next=Node(data="c", next=None)))
Теперь, когда у связанного списка всегда будет корень
Node
мы можем легко изменить функцию на вставку до, а не после.Вам следует
raise
ошибки не печатаются.
Во всем я бы следил ЦЕЛОВАТЬ.
def insert(self, index, value):
if index < 0:
raise IndexError("cannot work with negative indexes")
curr = self.head
for _ in range(index):
curr = curr.next
if curr is None:
raise IndexError(f"index, {index}, is out of range")
curr.next = Node(value, curr.next)
if curr is self.foot:
self.foot = curr.next
Сейчас же stack_insert
выглядит совершенно ненужным; мы можем просто использовать LinkedList.insert(0, ...)
вместо. Также, если мы изменили __len__
чтобы вернуться из константы, мы могли бы изменить код, чтобы не было заметной выгоды от queue_append
.
Удаление
Вместо того, чтобы сталкиваться с теми же проблемами, что и вставка, мы должны просто игнорировать delete_head
и delete_foot
.
Поскольку код для поиска текущего узла или предыдущего узла для удаления точно такой же, мы можем заставить функцию возвращать желаемый узел.
def _index(self, index):
if index < 0:
raise IndexError("cannot work with negative indexes")
curr = self.head
for _ in range(index):
curr = curr.next
if curr is None:
raise IndexError(f"index, {index}, is out of range")
return curr
Теперь нам просто нужно убедиться, что следующий значение нет None
поскольку индекс будет вне допустимого диапазона. И убедитесь, что мы обновляем self.foot
.
def delete_node(self, index):
prev = self._index(index)
if prev.next is None:
raise IndexError(f"index, {index}, is out of range")
if prev.next is self.foot:
self.foot = prev
prev.next = prev.next.next
Получение / обновление
Не должно быть сюрпризов. Мы просто звоним self._index
и обрабатывать узел, однако, необходимо.
Питонизмы
Мы можем использовать методы обмана контейнера:
get_node_data
->__getitem__
update_node
->__setitem__
delete_node
->__delitem__
Распространенная идиома Python: отрицательные числа означают «идти с конца». Мы легко можем изменить
_index
для обработки негативов, а не ошибок.Вам следует переименовать
is_empty_list
к__bool__
чтобы позволить достоверную проверку вашего связанного списка.Вы должны имитировать имена существующих типов данных, например
list
или жеcollections.deque
. Примечание: вам следует нет подражать именамqueue.Queue
или жеmultiprocessing.Queue
; оба класса используются для другого шаблона, чем ваш код.stack_insert
->appendleft
.queue_append
->append
.delete_head
->popleft
.delete_foot
->pop
.
from __future__ import annotations
import dataclasses
from typing import Generic, TypeVar
T = TypeVar("T")
@dataclasses.dataclass
class Node(Generic[T]):
data: T
next: Node = None
class LinkedList:
def __init__(self):
self.head = self.foot = Node(None)
self._length = 0
def __iter__(self):
curr = self.head.next
while curr is not None:
yield curr
def __len__(self):
return self._length
def __bool__(self):
return self.head.next is None
# You don't need max if you don't want to make a doubly
# linked list with a foot node like the head node
def _norm_index(self, index, min=0, max=0):
index += min if 0 <= index else max
index = len(self) + 1 + index if index < 0 else index
if index < min:
raise IndexError("out of range min")
if len(self) + max < index:
raise IndexError("out of range max")
return index
def _index(self, index, min=0, max=0):
try:
_index = self._norm_index(index, min, max)
if _index == len(self):
return self.foot
curr = self.head
for _ in range(_index):
curr = curr.next
if curr is None:
raise IndexError("curr is None")
return curr
except IndexError as e:
raise IndexError(f"index, {index}, is out of range").with_traceback(e.__traceback__) from None
def __getitem__(self, index):
return self._index(index, min=1).data
def __setitem__(self, index, value):
curr = self._index(index, min=1)
curr.data = value
def __delitem__(self, index):
prev = self._index(index - 1 if index < 0 else index)
if prev.next is None:
raise IndexError(f"index, {index}, is out of range")
if prev.next is self.foot:
self.foot = prev
self._length -= 1
prev.next = prev.next.next
def insert(self, index, value):
curr = self._index(index)
self._length += 1
curr.next = Node(value, curr.next)
if curr is self.foot:
self.foot = curr.next
def append(self, value):
self.insert(-1, value)
def appendleft(self, value):
self.insert(0, value)
def pop(self):
del self[-1]
def popleft(self):
del self[0]