Modifying a Linked List

We've now learned how to build and traverse a linked list, but there is still one broad class of algorithms we still need to talk about: modifying an existing linked list.

Deleting a node from a linked list

Watch the following video to see how to delete a node from a linked list:

Inserting a node in a linked list

Instead of adding a new node to the beginning or end of a linked list, we may wish to add a node in the middle of the list -- at position i.

Using what you learned from the node deletion video above, try implementing the insert() function below. The function should create a new node with the value new_val, and insert the node into position i of the linked list. For example, if the list contains the string 'rat', then insert('f', 2) should change the linked list so that it contains the string 'raft'.

If there is no position i of the list (i.e., the list is not long enough), the function should just add the node at the end of the list.

Remember to update self.head (and as an extra challenge, self.tail) if needed.

def insert(self, new_val, i):
    new_node = LLString.Node(new_val, None)
    trav = self.head
    prev = None

    if i < 0:
        return

    if trav is None:
        # list is empty
        self.head = new_node
        self.tail = new_node
        return

    num = 0
    while num < i:
        prev = trav
        trav = trav.next
        num += 1
        if trav is None:
            # add to the end
            prev.next = new_node
            self.tail = new_node
            return

    if i == 0:
        new_node.next = self.head
        self.head = new_node
    else:
        new_node.next = trav
        prev.next = new_node