datastructures

4
Linked Lists
The linked list, a deceptively simple data structure, is the basis for a surprising number of prob-
lems regarding the handling of dynamic data. Questions 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 an entire chapter is devoted to linked lists.


Why Linked Lists?
The simplicity of linked list questions appeals to interviewers who want to present at least two
or three problems over the course of a 1-hour interview, because they must give you problems
that you can be reasonably expected to answer in only 20 to 30 minutes. You can write a rela-
tively 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 imple-
ment a more complex data structure such as a hash table.
Also, little variation exists in linked list implementations, which means that an interviewer can
simply say “linked list” and not waste time discussing and clarifying implementation details.
Perhaps the strongest reason is that linked lists are useful to determine whether a candidate
understands how pointers and references work, particularly in C and C++. If you’re not a C
or C++ programmer, you may find the linked list problems in this chapter challenging. Still,
linked lists are so basic that you need to be familiar with them before moving to more compli-
cated data structures found in the chapters that follow.


NOTE In real-world development, you don’t usually write your own linked lists;
you use the implementation in your language’s standard library. In a program-
ming interview, you’re expected to be able to create your own implementation to
demonstrate that you fully understand linked lists.

,32 ❘ CHAPTER 4 Linked Lists




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.

head
pointer 12 3 –8 6



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 it has no data, it’s not a particularly useful list element. A more useful struct has at least
one data member in addition to the pointer:
// A more useful singly linked list element
typedef struct IntElement {
struct IntElement *next;
int data;
} IntElement;

The next pointer can be anywhere in the struct, but placing it at the beginning makes it easier to
write generic list-handling routines that work no matter what data an element holds by casting the
pointer to be of the generic list element type.
In C++ you could define a class for the list element:
// A singly linked list in C++
class IntElement {
public:
IntElement( int value ): next( NULL ), data( value ) {}

, Kinds of Linked List ❘ 33



~tElement() {}

IntElement *getNext() const { return next; }
int value() const { return data; }
void setNext( IntElement *elem ) { next = elem; }
void setValue( int value ) { data = value; }

private:
IntElement *next;
int data;
};

However, it usually makes more sense to define a template for the list element:
// A templated C++ singly linked list
template <class T>
class ListElement {
public:
ListElement( const T &value ): next( NULL ), data( value ) {}
~ListElement() {}

ListElement *getNext() const { return next; }
const T& value() const { return data; }
void setNext( ListElement *elem ) { next = elem; }
void setValue( const T &value ) { data = value; }

private:
ListElement *next;
T data;
};



NOTE When defining classes in C++, particularly in template form, it’s always
best to explicitly add copy constructors and assignment operators so you don’t
depend on the compiler-generated versions. In an interview, however, you’ll
generally skip these additional details as we’ve done here, but it doesn’t hurt to
mention them in passing to the interviewer.

A Java implementation using generics is similar, but of course uses references instead of pointers:
// A templated Java singly linked list
public class ListElement<T> {
public ListElement( T value ) { data = value; }

public ListElement<T> next() { return next; }
public T value() { return data; }
public void setNext( ListElement<T> elem ) { next = elem; }
public void setValue( T value ) { data = value; }

private ListElement<T> next;
private T data;
}