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

Question 1

Недавно я попытался преобразовать односвязный список из программы 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

Question 2

Ваш код выглядит не-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]

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

1 ответ
1

Узел

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

Итерация

Вставка

Удаление

Получение / обновление

Питонизмы

Добавить комментарий Отменить ответ

1 ответ 1

Узел

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

Итерация

Вставка

Удаление

Получение / обновление

Питонизмы

Похожие записи:

Добавить комментарий Отменить ответ

1 ответ
1