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

4.1. Kinds of Linked List

There are three basic kinds of linked list: singly-linked lists, doubly-linked lists and circularly-linked lists. Although most problems involve singly-linked lists, which are the simplest to implement — an example is shown in Figure 4-1 — it's important to understand the other two kinds as well.

Figure 4.1. Figure 4-1

When an interviewer says "linked list" he or she generally means a linear singly-linked list. This list consists of a number of data elements in which each data element has a next pointer or next reference (the link) to the element that follows. The last element in the list has an empty or null link.

In C or C++, an element's next pointer and the data the element holds are usually bound together as a single unit, as shown in the following example:

typedef struct IntElement {
    struct IntElement *next;
    int                data;
} IntElement;

Placing the next pointer at the beginning of the structure or class makes it easy to write generic list-handling routines that work no matter what data the element holds.

In other languages it's more common to create generic linked list routines whose elements store references to arbitrary objects. In Java or C# it might be a simple class like this:

public class ListElement {
    ListElement next;
    Object      data;

    public ListElement( Object data ){
        this.data = data;
    }
}

Although there's more overhead in this scenario, it works ...