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

Kinds of Linked List

There are three basic kinds of linked list: singly linked lists, doubly linked lists, and circular linked lists. Singly linked lists are the variety most commonly encountered in interviews.

Singly Linked Lists

When an interviewer says “linked list” he or she generally means a linear singly linked list, where each data element in the list has a link (a pointer or reference) to the element that follows it in the list, as shown in Figure 4-1. The first element in a singly linked list is referred to as the head of the list. The last element in such a list is called the tail of the list and has an empty or null link.

Figure 4-1

Singly linked lists have a host of special cases and potential programming pitfalls. Because the links in a singly linked list consist only of next pointers (or references), the list can be traversed only in the forward direction. Therefore a complete traversal of the list must begin with the first element. In other words, you need a pointer or reference to the first element of a list to locate all the elements in the list. It’s common to store that pointer or reference in a separate data structure.

In C, the simplest singly linked list element is a struct with a pointer to a struct of the same type as its only member:

// The simplest singly linked list element
typedef struct ListElement {
  struct ListElement *next;
} ListElement;

Because ...