Chapter 4: Linked Lists

The deceptively simple linked list is the basis for a surprising number of problems regarding the handling of dynamic data. Problems about efficient list traversal, list sorting, and the insertion or removal of data from either end of a list are good tests of basic data-structure concepts, which is why we devote an entire chapter to linked lists. Their simplicity appeals to interviewers, who want to present at least two or three problems over the course of an hour-long interview. This means that they have to give you problems that you can be reasonably expected to answer in 20 to 30 minutes. You can write a relatively complete implementation of a linked list in less than 10 minutes, leaving you plenty of time to solve the problem. In contrast, it might take you most of the interview period to implement a more complex data structure such as a hash table. In addition, there is little variation in the way linked lists are implemented, which means that an interviewer can simply say “linked list” and not waste time discussing and clarifying implementation details.

Linked list problems are typically posed for jobs requiring C or C++ experience because they’re an easy way to determine whether a candidate understands how pointers work, so most of the examples in this chapter are in C++, but without any use of C++’s object-oriented programming facilities. It’s assumed that you’re using a C++ compiler so that you can use the C++ new and delete operators in your code.

If you’re not experienced with C or C++, you may find the linked lists problems in this chapter quite challenging, especially because languages such as Java and C# provide linked list implementations as standard library routines. Still, linked lists are so basic that we suggest you familiarize yourself with them before moving on to the more-complicated data structures found in the following chapters.

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

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 well in languages where unused objects are automatically found and destroyed via garbage collection. Otherwise, careful attention must be paid to the allocation and deallocation of any referenced objects.

Whatever language they are implemented in, singly-linked lists have a host of special cases and potential programming traps. 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, so 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 in order to locate all the elements in the list. Consequently, the term linked list is often used as shorthand for the first element of a linked list. If an interviewer says that a function takes a linked list as an argument, he or she probably means that it takes a pointer/reference to the first element of a linked list as an argument.

The first element of a singly-linked list is referred to as the head of the list; the last element is referred to as the tail element.

Doubly-Linked Lists

A doubly-linked list, shown in Figure 4-2, eliminates many difficulties inherent in a singly-linked list. A doubly-linked list differs from a singly-linked list in that each element has a link to the previous element in the list in addition to the link to the next element. (The first element in the list has an empty or null previous link.) This additional link makes it possible to traverse the list in either direction. The entire list can be traversed starting from any element. A doubly-linked list has head and tail elements just like a singly-linked list.

Figure 4-2

Because many list operations that are difficult with singly-linked lists are trivial when bidirectional links are available, doubly-linked lists are rarely seen in interview problems; and if the problem isn’t any easier with a doubly-linked list, there’s no point in adding the overhead of bidirectional links.

Circularly-Linked Lists

The final variation on the linked list theme is the circularly-linked list, which comes in singly- and doubly-linked varieties. Circularly-linked lists have no ends - no head or tail. The primary traversal problem is cycle avoidance - if you don’t track where you start, you’ll cycle infinitely through the list. Although they have some interesting properties, circularly-linked lists rarely appear in interview problems.