вставить элемент в начало связанного списка? питон

поэтому я пытался вставить элемент в начало связанного списка, и это вроде работает, но не полностью. Вот что у меня есть (в классе LinkedList есть и другие методы, но я пропустил их, потому что они не были проблемой):

class _Node():
    def __init__(self, data=None, link=None):
        self.data = data
        self.link = link

class LinkedList():
    def __init__(self):
        self.first = None
        self.size = 0

    def insert(self, ind, item):
        if self.first is None:
            self.first = _Node(item)
        elif ind == 0:                   # this is where the problem is. When I try to 
            temp = self.first            # insert a node to the front, it seems to
            temp.link = self.first.link  # forget about the rest of the nodes.
            self.first = _Node(item)
            self.first.link = temp  
        else:
            count = 0
            while count != ind - 1:
                count += 1
                self.first = self.first.link
            self.first.link = _Node(item, self.first.link)
        self.size += 1

скажем, у меня есть это в оболочке:

    >>> L = LinkedList()
    >>> L.insert(0, 5)
    >>> L.insert(1, 10)
    >>> L.insert(0, 20)
    >>> L[0]
    20
    >>> L[1]
    5
    >>> L[2]
    # and here is an error message, it says NoneType object has no attribute 'data'

поэтому в приведенном выше коде я пытаюсь создать временный объект узла, который идентичен первому объекту узла, я связываю этот временный узел со ссылкой на первый узел, я создаю новый узел и связываю этот новый узел на временный, но это не работает. Любая помощь была бы замечательной, спасибо!


python nodes insert linked-list temporary
person peppy    schedule 11.03.2013    source источник
comment
Почему бы не использовать встроенную структуру данных?   -  person linbo    schedule 11.03.2013
comment
что ты имеешь в виду? Я новичок в программировании и делаю это для проверки перед тестом.   -  person peppy    schedule 11.03.2013
comment
Я имею в виду, что у python уже есть библиотека связанных списков   -  person linbo    schedule 11.03.2013
comment
Я не знаю, я просто должен знать, как реализовать связанный список с использованием узлов для моего теста, это единственная часть, на которой я застрял.   -  person peppy    schedule 11.03.2013

Ответы (2)


arrow_upward
2
arrow_downward

Кажется, что те функции, которые вы упустили, потому что они «не были проблемой», на самом деле могут быть вашей проблемой ...

Ваш код работает, если вы запрашиваете данные в каждом узле следующим образом:

>>> L = LinkedList()
>>> L.insert(0,5)
>>> L.insert(1,10)
>>> L.insert(0,20)
>>> print L.first.data
20
>>> print L.first.link.data
5
>>> print L.first.link.link.data
10

Вероятно, у вас возникла проблема с определением __getitem__. Кроме того, часть, которую вы прокомментировали, можно переписать в одну строку, которая может быть более Pythonic.

temp = self.first
temp.link = self.first.link
self.first = _Node(item)
self.first.link = temp

Первые две строки ничего не делают, потому что temp это self.first, поэтому все, что вы говорите, это self.first.link = self.first.link. Следующие два могут быть записаны:

self.first = _Node(item, self.first)
person Jared    schedule 11.03.2013

arrow_upward
0
arrow_downward

Во-первых, обратите внимание, что на самом деле вам не нужно специально указывать пустой список здесь:

def insert(self, ind, item):
    if ind == 0:
        newnode = _Node(item, self.first)
        self.first = newnode

Во-вторых, проблема не в этом. Этот код:

    else:
        count = 0
        while count != ind - 1:
            count += 1
            self.first = self.first.link
        self.first.link = _Node(item, self.first.link)
    self.size += 1

изменяет self.first на месте, поэтому забывает, каким был первый узел раньше. Наименьшее изменение, чтобы исправить это:

    else:
        count = 0
        insert_point = self.first # use a local variable to walk the list
        while count != ind - 1:
            count += 1
            insert_point = insert_point.link
        insert_point.link = _Node(item, insert_point.link)
    self.size += 1
person Useless    schedule 11.03.2013