The ‘Linked List’ Data Structure
Feb 192018When designing a data structure, there are always choices to make. In the previous post we described the array-list data structure implementing the list data type; in that post, we made the choice to store the list values in an “underlying array” so the list values would all be together in memory. In this post we’ll show that this really was a choice, by developing a list data structure which stores the list values in separate objects, rather than a single array object.
The data structure we’ll develop in this post, called a linked list,(1) looks like this:
This means each list value is stored in a separate object, we keep track of which object is the first in the list, and then each object has a reference to the next one in the sequence.
Each node might be anywhere in memory — the addresses don’t have to be in the same order as the list, because the references are enough to define the list’s order.(2)
The linked list itself is represented by the object with field named first, and the other objects are normally called the “linked list nodes”, and their fields might be called value and next.
Once we know how the data is stored, we also need to implement the list operations.
The first one of these is to ‘create’ an empty list; an empty list has no first item, so we simply have to create a new linked list object with first equal to null.
The next operations are ‘get’ and ‘set’.
The hard part is finding which node has the value we want to ‘get’ or ‘set’; to find the value at index i, we need to count i nodes forwards in the linked list, by following references from the first item.(3)
A full implementation of the linked list data structure would also need to support the remaining list operations — ’length’, ‘append’, ‘insert’, ‘remove’ and ‘clear’.
To get the ‘length’ of a linked list, we could count forwards from first until we reach a null pointer; alternatively, we could give the linked list object a length field, like we did for the array-list.
On the other hand, rather than learning how to implement every operation on a linked list, it’s more important to be able to think about them, and draw diagrams. The key things to think about are the same as when thinking about box-and-pointer diagrams more generally:
- What new nodes should be created?
- If the list should get longer (‘append’ or ‘insert’) then we need to create a new node to hold the new value.
- What references should be changed?
- If the list should get longer, then the new node should be referenced by its previous node, and should reference its next node.
- If the list should get shorter, then whichever node is being removed should no longer be referenced by its previous node.
Footnotes
- As before, the convention for naming data structures is that the second word (list) says what ADT it implements, and the first word (linked) says how it’s implemented.
- Recall that in a box-and-pointer diagram, the positions of the boxes don’t matter.
- Recall that we can only access an object if we have a reference to it.
Comments