Linked List
Linked List:
An ordered set of data elements, each containing a link to its successor (and sometimes its predecessor).
Types of Linked List:
1. Linear Linked List or One Way List or Singly Linked List
2. Doubly Linked List or Two-Way Linked List or Two-Way Chain
3. Circular Linked List
Note:
Doubly linked list can be used as doubly circular linked list.
Advantages:
- Linked lists are a dynamic data structure, allocating the needed memory while the program is running.
- Insertion and deletion node operations are easily implemented in a linked list.
- Linear data structures such as stacks and queues are easily executed with a linked list.
- They can reduce access time and may expand in real time without memory overhead.
Disadvantages:
- They have a tendency to waste memory due to pointers requiring extra storage space.
- Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
- Nodes are stored in contiguously , greatly increasing the time required to access individual elements within the list.
- Difficulties arise in linked lists when it comes to reverse traversing. Singly linked lists are extremely difficult to navigate backwards, and while doubly linked lists are somewhat easier to read, memory is wasted in allocating space for a back pointer.
Applications of Linked List in real world:
A linked list would be a reasonably good choice for implementing any of the following:
1. Applications that have an MRU list (a linked list of file names) .
2. The cache in your browser that allows you to hit the BACK button (a linked list of URLs).
3. Undo functionality in Photoshop or Word (a linked list of state).
4. A stack, hash table, and binary tree can be implemented using a doubly linked list.
5. A great way to represent a deck of cards in a game.