Связанный список и манипуляция

Question

Мне нужна помощь в создании LinkedList без параметров конструктора в python 3.3; в результате получается пустой объект LinkedList. Я хочу иметь возможность добавлять и удалять элементы в начале и в конце списка. Пока я могу только добавить и добавить вещи на фронт. Я немного разбираюсь в том, как все работает. Вот что у меня есть до сих пор:

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


class LinkedList: 
    def __init__(self): 
     self._head = None 
     self._size = 0 

    def __len__(self): 
     return self._size 

    def append(self, item): 
     pass 

    def prepend(self, item): 
     self._head = Node(item, self._head) 
     self._size += 1 

    def remove_first(self): 
     pass 

    def remove_last(self): 
     pass 

У кого-нибудь есть ключ? Огромное спасибо!

Answer 1

Вы можете использовать объект deque из модуля коллекций в стандартной библиотеке. Ваш метод prepend называется appendLeft в объекте deque.

В другой форме, вы можете изменить свой класс LinkedList со ссылкой на последний узел списка:

class LinkedList: 
    def __init__(self): 
     self._head = None 
     self._tail = None 
     self._size = 0 

    def append(self, item): 
     if self._tail is None: 
      self.prepend(item) 
     else: 
      self._tail.next = Node(item, None) 
      self._tail = self._tail.next 

    def prepend(self, item): 
     if self._head is None: 
      self._tail = Node(item, None) 
      self._head = self._tail 
     else: 
      self._head = Node(item, self._head) 
     self._size += 1