Linked List Data Structure
Linked List is the data structure that consists of Nodes.
Node is an Object that wraps around a single piece of data. Linked List contains a collection of nodes. List executes its algorithms on Nodes, not on the data directly.
To make a collection of Node objects into a List, they need to be linked together. Nodes in a Linked List are linked together using pointers. List where a Node points only to the next Node in the List is called Singly Linked List. List where Nodes point to both the next and the previous Node in the List is called Doubly Linked List.
In this post, I’ll refer to the Doubly Linked List.
The first Node in the List is called head and its pointer for the previous Node points to null. The last Node in the List is called tail and its pointer to the next Node points to null.
This is what a Doubly Linked List looks like:
There is already a Linked List implementation in Java — java.util.LinkedList. But in order to fully understand the data structure, let’s implement our own!
Let’s start with a Node:
And now add a Linked List class that will have pointers to the first Node in the List — head, and the last Node in the List — tail.
Now let’s implement some common methods for our Linked List.
Adding an Element into a Linked List
First, we start with an empty List:
Now we want to add the first Node with data value 7:
We create a new Node with data 7. The new Node should be both the head and the tail of our List. Its previous and next pointers should both point to null:
If we want to add another Node to our List, with data value 13:
Current tail Node’s next pointer should point to the new Node, and new Node’s previous pointer should point to the current tail Node:
Because our new Node is now the last one in the List, it should become the new tail:
Now let’s take a look at the code:
Accessing an element in Linked List
Now that we’ve added some elements to our Linked List, let’s see how can we access them.
Same as with Arrays — we use an index when accessing an element in Linked List. But this time, we have to count the Nodes. Let us access a Node at index position 2.
We start at the head Node and count, from 0 to the index value 2. We have the current pointer that points to the Node we are currently located at. Initially, current points to head Node and the counter is set to 0.
We check to see if counter matches the index value 2. If it does, we return the current Node. If it doesn’t match, we move current pointer to the next node and increment counter:
When our counter matches the index value, we stop our counting and return current Node:
Let’s take a look at the code:
As we can see, we have to iterate (in the worst case) the whole List in order to get the Node we need. This means that accessing an element has O(n) complexity. Which is much worse than Array’s O(1). This time complexity for accessing elements is one of the cons of Linked List.
Finding an element in Linked List
Finding an element in Linked List is a similar operation to accessing an element. This time we have to find the Node that has a specific data value. Again, we have to read every element in the List and check its data value. For example, let’s find an element 13 in our List. We start the search from the head:
We check every element if it holds data value 13. When we find one that does we return it:
Here is the code that will find the node with specified data value:
In the worst case, we have to check every Node if it has the data value we specified, so this algorithm has O(n) complexity.
Inserting an Element in a List
When we’re inserting a new Node, we should provide an index in the List where we want to insert the new Node and the Node object we want to insert. Let’s insert Node with data: -5 at index position 2.
We use the index to find the Node and call it nextToNewNode. We take nextToNewNode’s previous Node and name it previousToNewNode.
We create a new Node with data 5 and call it newNode.
We set previousToNewNode’s next pointer to newNode. We set newNode’s previous pointer to previousToNewNode.
We set nextToNewNode’s previous pointer to newNode.We set newNode’s next pointer to nextToNewNode.
Now that we’ve set all the pointers correctly we finished inserting the new Node in the List. Here is the code example:
insert method has O(1) time complexity. But to call it, we first have to find the current Node somehow.
Deleting an Element in a List
Deleting an element in a Linked List is also a matter of setting the right pointers correctly. Lets now delete the Node with data value -5 we recently added. Its located at index position 2.
We first have to get the Node at index position 2, that will be our nodeToDelete.
We take nodeToDelete’s previous and call it nodeToDeletesPrevious. We take nodeToDelete’s next Node and call it nodeToDeletesNext.
We set nodeToDeletesPrevious’s next pointer to nodeToDeletesNext. We set nodeToDeletesNext’s previous pointer to nodeToDeletesPrevious.
And that would be it. Since no object points to nodeToDelete, the garbage collector will remove the nodeToDelete.
Here is the example code:
Finding the nodeToDelete based on the index will take O(n) but removing it afterward will take O(1) time complexity.
Conclusion
Linked List is a data structure with O(1) time complexity for insert and delete methods and O(n) time complexity for finding an element.
Example code can be found here:
Good day and happy coding everybody 🍹
