Linked List
A linear data structure forming a sequential chain
Introduction
A Linked List is a linear data structure where elements are arranged sequentially in a chain-like form. Each node contains two parts: data (the value of the element) and a pointer (address of the next node in the sequence). Unlike arrays, linked lists allow dynamic memory allocation, meaning their size can grow or shrink as needed. They are particularly useful for scenarios requiring frequent insertions and deletions, as these operations can be performed efficiently without the need to shift elements, unlike in arrays.
Why Use Linked Lists?
Dynamic Size
Arrays Problem: Fixed size; resizing requires copying all elements, which is slow.
Linked List Solution: Grows or shrinks dynamically without copying.
Fast Insertions/Deletions
Arrays Problem: Adding or removing elements can require shifting, which is slow (O(n)).
Linked List Solution: Add or remove nodes quickly by updating pointers (O(1) with known position).
Non-Contiguous Memory
Arrays Problem: Needs a large, continuous block of memory.
Linked List Solution: Nodes can be stored anywhere, connected via pointers.
Flexible for Complex Data
Linked lists are great for dynamic structures like stacks, queues, and graphs (e.g., adjacency lists).
Structure of Node
Data Field:
This stores the actual value or information for that particular node.
Pointer Field:
This stores the address (or reference) of the next node in the list, enabling the nodes to be linked together sequentially.
-In the case of Singly Linked Lists, the pointer refers to the next node.
-For Doubly Linked Lists, each node contains two pointers: one pointing to the next node and another to the previous node.
Visualization of Linked List
Coding Implementation
// Definition of Node
#include<iostream>
using namespace std;
class Node{
public:
int data;
Node* next;
// constructor for initialization
Node(int data){
this->data=data;
this->next=NULL;
}
};
int main(){
Node *head=new Node(10); // Create head node with data = 10
Node *second=new Node(20);// Create second node with data = 20
head->next=second;// Linking head node with second node;
cout<<head->data<<" "<<head->next->data; //10->20
}