Implementation Concepts
To understand how to implement a linked list, we will want to look at the parts we will need to implement in order to create one.
Nodes
The basic unit of storage for a linked list is a node. A node stores data and one or more pointers to other nodes. At its most basic, a linked list node consists of data plus a pointer to the next node in the linked list. It is possible for a node to also store a pointer to the previous node in the linked list.
A linked lists where each node contains only a single pointer to the next node is called a singly linked list.
A linked list where each node contains two pointers one to the next node and one to the previous node is called a doubly linked list.
The idea of storing data in a node is not unique to linked lists. Other data structures such as trees also store data in nodes
Iterators
Iterators allows you to traverse a container class without actually knowing what the underlying container actually is or how that container may be implemented. You can observe their usage in container classes within the C++ Standard Library such as <vector> and <list>. You can also see it in Python list and dictionaries. A linked list is a container class. Thus, our implementation of a linked list should also include the concept of iterators. Iterators also allow us to traverse the list in various ways (backwards and forwards for example). The idea is simply to separate the thing that allows us to go through a list with the underlying data structure
Iterators should support the following functionalities at minimum. Note that these are just general ideas. They are not language specific:
- first - set iterator to refer to the first item in a container
- next - sets iterator to the next item in the container
- isDone - returns true if iterator is not refering to anything
- currentItem - returns the current piece of data
When thinking about iterators, the important concept is that an iterator lets us go through a container one data item at a time. It provides a uniform method to go through the container and access the data. While you may view it as being similar to a node pointer, it is not the same. To the user of the list, there should be no such thing as a node. They only have iterators. This is really important to remember.
An iterator is NOT a node, a linked list or a pointer to these. An iterator essentially hides the fact that there are even nodes within our linked list. It provides access to a set of data stored within a container in a uniform manner. It limits the type of access allowed to only some operations. We use iterators so that there is a familiarity to how we would access our custom container classes. That is we make them work in a similar manner to those containers that are part of the language.
Linked List
And finally we have the concept of the linked list itself. This particular object holds very little data within itself. The only data that is absolutely required is the location of a single node in the list, the node that allows you to follow links to every other node. Usually this is the first node in the list but it does not have to be the first node. This largely depends on the type of list we are coding and what we are trying to achieve.