Linked list head Java

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, Ill 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, lets implement our own!

Lets 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 lets 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 Nodes next pointer should point to the new Node, and new Nodes 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 lets take a look at the code:

Accessing an element in Linked List

Now that weve added some elements to our Linked List, lets 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 doesnt 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:

Lets 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 Arrays 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, lets 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 were 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. Lets insert Node with data: -5 at index position 2.

We use the index to find the Node and call it nextToNewNode. We take nextToNewNodes previous Node and name it previousToNewNode.

We create a new Node with data 5 and call it newNode.

We set previousToNewNodes next pointer to newNode. We set newNodes previous pointer to previousToNewNode.

We set nextToNewNodes previous pointer to newNode.We set newNodes next pointer to nextToNewNode.

Now that weve 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 nodeToDeletes previous and call it nodeToDeletesPrevious. We take nodeToDeletes next Node and call it nodeToDeletesNext.

We set nodeToDeletesPreviouss next pointer to nodeToDeletesNext. We set nodeToDeletesNexts 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