Связанные списки Python 2.7

Question

У меня проблемы с попыткой реализации связанного Списка без использования классов (мы еще не пришли в мой курс), и Google вообще не помог.Каждый пример связанного списка использует классы, которые я не рассмотрел.Я могу создать связанный список, который добавляет значение в начало связанного списка, но я не знаю, как просмотреть список и добавить значение после определенного узла.Любая помощь будет оценена.Самое сложное для меня - выяснить, как пройти список.

def addValue(linkedSet, value):
    """
    Adds a new element to a set.
    Parameters:
        the set to be changed (address of the first node)
        the new value to add to the set
    Return result: pointer to the head of the modified set.  This is
        usually the same as the linkedSet parameter, unless the value
        added is less than any value already in the set.

    If the value is already in the set, return the set unchanged.
    This is not an error.
    """
    newNode={}
    newNode['data']=value
    node=linkedSet
    if linkedSet==None:
        newNode['next']=None
        return newNode
    if member(linkedSet,value)==True:
        return linkedSet
    elif linkedSet['next']==None:
        newNode['next']=None
        linkedSet['next']=newNode
    elif linkedSet['next']!=None:
        return linkedSet

Answer 1

Так же, как общий план того, как я думаю, ваша функция addValue () может выглядеть как ...

def addValue(linkedSet, value):

    newNode={
        'data': value,
        'next': None
    }

    # if linkedSet is None, then you can just return this newNode

    # if linkedSet isnt None...
        # if linkedSets next is None, then it should just point to this newNode 
        # (append)

        # otherwise, you should set its current next to the next of this newnode,
        # and then set its next to this newNode (insert)

Это для общего связанного списка. Похоже, вы предполагаете, что ваша версия является более специализированной, которая поддерживает сортировку значений и всегда ожидает, что будет передан головной узел списка. Ваша будет требовать постоянного зацикливания каждого «следующего» до тех пор, пока не найдет тот, где значение будет больше текущего, а затем вставит себя, перемещаясь вокруг «следующих» ссылок следующих (и, возможно, предыдущих) элементов.

Answer 2

unless the value added is less than any value already in the set звучит так, как будто этот список должен быть отсортирован. Итак, вы просматриваете список, находите первый элемент, который больше вашего значения, и склеиваете его там.

Вы просматриваете список, отслеживая текущий узел:

def addValue(linkedSet, value):

    newNode={}
    newNode['data']=value
    newNode['next'] = None

    #traverse list
    current = linkedSet
    while True: 
        if current['value'] == value: 
            return linkedSet # it was already in that list

        if current['value'] > value:
            # new node is the new head
            newNode['next'] = linkedSet
            return newNode # new head

        if current['next'] is None:
            # new tail
            current['next'] = new_node
            return linkedSet

        if current['next']['value'] > value:
            # new node belongs here, splice it in
            next_node = current['next']
            current['next'] = newNode
            newNode['next'] = next_node
            return linkedSet

        # didnt return so far, try the next element:
        current = current['next']

Answer 3

Как насчет использования словаря в качестве дескриптора связанного списка?Что-то вроде:

linkedSet = {'first':firstNode, 'last':lastNode}

Тогда, когда вам нужны переходы, вы всегда можете начать с первого узла, а когда вам нужно добавить, у вас есть конечный узел.