Trouble with removing nodes in Python double linked list

Question

I have been trying to create a double linked list in Python for a little while now, but am having trouble with a few methods within my LinkedList class. I would like my removeFront and removeRear methods to return the value that is removed, but I cannot get this to work. With a test list, the if I enter some value x into a node and try to remove it, x is not returned.

I believe the idea for removing a node is to cut it out of the list by connecting its next node with its previous node, but have a feeling my attempt at this is fundamentally flawed.

I am also trying to implement a pop method (to remove a specific element in the list) but am not sure where to start. Any advice to nudge me in the right direction here would be appreciated. Thank you.

class Node:

    def __init__(self,data):
        self.data = data
        self.next = None
        self.prev = None

class LinkedList:

    def __init__(self):
        self.front = None
        self.rear = None

    def isEmpty(self):
        return self.front is None and self.rear is None

    def addFront(self, data):
        new_node = Node(data)
        if self.front is None:
            self.front = new_node
            self.rear = self.front
            self.front.prev = None
            self.rear.next = None
        else:
            self.front.prev = new_node
            new_node.next = self.front
            self.front = new_node
            self.front.prev = None

    def addRear(self, data):
        new_node = Node(data)
        if self.front is None:
            self.rear = new_node
            self.front = self.rear
            self.front.prev = None
            self.rear.next = None
        else:
            self.rear.next = new_node
            new_node.prev = self.rear
            self.rear = new_node
            self.rear.next = None

    def removeFront(self):
        if self.isEmpty():
            return None
        else:
            removed = self.front
            self.front.prev = self.front
            self.front.prev.next = None
            return removed

    def removeRear(self):
        if self.isEmpty():
            return None
        else:
            removed = self.rear
            self.rear.prev = self.rear
            self.rear.prev.next = None
            return removed

    def pop(self, index):
        # TODO: How to implement?
        pass

    def size(self):
        current = self.front
        count = 0
        while current is not None:
            count += 1
            current = current.next
        return count

Answer 1

Quick code review:

• Node.__init__() is correct.
• LinkedList.__init__() is correct.
• LinkedList.isEmpty() is correct.
• LinkedList.size() is correct.

---

Here is how to implement LinkedList.removeFront() properly:

    def removeFront(self):
        if self.isEmpty():
            return None
        else:
            removed = self.front.data
            self.front = self.front.next
            if self.front is None:  # List size was 1
                self.rear = None
            else:
                self.front.prev = None
            return removed

I will leave the implementation of removeRear() as an exercise to you. The logic is symmetrical to removeFront().

---

LinkedList.addFront() is correct, but can be simplified:

    def addFront(self, data):
        new_node = Node(data)
        if self.front is None:
            self.front = new_node
            self.rear = new_node
            #self.front.prev = None  # Already None
            #self.rear.next  = None  # Already None
        else:
            self.front.prev = new_node
            new_node.next = self.front
            self.front = new_node
            #self.front.prev = None  # Already None

Your LinkedList.addRear() is correct, but can be simplified in the same way.

---

You asked about how to implement LinkedList.pop(). It will be a tricky one. You have to consider multiple cases:

• What if the list has exactly one element?
• What if the node to be removed is at the front?
• What if the node to be removed is at the rear?
• What if the node to be removed is strictly in the middle?

Answer 2

Here's an implementation of removeFront with comments:

def removeFront(self):
    if self.isEmpty():
        return None

    # Store data so that it can be returned
    data = self.front.data
    if self.front == self.rear:
        # List contains one item, set front & rear to initial state
        self.front = self.rear = None
    else:
        # More than one item
        self.front = self.front.next    # Set front to point next item
        self.front.prev = None          # Front doesn't have previous item

    return data

removeRear works exactly with the same logic.

In order to implement pop you need to consider three different cases:

• Front is being removed
• Rear is being removed
• Node between front and rear is being removed

No matter what case is in question you still need to find the right node to remove. You can do this in a loop while advancing in the list. Once you have found the correct node you can utilize removeFront or removeRear in case it's first or last node. If node falls somewhere between you need cut it from previous & next node and join the remaining nodes together.