链接列表Python 2.7

Question

我在尝试在不使用类的情况下实现链表时遇到了问题（我们在课程中还没有做到），谷歌根本没有帮助。每个链表示例都使用类，我还没有介绍这些类。我可以创建一个链表，在链表的开头添加值，但我不知道如何遍历列表并在特定节点后添加值。如有任何帮助，我们将不胜感激。对我来说，最困难的部分是弄清楚如何遍历列表。

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)

这是一个通用的链表。你似乎在暗示你的版本是一个更专业的版本，它维护了一个值排序，并且总是希望被传递到列表的头节点。您的方法需要在每个"next"上进行持续循环，直到找到一个值大于当前值的值，然后通过在以下（可能还有前一个）元素的"next"引用周围移动来插入自己。

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

使用dictionary作为链表描述符怎么样？类似于：

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

然后，当您需要遍历时，您可以始终从第一个节点开始，当你需要添加时，你就有了自己的结束节点。