Doubly Linked List
- A linked list is a collection of objects stored in a list form.
- A linked list is a sequence of items (objects) where every item is linked to the next.
- Also, A linked list is a non-primitive type of data structure in which each element dynamically allocated and in which elements point to each other to define a linear relationship.
- Elements of the linked list called nodes where each node contains two things, data, and a pointer to next node.
- Moreover, Linked list require more memory compared to the array because along with value it stores the pointer to next node.
- Linked lists are among the simplest and most common data structures. They can use to implement other data structures like stacks, queues, and symbolic expressions, etc…
// C Structure to represent a node struct node
int info struct node *link
Operations on linked list
- Insert at first position
- Moreover, Insert at last position
- Insert into ordered list
- Traverse list (Print list)
- Copy linked list
Types of linked list
Singly Linked List
- It is the basic type of linked list.
- Each node contains data and pointer to next node.
- Last node’s pointer is null.
- Limitation of the singly linked list is we can traverse only in one direction, forward direction.
Circular Linked List
- The circular linked list is a singly linked list where the last node points to the first node in the list.
- It does not contain null pointers like the singly linked list.
- We can traverse only in one direction that is the forward direction.
- It has the biggest advantage of time-saving when we want to go from the last node to the first node, it directly points to the first node.
- A good example of an application where the circular linked list should be used is a timesharing problem solved by the operating system.
Doubly Linked list
- Each node of the doubly linked list contains data and two pointers to point previous (LPTR) and next (RPTR) node.
- The main advantage of the doubly linked list is we can traverse in any direction, forward or reverse.
- Another advantage of the doubly linked list is we can delete a node with little trouble since we have pointers to the previous and next nodes. A node on a singly linked list cannot remove unless we have the pointer to its predecessor.
- A drawback of the doubly linked list it requires more memory compared to the singly linked list because we need an extra pointer to point the previous node.
- So, L and R in image denote left most and right most nodes in the list.
- Left link of L node and right link of R node is NULL, indicating the end of the list for each direction.