tech-notes-and-questions

Linked Lists

Definition

A linked list is a linear data structure that consists of a series of nodes connected by pointers (in C or C++) or references (in Java, Python, and JavaScript). Each node contains data and a pointer/reference to the next node in the list.

Uses

• Efficient insertion and deletion compared to arrays.
• Used to implement other data structures like stack, queue and deque.

Basic Operations

1. Insertion
2. Search an element
3. Find length
4. Reverse a linked list
5. Delete an element (given a key, given a position)
6. Get Nth node (from first, from last)

Problems

1. Print the middle of a given linked list
2. Write a function that counts the number of times a given int occurs in a Linked List
3. Check if a linked list is a Circular Linked List
4. Count nodes in a Circular linked list
5. Convert a singly linked list into a circular linked list
6. Exchange first and last nodes in Circular Linked List
7. Reverse a Doubly Linked List
8. Program to find the size of Doubly Linked List
9. An interesting method to print reverse of a linked list
10. Can we reverse a linked list in less than O(n)?
11. Circular Linked List Traversal
12. Delete a node in a Doubly Linked List
13. Detect loop in a linked list
14. Find length of loop in a linked list
15. Remove duplicates from a sorted linked list
16. Intersection of two Sorted Linked Lists
17. QuickSort on Singly Linked List
18. Split a Circular Linked List into two halves
19. Deletion from a Circular Linked List
20. Merge Sort for Doubly Linked List
21. Find pairs with given sum in a doubly linked list
22. Insert value in sorted way in a sorted doubly linked list
23. Remove duplicates from an unsorted doubly linked list
24. Rotate a Doubly linked list by N nodes
25. Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?
26. Modify contents of Linked List
27. Intersection point of two Linked Lists.

28. Circular Queue

    Set 2 (Circular Linked List Implementation)

29. Josephus Circle using a circular linked list
30. The Great Tree-List Recursion Problem.
31. Copy a linked list with next and orbit pointer

32. Convert a given Binary Tree to Doubly Linked List

    Set

33. Priority Queue using a doubly linked list
34. Reverse a doubly linked list in groups of given sizes
35. Reverse a stack without using extra space in O(n)
36. Linked List representation of Disjoint Set Data Structures
37. Sublist Search (Search a linked list in another list)
38. Construct a linked list from 2D matrix