Data Structures — Linked List
A Linked List is a data structure that looks like a train with carriages connected to each other. It has a Head or the motor unit that connects to the first carriage. Each carriage carries a payload, and also maintains a connection to the next carriage in the train. The last carriage has no link to anything. Access the train from the head to get to the first carriage and move along the connection between the carriages until the last carriage.
Let’s create the carriages, called a node in our code first. It would have the payload that it carries, and a link or pointer that points to the next node.
A linked list is best represented in a class which gives it a structure where all its methods are represented in the class.
As you can see it has a pointer called head that points to the first node. The pointer is NULL at first or when the list is empty.
So, to determine if the list is empty, we can simply use the head pointer to check if it points to something or is it NULL. Let's see the implementations of the IsEmpty function below.
Inserting a new node into the list is always in the front. If a list is empty, we just need the head points to the newNode, and the newNode’s next pointer to NULL. If the list already contains any nodes, make head points to the newNode and newNode’s next pointer to the existing first node.
In this scenario, the first part to connect head to newNode is similar. The second part is also similar, because the value of head is NULL when the list is empty, and point to the first node if the list is not empty.
So we can simply point newNode’s next pointer to head. Then we point head to the newNode itself.
These two steps must be in the sequence above so we don’t override the head and losing our connection to the existing first node.
Deleting a node from the list requires similar manipulation of the head pointer. The head pointer needs to be pointing to the second node then we have to delete the first node. Since only the first node has the pointer to the second node, we would need a temporary pointer to the first node. Then move head to the second node, which is the first node’s next pointer. Finally, we can delete the first node.
Apart from inserting and removing items from a data structure, we would also need to access an item at a specific position or to find a specific payload. We have to do a traversal to achieve this.
Let's look at the Display function below which does a traversal of the linked list. It prints out each of the payloads in the list one by one, starting from the head.
There are other functions we can implement with a linked list depending on our needs. For example, you may want to insert or remove a particular node in the list, not just the node at the head. To do this you have to do the same traversal routine, visiting each node from the head to find the particular node. A more detailed implementation of such functions are listed below:
The full implementation of the linked list can be found in this Github repo:
