Programming Interviews Exposed: Secrets to Landing Your Next Job, Second Edition

4.2. Basic Linked List Operations

Most linked list problems require a thorough understanding of basic operations on singly-linked lists. These operations include tracking the head element so the list doesn't get lost, traversing the list, and inserting or deleting list elements. Again, these operations are trivial with a doubly-linked list, so the problems will almost always use singly-linked lists.

4.2.1. Tracking the Head Element

The head element of a singly-linked list must always be tracked; otherwise, the list will be lost in memory. This means that the pointer or reference to the head of the list must be updated when a new element is inserted ahead of the first element or when the existing first element is removed from the list. Tracking the head element becomes a problem when you alter the list inside a function or method, because the caller must be made aware of the new head element. For example, the following Java/C# code is incorrect because it fails to update the reference to the head of the list:

public void insertInFront( ListElement list, Object data ){
    ListElement l = new ListElement( data );
    l.next = list;
}

The correct solution is to return the new head element from the method:

public ListElement insertInFront( ListElement list, Object data ){
    ListElement l = new ListElement( data );
    l.next = list;
    return l;
}

The caller simply updates its reference to the head element accordingly:

Object data = ....; // data to insert ListElement head = ....; // reference to ...