Linked List
Linked list is a dynamic data structure that contains a “link” to the structure containing the next item. It is a collection of structures ordered not by their physical placement in memory (like array) but by logical links that are stored as part of the data in the structure itself.
Self-Referential Structure
A structure which is referencing to another structure of same type is called self referential structure.
Malloc
It allocates memory at run time and returns pointer to first byte of memory.
Advantages of Linked Lists
- Dynamic structure (Mem. Allocated at run-time).
- We can have more than one datatype.
- Re-arrange of linked list is easy (Insertion-Deletion).
- It doesn’t waste memory.
Disadvantages of Linked Lists
- In linked list, if we want to access any node it is difficult.
- It is occupying more memory.
Types of Linked List
- Singly or Chain Linked List.
- Doubly or Two Way Linked List.
- Circular Linked List.
- Circular Doubly Linked List.
Singly or Chain Linked List
The way to represent a linear list is to expand each node to contain a link or pointer to the next node. This representation is called a one-way chain or singly linked list.
Circular Linked List
A linked list in which the pointer of the last node points to the first node of the list is called circular linked list.
Doubly or Two-Way Linked List
A linked list which can be traversed both in backward as well as forward direction is called doubly linked list. It uses double set of pointers.
Circular Doubly Linked List
It employs both the forward pointer and backward pointer in circular form.