Python LinkedList deletion method not working

Question

This is my node:

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

And this is the LinkedList itself:

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()

Finally, these are the tests I'm performing:

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))

I am currently getting this output:

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

But I SHOULD be getting this output:

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

2 should be deleted and the LinkedList should all appear on one line. Any idea why the deletion function isn't working? Also how could I properly format this?

Martijn Pieters · Accepted Answer · 2017-09-05 06:43:18Z

Your error in deleting is here:

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

For the node with value 2, there is no prev_node (it's at the head of the link), so you assign the node itself to self.root. You should assign the next node instead:

  self.root = this_node.get_next()

Next, your search code modifies your linked list; it assigns the first node to self.root, and then always return None immediately when no match is found on that first node:

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

Don't do that! You want this_node to be replaced instead, and only return None after the while loop has completed:

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

As for printing; you are using a print() call per node, so either tell it to put spaces between nodes, or collect all node values into a list before printing:

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()

or

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

Note that there is little point in giving Node getters and setters; just access the next and data attributes directly, like you already do in some places.

Together, with these changes the output becomes:

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

Collectives™ on Stack Overflow

Python LinkedList deletion method not working

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related