Python 3 - Using recursion in a linked list

Question

Python 3 - I am new to coding and am finding recursion difficult. I'm making a linked list class with recursive methods for adding and removing items from the list. Right now, I am unable to remove an item if it happens to be the first item in my list. I wrote some alternative code which could remove the first item from the list if I included another parameter (previous) and another base case, but then I could only remove the first item and spent way too long trying to figure out why so I scrapped that entirely. I would appreciate a hint!

Also, I am already aware that I have getters and am not using them properly.

class Node:
    """
    Represents a node in a linked list
    """
    def __init__(self, data):
        self._data = data
        self._next = None

    def get_data(self):
        """getter method for data in Node class"""
        return self._data

    def get_next(self):
        """getter method for next in Node class"""
        return self._next
class LinkedList:
    """
    A linked list implementation of the List ADT
    """
    def __init__(self):
        self._head = None

    def get_head(self):
        """getter function for head of list"""
        return self._head

    def add(self, val):
        """ Adds a node containing val to the linked list - helper function"""
        self._head = self.recursive_add(self._head, val)

    def recursive_add(self, node1, val):
        """ Adds a node containing val to the linked list """
        if node1 is None:
            return Node(val)
        else:
            node1._next = self.recursive_add(node1._next, val)
            return node1

    def remove(self, val):
        """removed the node containing val from the linked list - helper function"""
        self.recursive_remove(self._head, val)

    def recursive_remove(self, node1, val):
        """
        Removes the node containing val from the linked list
        """
        if node1 is None:
            return node1
        elif node1._data == val:
            return node1._next
        else:
            node1._next = self.recursive_remove(node1._next, val)
            return node1

    def main():
       my_list = LinkedList()
       my_list.add(13)
       my_list.add(9)
       my_list.add(5)
       my_list.remove(9)
    


if __name__ == '__main__':
    main()

If you use recursion, your code won't be able to handle lists longer than 1000 elements in CPython. Better to use loops, although I presume this is purely for pedagogical purposes. Can you not make an assignment to the head in self.recursive_remove(self._head, val)? — ggorlen
– ggorlen, Commented Nov 10, 2021 at 6:11
Haha now I guess there is a course using the same linked list class: stackoverflow.com/questions/69908090/… — j1-lee
– j1-lee, Commented Nov 10, 2021 at 6:11
To remove a given node, simply say that node.next = node.next.next. Or if you are trying to remove the first node, you can just say node = node.next — Larry the Llama
– Larry the Llama, Commented Nov 10, 2021 at 6:16

Ammar Aslam · Accepted Answer · 2021-11-10 07:08:19Z

1

    def remove(self, val):
        """removed the node containing val from the linked list - helper function"""
        if self._head and self._head._data == val:
            self._head = self._head._next
            return
        self.recursive_remove(self._head, val)

if its at the start, the head needs to be changed.

answered Nov 10, 2021 at 7:08

Ammar Aslam

6704 silver badges17 bronze badges

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

Comments

trincot · Accepted Answer · 2021-11-10 15:02:44Z

In remove you call recursive_remove, but ignore its return value. You should use it as the (potentially different) _head reference, must like is done in the recursive method itself, where you have:

node1._next = self.recursive_remove(node1._next, val)
#       ^                                   │
#       └───────────────────────────────────┘

Note how node1._next is passed as argument, and the method's return value is the (potentially different) reference that node1._next should end up with. The same pattern should be applied in the initial call in remove:

def remove(self, val):
    self._head = self.recursive_remove(self._head, val)
#          ^                                  │
#          └──────────────────────────────────┘

NB: the same pattern is used in add, where you do it correctly.

Collectives™ on Stack Overflow

Python 3 - Using recursion in a linked list

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related