As the name suggests it is a list in which each element is linked to each other. It is analogues to a train in which all the compartments are connected to each other and you can go from one compartment to other. The difference is that in one type of linked list you can only move from engine to the last compartment and not the other way it is called Single Linked List. Which means there is only a single connection between each element.
In another type of linked list you can go from engine to the last compartment and the other way as well it is called Double Linked List, the name it self suggests that there are two links one forward and another backward.
To completely understand the implementation of a linked list you should have a working knowledge of pointers, I am assuming that you do have that knowledge.
Let us now take up a simple problem in Linked List. In general whenever someone says Lists they mean Linked Lists, when they say linked lists they mean single linked list. A double linked list will be mentioned specifically if they mean to.
Write a code to remove duplicates from an unsorted lists.
What are we doing in this piece of code ?
Let us see what the code does line by line. We first receive a pointer input to the function. We declare two pointers current and scanner. Current pointer is assigned the value of the root pointer and the scanner pointer is first assigned the value of current pointer and then traverses till the end of the linked list. If we find an element similar to the current pointer we remove the element from the linked list by pointing the next pointer to a node after the repeated one. Continuing the train analogy, I remember the face of single passenger in one compartment and traverse till the last compartment to see if I find anyone similar.
Circular Linked Lists
As the name says they are circular and this is how you visualize them
Circular Linked Lists
As the name says they are circular and this is how you visualize them
Fast Runner and Slow Runner
This technique is used to
i) determine if a linked list is a circular linked list or not.
This is very similar to detecting the beginning of a loop. If a linked list is circular fast runner will not reach NULL and will meet the slow runner. So if both the pointers meet each other it is circular else if the fast runner meets NULL it is not circular.
ii) to determine where a linked list loop begins.
Let us find the starting node of the loop in the above shown circular linked list. To demonstrate this concept I should first create a circular linked list in the code below I segregated the parts which create a circular linked list from the one which detects one.
You can change the number at line 73 to make a loop at a different node and see that you get the same number returned as the starting node of the loop.
iii) to determine the middle node of a linked list
Again as very similar approach to the one described above. If we move one pointer twice as fast as the other, by the time the fast one reaches the end of the linked list the slower one would be at the middle of the entire linked list.
Reverse a Linked List
Another very useful tool in linked list related programing is to reverse a given linked list i.e. convert the linked list like this
To a linked list like this
That is to change the head pointer from 1 to 5 and all the corresponding links.
The code below is to reverse a linked list
Let us also implement the same reversing using recursion. Give it a try......
If not here is the code
No comments:
Post a Comment