What are Linked Lists?

This section provides you with a high level introduction to the linked list data structure.

If you have ever used a list from the C++ STL, that is implemented as a linked list... so while you may not have actually implemented it, you might have used it. However there are definitely some important issues to consider when using a linked list. This section will provide a brief introduction to linked list and its concepts. Note that Python list is not linked list based.

Introduction

A linked list is a data structure that stores a collection of data objects in a sequential manner. Each data object in list is stored in a node. Each node consists of a single data object along with at least one pointer to another node, typically the next node within the list. The linked list object itself must contain a pointer to a node within the list that will allow access to every other node by following the pointers in the node. Usually this is a pointer to the first node in the linked list.

If you wanted to store an array of 5 numbers in an array this is what the array would look like:

A simple linked list that stores the same 5 numbers in the same sequence would look like this

The above is a singly linked list. It is called this because there is a single pointer out of each node to another node.

caution

Note that while the above diagram only has a single pointer out of the linked list object itself, it is not part of the definition of a singly linked list. The single link only refers to the link from one node to another, the fact there is only one link to the set of nodes.

Due to the way they are implemented, it is very fast to reach the first node in the linked list. However, to get to any other node, we must iterate through the list from node to node. Thus to get to the 5th node, we have to start at the first and follow the next pointers until we reach the 5th one.

This is different from an array. When you have an array, if you wanted to access the 5th item in the array, you would simply access array[4] which can be done in constant time because under that array is a mathematical calculation that is not affected by the array size.

Typical Operations

To look at how to implement a linked list, the operations a linked list can do should be considered. A linked list can typically support some subset of the following operations.

• push_front - add an item to the front of the linked list
• push_back - add an item to the back of the linked list
• pop_front - remove the frontmost item from the linked list
• pop_back - remove the backmost item from the linked list
• insert - given a point within the list insert an item just before that point
• erase - remove a node at a specific point within the list
• erase(a,b) - erases all nodes between a and b
• traversals - some operation that applies to every node in the list

Enhancements

To support the above operations, a linked list typically will store more information than the basic list. We will detail these in the implementation section