Linked Lists and Its Properties
A linked list is a linear data structure as well as a dynamic data structure. A Linked list consists of nodes where each node contains a data field(to store some data values) and a reference to the next node in the list.
Properties of Linked List
- It can be visualized as a chain of nodes where each node contains the location of the next node. You can see this in the diagram given below:
- The structure of the node is
class Node{
int val // variable storing the data of each node
Node next // variable storing the address of the next blog
}
- The first node of the linked list is called the head of the linked list . Through head, we can perform different operations on the linked list. In every linked list question, we will be given the reference of the head node of the linked list.
- The last node of the linked list is pointing to NULL (None) which indicates that it is the last node.
- Unlike arrays, linked list elements are not stored at contiguous memory locations.
- Linked Lists addresses some of the limitations of arrays of having a fixed size because Linked Lists are dynamic in nature.
Advantages and Disadvantage of Linked list
PROS
- They are dynamic in nature which allocates the memory when required.
- Insertion and deletion operations can be easily implemented.
CONS
- The memory is wasted as pointers require extra memory for storage.
- No element can be accessed randomly, it has to access each node sequentially i.e. proper traversal must be done.
- Reverse Traversing is difficult in the linked list(though we can achieve this with the help of Doubly Linked List).
Applications of Linked Lists
- Linked lists are used to implement stacks, queues, graphs, etc.
- Any application which has to deal with an unknown number of objects will need to use a linked list.
Critical Concepts to explore in Linked List
Suggested Problems to solve in Linked List
- Reverse linked list
- Middle of the Linked List
- Odd even linked List
- Remove Duplicates from Sorted List
- Merge Sort on Linked List
- Check if a singly linked list is palindrome
- Detect and Remove Loop in a Linked List
- Sort a linked list using insertion sort
- Remove Nth Node from List End
Happy coding! Enjoy Algorithms.