Python singly linked list - removing an element

Question

for some reason my remove_element method does not delete ALL nodes containing an element. Why?

class Node:
    def __init__(self, element):
        self.element = element
        self.next = None

class SLL:
    def __init__(self):
        self.head = None

    # add a node to front
    def add_front(self, element):
        new_node = Node(element)
        if self.head == None:
            self.head = new_node
        else:
            new_node.next = self.head
            self.head = new_node

    # removes from the head
    def remove(self):
        if self.head == None:
            print "Error: the list is empty."
        else:
            self.head = self.head.next

    # removes all nodes which hold a given element
    def remove_element(self, element):
        previous = None
        cursor = self.head

        while cursor != None:
            if cursor.element == element:
                if cursor == self.head:
                    self.remove()
                else:
                    previous.next = cursor.next

            previous = cursor
            cursor = cursor.next

    # traverses the list and prints out its elements
    def print_list(self):
        cursor = self.head
        while (cursor != None):
            print(cursor.element)
            cursor = cursor.next

# Main
SLL = SLL()
SLL.add_front(21)
SLL.add_front(21)
SLL.add_front(1)
SLL.add_front(1)
SLL.add_front(1)
SLL.add_front(2)
SLL.add_front(3)
SLL.add_front(5)
SLL.add_front(8)
SLL.add_front(13)
SLL.add_front(21)
SLL.print_list()
print
SLL.remove_element(1)
SLL.print_list()
print

Output:

bash-3.2$ python SLL.py 
21
13
8
5
3
2
1
1
1
21
21

21
13
8
5
3
2
1 <--- What is this guy doing here?
21
21

Why are you implementing a linked list in Python? Unless it's a homework assignment there's no good reason to do this. Also, PEP8 suggests to use is and is not when comparing to None. — ThiefMaster
– ThiefMaster, Commented Dec 8, 2013 at 13:22
@ThiefMaster thanks, will have to read the whole style suggestions document. — chuckfinley
– chuckfinley, Commented Dec 8, 2013 at 13:24
As a bonus task once everything is working it'd be a nice idea to add add some __*__ methods like __iter__ and __contains__ so you can use the common operators/statements (if foo in bar, for foo in bar, etc.) on your structure. — ThiefMaster
– ThiefMaster, Commented Dec 8, 2013 at 13:25

chuckfinley · Accepted Answer · 2013-12-08 14:04:20Z

2

You don't need to move the previous variable reference when you're removing an element:

while cursor != None:
    if cursor.element == element:
        if cursor == self.head:
            self.remove()
        else:
            previous.next = cursor.next                
    else:
        previous = cursor

    cursor = cursor.next

Otherwise, every time you remove an element, you skip the next element by reassigning previous and cursor variables.

edited Dec 8, 2013 at 14:04

chuckfinley

2,59510 gold badges34 silver badges42 bronze badges

answered Dec 8, 2013 at 13:44

aga

29.6k13 gold badges91 silver badges127 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

interjay Over a year ago

cursor still needs to be changed.

chuckfinley Over a year ago

Infinite loop :) But thanks, i get the idea - i just need to adjust the cursor

aga Over a year ago

@interjay, yes, there was an indentation issue also. thanks for pointing out the mistake!

Collectives™ on Stack Overflow

Python singly linked list - removing an element

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related