Recursively insert node in linked list, given position and value

Question

I'm implementing a linked list containing only values, and am attempting to utilize recursion to traverse the list to insert a specific value at a specific position in the list. I've solved how to do this using a while loop, however, I'm having trouble translating this into a recursive function.

The insert method includes both the value and the index as parameters, and if the position is 0 the function will set the head node to the new value. Else, I create a new_node variable set to the head of the node and, while the position is greater than 1, new_nodeis set to the next node and index is decremented by 1. I can insert using this method but I've been unable to implement this using recursion.

My iterative solution

class Node:
    def __init__(self, data, node=None):
        self._data = data
        self._next = node

    def get_next(self):
        return self._next

    def get_data(self):
        return self._data

    def set_next_node(self, val):
        self._next = val 


class LinkedList:
    def __init__(self):
        self._head = None

    def get_head(self):
        return self._head

    def set_head(self, value):
        self._head = value

    def insert(self, value, index):
        if index == 0:
            self._head = Node(value, self._head)
            return
        new_node = self._head
        while index > 1:
            new_node = new_node.get_next()
            index -= 1
        new_node._next = Node(value, new_node.get_next())

j1-lee · Accepted Answer · 2021-11-10 05:58:32Z

0

Do you need to have separate classes for Node and LinkedList? Otherwise, you can simplify the code as follows:

class Node:
    def __init__(self, data, node=None):
        self.data = data
        self.next = node
    def __repr__(self):
        return f"{self.data}, {self.next}" if self.next else str(self.data)
    def insert(self, value, index=0):
        if self.next:
            if index == 0:
                self.next, self.data = Node(self.data, self.next), value
            else:
                self.next.insert(value, index - 1)
        else: # if terminal node, ignore index
            self.next = Node(value)

ll = Node(1, Node(3, Node(4)))
print(ll) # 1, 3, 4
ll.insert(2, 1)
print(ll) # 1, 2, 3, 4
ll.insert(5, 4)
print(ll) # 1, 2, 3, 4, 5

Basically, each Node itself represents a linked list starting from that node, which (I believe) conforms to the notion of recursiveness.

Here, insert does the real job only when index == 0, the same idea as in your iterative solution. Otherwise (if index > 0), it tosses the job to the next node with one less index (self.next.insert(value, index - 1)).

If you must maintain the Node-LinkedList structure, you can do as follows:

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

class LinkedList:
    def __init__(self, node=None):
        self.head = node
    def __repr__(self):
        values = []
        curr = self.head
        while curr:
            values.append(curr.data)
            curr = curr.next
        return ', '.join(map(str, values))
    def insert(self, value, index=0, node=None):
        node = node or self.head # if node==None, then assign self.head
        if node.next:
            if index == 0:
                node.next, node.data = Node(node.data, node.next), value
            else:
                self.insert(value, index=index-1, node=node.next)
        else: # if terminal node, ignore index
            node.next = Node(value)

ll = LinkedList(Node(1, Node(3, Node(4))))
print(ll) # 1, 3, 4
ll.insert(2, 1)
print(ll) # 1, 2, 3, 4
ll.insert(5, 4)
print(ll) # 1, 2, 3, 4, 5

Note that insert has one more state variable node. Although technically recursive, I have reservations about its beauty.

edited Nov 10, 2021 at 5:58

answered Nov 10, 2021 at 5:02

j1-lee

13.9k3 gold badges16 silver badges27 bronze badges

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

3 Comments

pc_86 Over a year ago

Yes, I must use a separate linked list and node class to implement.

j1-lee Over a year ago

@pc_86 Then I guess you cannot achieve a neat recursive form, although it is possible. I'll update the answer.

j1-lee Over a year ago

@pc_86 I've updated the answer and corrected an error.

Collectives™ on Stack Overflow

Recursively insert node in linked list, given position and value

1 Answer 1

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related