Top 10 algorithms for linked lists?

Top 10 algorithms for linked lists?



1. Insertion of a node in Linked List (On the basis of some constraints)
2. Delete a given node in Linked List (under given constraints)
3. Compare two strings represented as linked lists
4. Add Two Numbers Represented By Linked Lists
5. Merge A Linked List Into Another Linked List At Alternate Positions
6. Reverse A List In Groups Of Given Size
7. Union And Intersection Of 2 Linked Lists
8. Detect And Remove Loop In A Linked List
9. Merge Sort For Linked Lists
10. Select A Random Node from A Singly Linked List


1. Insertion of a node in Linked List (On the basis of some constraints)
If Linked list is empty then make the node as
head and return it.
2) If value of the node to be inserted is smaller
than value of head node, then insert the node
at start and make it head.
3) In a loop, find the appropriate node after
which the input node (let 9) is to be inserted.
To find the appropriate node start from head,
keep moving until you reach a node GN (10 in
the below diagram) who's value is greater than
the input node. The node just before GN is the
appropriate node (7).
4) Insert the node (9) after the appropriate node
(7) found in step 3.

2. Delete a given node in Linked List (under given constraints)
We explicitly handle the case when node to be deleted is first node, we copy the data of next node to head and delete the next node. The cases when deleted node is not the head node can be handled normally by finding the previous node and changing next of previous node. Following is C implementation.

3. Compare two strings represented as linked lists
# Traverse both lists. Stop when either end of linked
# list is reached or current characters don't watch
while(list1 and list2 and list1.c == list2.c):
list1 = list1.next
list2 = list2.next

# If both lists are not empty, compare mismatching
# characters
if(list1 and list2):
return 1 if list1.c > list2.c else -1

# If either of the two lists has reached end
if (list1 and not list2):
return 1

if (list2 and not list1):
return -1
return 0

4. Add Two Numbers Represented By Linked Lists
1) Calculate sizes of given two linked lists.
2) If sizes are same, then calculate sum using recursion. Hold all nodes in recursion call stack till the rightmost node, calculate sum of rightmost nodes and forward carry to left side.
3) If size is not same, then follow below steps:
....a) Calculate difference of sizes of two linked lists. Let the difference be diff
....b) Move diff nodes ahead in the bigger linked list. Now use step 2 to calculate sum of smaller list and right sub-list (of same size) of larger list. Also, store the carry of this sum.
....c) Calculate sum of the carry (calculated in previous step) with the remaining left sub-list of larger list. Nodes of this sum are added at the beginning of sum list obtained previous step.

5. Merge A Linked List Into Another Linked List At Alternate Positions
The idea is to run a loop while there are available positions in first loop and insert nodes of second list by changing pointers.

6. Reverse A List In Groups Of Given Size
Algorithm: reverse(head, k)
1) Reverse the first sub-list of size k. While reversing keep track of the next node and previous node. Let the pointer to the next node be next and pointer to the previous node be prev. See this post for reversing a linked list.
2) head->next = reverse(next, k) / Recursively call for rest of the list and link the two sub-lists /
3) return prev / prev becomes the new head of the list (see the diagrams of iterative method of this post) /

7. Union And Intersection Of 2 Linked Lists
Intersection (list1, list2)
Initialize result list as NULL. Traverse list1 and look for its each element in list2, if the element is present in list2, then add the element to result.

Union (list1, list2):
Initialize result list as NULL. Traverse list1 and add all of its elements to the result.
Traverse list2. If an element of list2 is already present in result then do not insert it to result, otherwise insert.

This method assumes that there are no duplicates in the given lists.

8. Detect And Remove Loop In A Linked List
We know that Floyd's Cycle detection algorithm terminates when fast and slow pointers meet at a common point. We also know that this common point is one of the loop nodes (2 or 3 or 4 or 5 in the above diagram). We store the address of this in a pointer variable say ptr2. Then we start from the head of the Linked List and check for nodes one by one if they are reachable from ptr2. When we find a node that is reachable, we know that this node is the starting node of the loop in Linked List and we can get pointer to the previous of this node.

9. Merge Sort For Linked Lists
MergeSort(headRef)
1) If head is NULL or there is only one element in the Linked List
then return.
2) Else divide the linked list into two halves.
FrontBackSplit(head, &a, &b); / a and b are two halves /
3) Sort the two halves a and b.
MergeSort(a);
MergeSort(b);
4) Merge the sorted a and b (using SortedMerge() discussed here)
and update the head pointer using headRef.
*headRef = SortedMerge(a, b);

10. Select A Random Node from A Singly Linked List

(1) Initialize result as first node
result = head->key
(2) Initialize n = 2
(3) Now one by one consider all nodes from 2nd node onward.
(3.a) Generate a random number from 0 to n-1.
Let the generated random number is j.
(3.b) If j is equal to 0 (we could choose other fixed number
between 0 to n-1), then replace result with current node.
(3.c) n = n+1
(3.d) current = current->next

Popular posts from this blog

After analyzing the model, your manager has informed that your regression model is suffering from multicollinearity. How would you check if he's true? Without losing any information, can you still build a better model?

After analyzing the model, your manager has informed that your regression model is suffering from multicollinearity. How would you check if he's true? Without losing any information, can you still build a better model? Answer: To check multicollinearity, we can create a correlation matrix to identify & remove variables having correlation above 75% (deciding a threshold is subjective). In addition, we can use calculate VIF (variance inflation factor) to check the presence of multicollinearity. VIF value <= 4 suggests no multicollinearity whereas a value of >= 10 implies serious multicollinearity. Also, we can use tolerance as an indicator of multicollinearity. But, removing correlated variables might lead to loss of information. In order to retain those variables, we can use penalized regression models like ridge or lasso regression. Also, we can add some random noise in correlated variable so that the variables become different from each other. But, adding noise m...
Read more

Is rotation necessary in PCA? If yes, Why? What will happen if you don't rotate the components?

Is rotation necessary in PCA? If yes, Why? What will happen if you don't rotate the components? Answer: Yes, rotation (orthogonal) is necessary because it maximizes the difference between variance captured by the component. This makes the components easier to interpret. Not to forget, that's the motive of doing PCA where, we aim to select fewer components (than features) which can explain the maximum variance in the data set. By doing rotation, the relative location of the components doesn't change, it only changes the actual coordinates of the points. If we don't rotate the components, the effect of PCA will diminish and we'll have to select more number of components to explain variance in the data set.
Read more

What does Latency mean?

What does Latency mean? Latency is a networking term to describe the total time it takes a data packet to travel from one node to another. In other contexts, when a data packet is transmitted and returned back to its source, the total time for the round trip is known as latency. Latency refers to time interval or delay when a system component is waiting for another system component to do something. This duration of time is called latency.
Read more