链接列表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) 

这是一个通用链表。看起来好像你在暗示你的是一个更专业的版本，它维护着一个值类型，并且总是期望被传递给列表的头节点。你的每一个'next'需要不断循环，直到找到一个值大于当前值的值，然后通过围绕下一个元素（可能还有之前的元素）的'next'引用进行插入。

Answer 2

如何使用字典作为链表描述符？ 喜欢的东西：

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

然后，当你需要斯格特你总是可以从第一个节点， 开始，当你需要添加你有你的终端节点。

Answer 3

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']