Python LinkedList删除方法不起作用

Question

这是我的节点：

class Node(object):
    def __init__(self, data, next = None):
      self.data = data
      self.next_node = next
    def get_next(self):
      return self.next_node
    def set_next(self, next):
      self.next_node = next
    def get_data(self):
      return self.data
    def set_data(self):
      self.data = data

这是LinkedList本身：

class LinkedList(object):
    def __init__(self, root = None):
      self.root = root
      self.size = 0
    def size(self):
      return self.size
    def insert(self, data):
      new_node = Node (data, self.root)
      self.root = new_node
      self.size += 1
    def delete(self, data):
      this_node = self.root
      prev_node = None
      while this_node:
        if this_node.get_data() == data:
          if prev_node:
            prev_node.set_next(this_node.get_next())
          else:
            self.root = this_node
          self.size -= 1
          return True
        else:
          prev_node = this_node
          this_node = this_node.get_next()
      return False
    def search(self, data):
      this_node = self.root
      while this_node:
        if this_node.get_data() == data:
          return data
        else:
          self.root = this_node.get_next()
        return None
    def printLL(self):
      this_node = self.root
      while this_node:
        print(this_node.data)
        this_node  = this_node.get_next()

最后，这些是我正在执行的测试：

ll = LinkedList()
ll.insert(1)
ll.insert(2)
ll.printLL()
ll.delete(2)
ll.printLL()
if ll.search(2):
    print("Value 2 found")
else:
    print("Value 2 not found")
if ll.search(1):
    print("Value 1 found")
else:
    print("Value 1 not found")
ll.insert(4)
ll.printLL()
print(str(ll.size))

我目前正在获取此输出：

2
1
2
1
Value 2 found
Value 1 not found
4
1
2

，但我应该得到此输出：

2 1
1
Value 2 not found
Value 1 found
4 1
2

2应该删除，链接清单应全部出现在一行上。知道为什么删除函数不起作用吗？另外，我如何正确格式化？

Answer 1

您在删除中的错误在这里：

if prev_node:
  prev_node.set_next(this_node.get_next())
else:
  self.root = this_node

对于具有值2的节点，没有prev_node（链接的头部），因此您将节点本身分配给self.root。您应该分配下一个节点：

  self.root = this_node.get_next()

接下来，您的搜索代码会修改您的链接列表；它将第一个节点分配给self.root，然后在第一个节点上找不到匹配时，立即始终返回None：

while this_node:
  if this_node.get_data() == data:
    return data
  else:
    self.root = this_node.get_next()
  return None

不要那样做！您希望更换this_node，并且仅在while循环完成后返回None：

while this_node:
  if this_node.get_data() == data:
    return data
  else:
    this_node = this_node.get_next()
return None

印刷；您使用的是每个节点的print()调用，因此要么告诉它在节点之间放置空间，要么在打印之前将所有节点值收集到列表中：

def printLL(self):
  this_node = self.root
  first = False
  while this_node:
    print(' ' if not first else '', this_node.data, sep='', end='')
    first = False
    this_node  = this_node.get_next()
  print()

或

def printLL(self):
  this_node = self.root
  values = []
  while this_node:
    values.append(this_node.data)
    this_node  = this_node.get_next()
  print(*values)

请注意，给予Node Geters和setters几乎没有意义。只需直接访问next和data属性，就像您在某些地方已经做的一样。

一起，随着这些更改，输出变为：

2 1
1
Value 2 not found
Value 1 found
4 1
2