Every data structure is important; linked lists are one of the fundamental building blocks of more advanced structures. Let’s get into the basics.
The linked list is a concept in Computer Science, where a group of nodes is linked together forming a chain. This chain is created by “linking” a node to another node. Now, a “link” is simply a reference to another node; it’s not some wild new concept. The main idea is an object referencing another object. That’s the concept, but as programmers, we have to be able to effectively represent that in the computer. So, let’s construct that representation for linked lists and doubly linked lists.
A representation is simply recreating a concept inside a computer. To do that effectively, we need to write some code that captures the actions and structure of a linked list. In my opinion, these are very straightforward. These include:
- Linked List: A class for containing the important linked list information and methods (how to traverse the list)
- Node: An element on the list that contains data
- setNext(): Links a node to the next node
- setPrev(): Links a node to the previous node
- getNext(): gets the next linked node
- getPrev(): gets the previously linked node
- getData(): gets the data contained within a node
As you can see, we create the basic linked list and doubly linked list classes. Each one has minor differences, but the most important thing to pay attention to is the addNode method which adds a node to the tail end of the list and removeNode which removes the node at the tail end of the list. To make it easier to add nodes multiple times, we simply return the newly created class and use chaining. The process of adding a node is what we need to focus on. First, we create a node, then we set the next reference of the tail to be the new node; this allows the tail to “link” to the new node. Afterward, the new node is the tail, so we simply say `this._tail = node;`. Changing the tail to reference the new node, instead of the old tail. The same rules are applied to the doubly linked list. In this case, we’re only working with adding nodes at the tail end of a linked list, but you could be more flexible and add nodes after the head if you wrote a similar method. Anyway, let’s illustrate the linked list addNode method.
As you can see, first we created our new linked list in code; this is line 120. Afterward, we add nodes; this is how a node is added. The new node becomes the new tail. Once we have completed that, the old tail (the head in this case), uses setNext to link to the new node, forming a chain between them. For each subsequent node, this process is repeated. This is how nodes are added to the tail end of the linked list. The only difference between this and the doubly linked list is that we also set the new node to link back to the previous node so we can reference (link) previous nodes.
I hope this post helps you understand linked lists a bit better; take time to play with the code yourself and you’ll start to understand the concept a bit better. It can make sense on a whiteboard, but understanding how to code it is also important.