Introduction to link list
Link list
Array
linked lists are stored in a non-contiguous memory location. To add a new element, we just have to create a node somewhere in the memory and get it pointed by the previous element. And deleting an element is just as easy as that. We just have to skip pointing to that particular node. Lengthening a linked list is not a big deal.
Arrays demand a contiguous memory location. Lengthening an array is not possible. We would have to copy the whole array to some bigger memory location to lengthen its size. Similarity inserting or deleting an element causes the elements to shift right and left.
Structure of a Linked List:
Every element in a linked list is called a node and consists of two parts, the data part, and the pointer part. The data part stores the value, while the pointer part stores the pointer pointing to the address of the next node.
Both of these structures (arrays and linked lists) are linear data structures.
Linked lists VS Arrays:
Why linked lists?
Memory and the capacity of an array remain fixed, while in linked lists, we can keep adding and removing elements without any capacity constraint.
For accessing elements arrays are better and for insertion and deletion linked lists are better.
Drawbacks of linked lists
- Extra memory space for pointers is required (for every node, extra space for a pointer is needed)
- Random access is not allowed as elements are stored in contiguous memory locations.
Implementations
struct Node
{
int data;
struct Node *next; // Self referencing structure
};