March 30, 2008: Linked Lists
Introduction
A list is an object that maintains a dynamic sequence of data by keeping track of where the first and last elements in the sequence are. Because the point is to make the sequence grow as it needs to,
we must have a method of adding elements without checking for some hard limit. For this reason we use what is commonly referred to as a node.
Addition of elements is done to the end of the list (linking a new node after the current tail node) and traversal for searching, deleting, and inserting is always done from the beginning (head node). Two implement a list, you generally define a node class that will hold a data item and point to another node, and the list class which has pointers for the head and tail nodes.
This is an example showing how to build and use linked lists of an Mp3 type.
NOTE: Throughout these pages, whenever I refer to head, tail or any identifier that is a list node pointer (all of them are), its value indicates the node that it points to. So when I say things like … start a search at the head… , I mean start searching at the node pointed to by head.
Creating and Adding to a Linked List
When your List object is first created, its pointers should be set to NULL as it is representing a list with no elements. For every element added, a node needs to be created to hold it and
maintain the connection between it and other nodes (thus, a sequence is built).
Adding the first element is a special case as head and tail aren’t yet pointing to a node. As with any other add, a new node is created (in this case pointed to temporarily by the pointer t). if your node class is implemented correctly, the constructor will take care of constructing the data instance and setting its pointer to it (this instance can also be held directly by the node to avoid using new and delete within the node).
After the object is created, the list should handle the special case of adding the first node to the class. This involves setting both head and tail to point to the new node.
Once the first node is added, it is no longer a special case to add a new one as a adds always are done to the tail. For any of the following adds, a new node is created again:
The list now looks at the node pointed to by tail and sets its next pointer to point to the new node.
The final step is to set tail to point to the new node (the new tail).
Addition of a third element follows the same rules: a node is created,
tail’s next is set to point to the new node, which then is set to be pointed to by tail as well.
