使用单链表，如何在python中交换节点? [英] Using single linked lists, how to swap nodes in python?

问题描述

目前，我一直在尝试根据我的主函数 switch(myList,index) 重新排列一个链表.

Currently, I've been trying to rearrange a linked list based on my main function switch(myList,index).

def createList(plist):
    linkedList = None
    # goes backwards, adding each element to the beginning
    # of the list.  
    for index in range(len(plist)-1, -1, -1):
        linkedList = insertValueHead(linkedList, plist[index])
    return linkedList

def insertValueHead(linkedList, value):
    newnode = {}
    newnode["data"] = value
    #set the next pointer of this new node to the head of the list, linkedList
    #newnode is now the head of the list 
    newnode["next"] = linkedList
    return newnode

def listString(linkedList):
   ptr = linkedList
   str1 = ''
   while ptr != None:
     str1 += str(ptr['data'])
     ptr = ptr['next']
     if ptr != None:
      str1 += "->"
  str1 = str1
  return str1

def switch(j, i):
   head = j
   currentItem = j[0]     # The head again
   prevItem = 1       # The item that links to tempItem
   for x in range(i):    # Find the item to swap
        prevItem = currentItem
        currentItem = currentItem['next']
        currentItem = currentItem['next']
        temp = currentItem['next']
        currentItem['next'] = head['next']
        head['next'] = prevItem['next']
        prevItem['next'] = temp

def testSwitch():
    #test code to ensure that switch() is working correctly.
    myList = createList([10, 20, 30, 40, 50, 60])
    print "The initial list", listString(myList)
    myList = switch(myList, 2)
    print "Switching the 1 and the 2.  Resulting list is ", listString(myList)

testSwitch()

这应该产生一个包含交换元素的列表.但是，当我运行它时，这是输出:

This should yield a list with swapped elements. However, when I run it this is the output:

The initial list 10->20->30->40->50->60
Switching the 1 and the 2.  Resulting list is 

然后是错误:

    currentItem = currentItem['next']
TypeError: list indices must be integers, not str

我做错了什么?我似乎无法弄清楚...

What am I doing wrong? I can't seem to figure it out...

推荐答案

如果你需要支持 switch 操作，简单链表并不是一个非常有用的结构.在双向链表上，如果节点有向前和向后的指针，那么这很容易，但在单向链表上，您至少需要扫描一次列表.另外，你的代码太乱了，没人能真正调试它.于是

The simply-linked list is not a very useful construct, if you need to support switch operation. On a doubly linked list, if the nodes have the pointers forward and backward, then it is very easy, but on singly linked list you need to scan the list at least once. Also, your code is so messy that no one can really debug it. Thus

• 使用基于类的列表，而不是使用 Node 子类的项目.
• 对于switch 操作，您非常希望拥有双向链表.也许使用 linux 链表约定，其中末端也是一个列表节点

• use class-based lists instead having items of a Node subclass, say.
• for switch operation you seriously want to have doubly linked list. Maybe use the linux linked list convention, where the ends are a list node too

类似的东西

 class Node(object):
     prev = None
     next = None

 class List(object):
     def __init__(self):
         self.head = self
         self.tail = self
         self.prev = self
         self.next = self
         self.nil = self

     def insert_head(self, node):
         node.next = self.head.next
         self.head.next.prev = node
         node.prev = self.head
         self.head.next = node

     def __iter__(self):
         current = self.head.next
         while current != self.nil:
             yield current
             current = current.next

     def __str__(self):  # the "list_string" op
         items = []
         return ' -> '.join(map(str, self))

 class TestNode(Node):
     def __init__(self, value):
         self.value = value

     def __repr__(self):
         return repr(self.value)

list = List()
list.insert_head(TestNode('a'))
list.insert_head(TestNode('b'))
print(list)

这篇关于使用单链表，如何在python中交换节点?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！