Union and Intersection of two unsorted Linked Lists
Posted on July 30, 2014
(Last modified on August 7, 2020)
| 4 minutes
| Kinshuk Chandra
Problem Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. Order of elments in output lists doesn’t matter.
Example Input: List1: 10->15->4->20 lsit2: 8->4->2->10 Output: Intersection List: 4->10 Union List: 2->8->20->4->15->10 Solution Method 1 - Simple
Following are simple algorithms to get union and intersection lists respectively.
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.
[Read More]Create linked lists of all the nodes at each depth for a BST
Posted on February 10, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Problem
Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (i.e., if you have a tree with depth D, you’ll have D linked lists)
Example
So a binary tree such as :
(1) / \\ / \\ (2) (3) / \\ / \\ (4) (5) (6) (7) Will return linked lists:
(1) => NULL (2) => (3) => NULL (4) => (5) => (6) => (7) => NULL Solution
[Read More]Insertion sort on linked list
Posted on January 19, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
If you want a simpler algorithm that needs only O(1) space, you can also consider using insertion sort to sort the linked lists. While insertion sort is easier to implement, it runs in O(n2) time in the worst case (though it also has O(n) best-case behavior), so it’s probably not a good choice unless you specifically want to avoid merge sort.
The idea behind the insertion sort algorithm is as follows:
[Read More]Selection sort on linked list
Posted on January 19, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Another O(n2) sorting algorithm that can be adapted for linked lists is selection sort. This can be implemented very easily (assuming you have a doubly-linked list) by using this algorithm:
Initialize an empty list holding the result. While the input list is not empty: Scan across the linked list looking for the smallest remaining element. Remove that element from the linked list. Append that element to the result list.
[Read More]Sort a linked list using bubble sort
Posted on January 19, 2014
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
Merge sort looks like a best choice for sorting the linked list.At a first appearance, merge sort may be a good selection since the middle element is required to subdivide the given list into 2 halves, but we can easily solve this problem by moving the nodes alternatively to 2 lists.
We have discussed the sorting options for linked list here. Here we will discuss about bubble sort
Pseudocode for bubble sort:
[Read More]Sort a linked list using quick sort
Posted on January 19, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Merge sort looks like a best choice for sorting the linked list.At a first appearance, merge sort may be a good selection since the middle element is required to subdivide the given list into 2 halves, but we can easily solve this problem by moving the nodes alternatively to 2 lists.
We have discussed the sorting options for linked list here. Here we will discuss about quick sort.
Another O(n log n) sort that you can implement on linked lists is a modification of quicksort.
[Read More]Sort a linked list using merge sort
Posted on January 19, 2014
(Last modified on August 7, 2020)
| 3 minutes
| Kinshuk Chandra
Merge sort looks like a best choice for sorting the linked list.At a first appearance, merge sort may be a good selection since the middle element is required to subdivide the given list into 2 halves, but we can easily solve this problem by moving the nodes alternatively to 2 lists.
We have discussed the sorting options for linked list here.
Merge sort is very special (in fact many standard sort libraries like in java internally uses a combination of merge sort and insertion sort) because it has the wonderful property of being a stable sort.
[Read More]What's the fastest algorithm for sorting a linked list?
Posted on January 19, 2014
(Last modified on August 7, 2020)
| 2 minutes
| Kinshuk Chandra
Merge sort is the best choice. At a first appearance, merge sort may be a good selection since the middle element is required to subdivide the given list into 2 halves, but we can easily solve this problem by moving the nodes alternatively to 2 lists.
It is reasonable to expect that you cannot do any better than O(N log N) in running time, whenever we use comparison based sorts.
[Read More]Operation time complexity for a LINKED LIST
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
The time complexity of handling the operations in a data structure like a LINKED LIST are as follows:
i. Most of the operations are O(n) [i.e. omega times n]
ii. Remove/Insert operations that handles element between elements require O(1) [i.e. omega times one] this is due to references/pointers on both the ends of the list, hence the elements don’t require to be shifted. However, due to the references/pointers this data structure requires additional memory!
[Read More]What is a non-linear datastructure?
Posted on July 30, 2013
(Last modified on August 7, 2020)
| 1 minutes
| Kinshuk Chandra
A non-linear datastrucutre is a datastructure in which the data items in the memory are not allocated contiguously i.e. the data items are dispersed in the memory. The first data item will have a link to the second data item and second data item will have a link to the third data item and so on.
Pros
Uses memory efficiently that the free contiguous memory in not an requirement for allocating data items The length of the data items is not necessary to be known prior to allocation Cons
[Read More]