Linked lists, sometimes simply called lists, are a fundamental data structure in computer science. Languages such as Java and C# do an admirable job of abstracting away the details behind lists, but understanding them is absolutely crucial when building efficient programs.

The way in which linked lists are structured varies, but we will consider a doubly-linked list with external data. By that, we mean that each link in the list will refer to the previous link and the next link in the list, and that the data type that represents the list itself will not contain the data itself, but instead each link will contain a reference (pointer) to its corresponding data. In C++, a naive implementation might look like this:

struct LinkedList
{


LinkedList *prev;
LinkedList *next;
DataType *data;

};


The advantages of linked lists are varied, as are the pitfalls. For example, here’s a comparison of the time complexity of various operations performed on an array versus performed on a list:

* O(1) if resize operation is amortized, but this increases space complexity by a constant factor
** Assumes a priori knowledge of array size, otherwise a sigil value may be necessary and time complexity increases to O(n)

I’ve written more linked lists in my time than I care to remember, so I won’t bother to duplicate the code here, but it’s important to mention that there is a fair amount of tedium in getting all the pointer updates correct when adding and removing elements. It’s better, in my opinion, to write in a higher-level language, or at least use higher-level facilities written by other people who have sweated out the details.

Next time, we’ll take a look at stacks and queues, abstract data types that allow us to consider data elements in different orders. They’re the backbone of many parsing, searching, and sorting algorithms.