Linked List Data Structure

A linked list is a fundamental data structure in computer science. It mainly allows efficient insertion and deletion operations compared to arrays . Like arrays, it is also used to implement other data structures like stack, queue and deque.

What is a Linked List?

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. Unlike arrays, linked lists allow for efficient insertion or removal of elements from any position in the list, as the nodes are not stored contiguously in memory.

Linked Lists vs Arrays

Here’s the comparison of Linked List vs Arrays

Linked List:

• Data Structure: Non-contiguous
• Memory Allocation: Typically allocated one by one to individual elements
• Insertion/Deletion: Efficient
• Access: Sequential

Array:

• Data Structure: Contiguous
• Memory Allocation: Typically allocated to the whole array
• Insertion/Deletion: Inefficient
• Access: Random

Types of Linked List

1. Singly Linked List
2. Doubly Linked List
3. Circular Linked List
4. Circular Doubly Linked List
5. Header Linked List

Operations of Linked Lists:

• Linked List Insertion
• Search an element in a Linked List (Iterative and Recursive)
• Find Length of a Linked List (Iterative and Recursive)
• Reverse a linked list
• Linked List Deletion (Deleting a given key)
• Linked List Deletion (Deleting a key at given position)
• Write a function to delete a Linked List
• Write a function to get Nth node in a Linked List
• Nth node from the end of a Linked List

Linked List Applications

• Implementing stacks and queues using linked lists.
• Using linked lists to handle collisions in hash tables.
• Representing graphs using linked lists.
• Allocating and deallocating memory dynamically.

Basics of Linked List:

• What is Linked List
• Introduction to Linked List – Data Structure and Algorithm Tutorials
• Applications, Advantages and Disadvantages of Linked List

Easy Problems on Linked List:

• Print the middle of a given linked list
• Write a function that counts the number of times a given int occurs in a Linked List
• Check if a linked list is Circular Linked List
• Count nodes in Circular linked list
• Convert singly linked list into circular linked list
• Exchange first and last nodes in Circular Linked List
• Reverse a Doubly Linked List
• Program to find size of Doubly Linked List
• An interesting method to print reverse of a linked list
• Can we reverse a linked list in less than O(n)?
• Circular Linked List Traversal
• Delete a node in a Doubly Linked List

Medium Problems on Linked List:

• Detect loop in a linked list
• Find length of loop in linked list
• Remove duplicates from a sorted linked list
• Intersection of two Sorted Linked Lists
• QuickSort on Singly Linked List
• Split a Circular Linked List into two halves
• Deletion from a Circular Linked List
• Merge Sort for Doubly Linked List
• Find pairs with given sum in doubly linked list
• Insert value in sorted way in a sorted doubly linked list
• Remove duplicates from an unsorted doubly linked list
• Rotate Doubly linked list by N nodes
• Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?
• Modify contents of Linked List

Hard Problems on Linked List:

• Intersection point of two Linked Lists.
• Circular Queue | Set 2 (Circular Linked List Implementation)
• Josephus Circle using circular linked list
• The Great Tree-List Recursion Problem.
• Copy a linked list with next and arbit pointer
• Convert a given Binary Tree to Doubly Linked List | Set
• Priority Queue using doubly linked list
• Reverse a doubly linked list in groups of given size
• Reverse a stack without using extra space in O(n)
• Linked List representation of Disjoint Set Data Structures
• Sublist Search (Search a linked list in another list)
• Construct a linked list from 2D matrix

Quick Links :

• ‘Practice Problems’ on Linked List
• ‘Videos’ on Linked List
• ‘Quizzes’ on Linked List

Recommended: