Modifying a linked list

Now we'll look at functions to modify the nodes that appear in the list. Adding or removing at the front of the list is easy enough.

def add_first(list_obj, value):
    list_obj.head = Node(value, list_obj.head)

def remove_first(list_obj):
    list_obj.head = list_obj.head.next

Working with the list's end is more complex. As an example, suppose we want to add a new node to the end of the list. We must first find the last node in the list (i.e., the node whose next value is None). We can accomplish this by using the same sort of search pattern we did before, where we have a variable tracking the “current” node we are looking for, which steps forward each time. One slightly tricky bit is remembering to deal with the possibility that the list is empty, where we need to change the head of the list.

def add_last(list_obj, value):
    if list_obj.head is None:
        list_obj.head = Node(value, None)
    else:
        cur = list_obj.head
        while True:
            if cur.next is None:
                cur.next = Node(value, None);
                return
            cur = cur.next

In removing the final node, we'll need to find the next-to-last node — that is, a node whose next references a node with a next of None. That next-to-last node's next will need to be changed to None. We can again do the same thing — and once again, we need to remember that the job is somewhat different when the list contains just one node (and so there is no next-to-last node).

def remove_last(list_obj):
    if list_obj.head.next is None:
        list_obj.head = None
    else:
        cur = list_obj.head
        while True:
            if cur.next.next is None:
                cur.next = None
                return
            cur = cur.next