Function that iterates through a linked list

Question

class LN:
    def __init__(self,value,next=None):
        self.value = value
        self.next  = next

def list_to_ll(l):
    if l == []:
        return None
    front = rear = LN(l[0])
    for v in l[1:]:
        rear.next = LN(v)
        rear = rear.next
    return front

def add_after(ll,value,new):
    for item in ll:
        if item == value:
            ll.insert(ll.index(value),new)

I am working on an iterative function named add_after. It takes linked list and two values, value and new. It mutates the linked list such that every occurrence of the value is now followed by new. For example:

a = list_to_ll([2,1,8,2,2,4,2,5,2])

add_after(a,2,-1) results in a referring to a linked list containing the values 1->8->2->-1->4->2->-1->5->2->-1->None.

add_after(a,2,2) for the original list in a results in a referring to a linked list containing the values 1->8->2->2->4->2->2->5->2->2->None.

plus( I am not allowed to use lists, tuples, sets, or dicts in my code)

use linked lists processing only

when I run my add_after it gives me an error:

add_after(ll,2,-1)
for item in ll:
TypeError: 'LN' object is not iterable

can anyone help me to fix my add_after function? many thanks.

Answer 1

Here is my solution using recursion. I've also added a helper method flatten to visualise the changes for when I was testing.

def add_after(ll, at_value, new_value):
    if ll.value == at_value:
        ll.next = LN(new_value, ll.next)
        if ll.next is not None and ll.next.next is not None:
            # skips over the newly added LN
            add_after(ll.next.next, at_value, new_value)
    elif ll.next is not None:
        add_after(ll.next, at_value, new_value)

def flatten(ll):
    if ll.next is None:
        return [ll.value]
    return [ll.value] + flatten(ll.next)

# Output
>>> a = list_to_ll([2,1,8,2,2,4,2,5,2])
>>> flatten(a)
[2, 1, 8, 2, 2, 4, 2, 5, 2]
>>> add_after(a, 2, -1)
>>> flatten(a)
[2, -1, 1, 8, 2, -1, 2, -1, 4, 2, -1, 5, 2, -1]
>>> b = list_to_ll([2,1,8,2,2,4,2,5,2])
>>> add_after(b, 2, 2)
>>> flatten(b)
[2, 2, 1, 8, 2, 2, 2, 2, 4, 2, 2, 5, 2, 2]

Answer 2

ll is an object of user-defined class LN. It is not iterable like a list, hence a for-each construct would not work in this context.

The following would be the alternative.

def add_after(ll,value,new):
    item = ll
    while item is not None:
        if item.value == value:
            newnode = LN(new, item.next)
            item.next = newnode
            break
        else:
            item = item.next

Addressing the OP's concern on inserting at the nth occurrence, the following code can be also applicable:

def add_after(ll,value,new,occ=1):
    item = ll
    while item is not None:
        if item.value == value:
            occ -= 1
            if occ == 0:
                newnode = LN(new, item.next)
                item.next = newnode
                break
        item = item.next

The optional fourth argument determines after which occurrence should the new value be inserted. For example, add_after(ll, 2, -1, 2) adds -1 after the second occurrence of 2.

Answer 3

1. Make LN iterable, by defining __iter__ methods which yields nodes:
2. Make add_after link new node.

---

class LN:
    def __init__(self, value, next=None):
        self.value = value
        self.next  = next

    def __iter__(self):  # yield all linked node (including the first node)
        node = self
        while node is not None:
            yield node
            node = node.next

def list_to_ll(l):
    if l == []:
        return None
    front = rear = LN(l[0])
    for v in l[1:]:
        rear.next = LN(v)
        rear = rear.next
    return front

def add_after(ll, value, new):
    for item in ll:
        if item.value == value:
            ll.next = LN(new, ll.next)  # Make new node and link after current node
            break
    # TODO: Handle not-found case.


ll = list_to_ll([2,1,8,2,2,4,2,5,2])
add_after(ll, 2, -1)
for item in ll:
    print(item.value)

# Prints 2, -1, 1, 8, 2, 2, 4, 2, 5, 2

---

UPDATE after reading OP's comment => changing only add_after (manually loop through nodes):

def add_after(ll, value, new):
    node = ll
    while node is not None:
        if node.value == value:
            node.next = LN(new, node.next)
            break
        node = node.next

NOTE: I made add_after add only one node. I will leave it as your work to add multiple nodes.