.png)
DSA SERIES — LINKED LISTS IN C
1. Introduction to Linked Lists
A Linked List is a dynamic linear data structure where elements (called nodes) are stored in non-contiguous memory.
Each node contains:
-
Data
-
Pointer to next node
[DATA | NEXT] → [DATA | NEXT] → [DATA | NEXT] → NULL
Linked lists overcome array limitations:
-
No fixed size
-
No expensive shifting while inserting at beginning/middle
-
Efficient deletions
2. Node Structure in C
struct Node {
int data;
struct Node *next;
};
Detailed Explanation of Members in the Node Structure (C Edition)
The linked list node in C is defined as:
struct Node {
int data;
struct Node *next;
};
This structure contains two members, and each plays a specific role in the linked list architecture.
1. int data — Data Member
Meaning
This field stores the actual value of the node.
It represents the information that you want to keep in the linked list.
Key Characteristics
It can be any data type: int, float, char, or even another structure.
For DSA implementation, using int is the most common as it simplifies logic.
Every node holds one unit of data, but the structure can be modified to store:
Multiple values
Strings
Complex objects
Purpose
Acts as the payload or content of the node.
Example: In a student list, it can store roll number or marks.
2. struct Node *next — Pointer Member
Meaning
This member is a pointer of type struct Node*, which stores the address of the next node.
It creates the link that connects nodes together.
Key Characteristics
If next = NULL, it means the node is the last element in the list.
For the first node, next points to the second node.
This pointer allows dynamic chaining of nodes in non-contiguous memory.
Purpose
Enables traversal from one node to another.
Forms the linked structure:
[Node1] → [Node2] → [Node3] → NULL
Without the pointer, nodes would be isolated and not form a list.
Why this pointer is important
Linked lists rely on pointers to create flexible, resizable structures.
The pointer allows:
Dynamic insertion
Dynamic deletion
Rearranging nodes without shifting memory
Unlike arrays, linked lists do not need contiguous memory; the pointer links scattered nodes.
Combined Purpose of Both Members
Together these two members allow the node to hold:
Data (value to be stored)
Link (connection to the next node)
Thus forming a chain-like structure.
+-----------+-------------+
| data | next | ---> address of next Node
+-----------+-------------+
Every node contains:
What to store
Where to go next
This is the heart of linked list design.
Then define a head pointer:
struct Node *head = NULL;
3. Memory Allocation
Nodes are created using dynamic memory:
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
Detailed explanation for Point 3 — Memory Allocation specifically for the line:
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
When creating a node in a linked list, we do not declare it like a
normal variable:
struct Node n; // ❌ Wrong for Linked List
This allocates memory statically (on stack), which cannot be linked dynamically.
Instead, we use dynamic memory allocation using malloc().
Here is the full statement again:
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
Now let’s analyze each component thoroughly.
Part-by-Part Breakdown
1. struct Node* newNode
This declares a pointer of type struct Node*.
newNode will hold the address of the newly allocated node.
Until memory is allocated, newNode does not point to any node.
2. malloc(sizeof(struct Node))
* What is malloc()?
malloc() stands for memory allocation.
It allocates memory from the heap during runtime.
malloc(bytes);
It returns a void pointer (void*) to the beginning of allocated memory.
* Why sizeof(struct Node)?
sizeof(struct Node) calculates the number of bytes required for one node.
For a node like:
struct Node {
int data; // 4 bytes (typically)
struct Node *next; // 4 or 8 bytes depending on OS
};
Total size = size of data + size of pointer.
Example (64-bit OS):
int = 4 bytes
pointer = 8 bytes
alignment padding may be added
So sizeof(struct Node) ensures exact required memory is allocated.
✔️ What malloc returns?
Pointer to memory block
Memory is uninitialized (contains garbage values)
❗ Why Typecasting malloc()?
(struct Node*)malloc(...)
Although C does auto-conversion from void* to any pointer type, explicit typecasting is:
Recommended in C++
Optional in C, but used for clarity in teaching and readability
Typecasting helps:
Avoid type mismatch errors
Make purpose clear to readers
Final pointer type:
struct Node*
Putting it all together
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
* Creates a new node in heap memory
* Returns address of the allocated memory
* Stores the address in pointer newNode
* Allows dynamic creation of nodes anytime during program execution
* What Happens in Memory?
malloc() requests memory from heap.
OS allocates required number of bytes.
The address of that block is returned.
newNode stores that address.
Now you can do:
newNode->data = value;
newNode->next = NULL;
Why Dynamic Allocation is Required in Linked Lists?
Linked List does not have fixed size.
Nodes must be created on demand.
Memory remains until manually freed using free().
Nodes are placed anywhere in memory → connected using pointers.
This is what makes linked lists flexible compared to arrays.
4. Types of Linked Lists
-
Singly Linked List
-
Doubly Linked List
-
Circular Linked List
-
Circular Doubly Linked List
In this post, we focus on Singly Linked List (base structure).
Other types will be covered in separate DSA posts.
5. Basic Operations with Implementation (C Version)
5.1 Insert at Beginning
Logic:
-
Create node
-
Point its
nexttohead -
Move head to new node
void insertAtBeginning(int value) {
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = head;
head = newNode;
}
5.2 Insert at End
void insertAtEnd(int value) {
struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (head == NULL) {
head = newNode;
return;
}
struct Node *temp = head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
5.3 Insert at Given Position
void insertAtPosition(int value, int pos) {
struct Node *newNode = malloc(sizeof(struct Node));
newNode->data = value;
if (pos == 1) {
newNode->next = head;
head = newNode;
return;
}
struct Node *temp = head;
for (int i = 1; i < pos - 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL) return; // position invalid
newNode->next = temp->next;
temp->next = newNode;
}
5.4 Delete from Beginning
void deleteBeginning() {
if (head == NULL) return;
struct Node *temp = head;
head = head->next;
free(temp);
}
5.5 Delete from End
void deleteEnd() {
if (head == NULL) return;
if (head->next == NULL) {
free(head);
head = NULL;
return;
}
struct Node *temp = head;
struct Node *prev = NULL;
while (temp->next != NULL) {
prev = temp;
temp = temp->next;
}
prev->next = NULL;
free(temp);
}
5.6 Delete at Position
void deleteAtPosition(int pos) {
if (head == NULL) return;
if (pos == 1) {
struct Node *temp = head;
head = head->next;
free(temp);
return;
}
struct Node *temp = head;
for (int i = 1; i < pos - 1 && temp != NULL; i++) {
temp = temp->next;
}
if (temp == NULL || temp->next == NULL) return;
struct Node *nodeToDelete = temp->next;
temp->next = nodeToDelete->next;
free(nodeToDelete);
}
5.7 Searching a Value
int search(int key) {
struct Node *temp = head;
while (temp != NULL) {
if (temp->data == key) return 1;
temp = temp->next;
}
return 0;
}
5.8 Display Linked List
void display() {
struct Node *temp = head;
while (temp != NULL) {
printf("%d → ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
6. Time Complexity Analysis
| Operation | Singly Linked List |
|---|---|
| Insert Beginning | O(1) |
| Insert End | O(n) |
| Insert Position | O(n) |
| Delete Beginning | O(1) |
| Delete End | O(n) |
| Delete Position | O(n) |
| Search | O(n) |
Linked lists prioritize fast insert/delete at the beginning.
7. Professional Engineering Notes
-
Linked list allocates memory dynamically → no wastage
-
Better than arrays for frequent insert/delete
-
Not cache-friendly (non-contiguous memory)
-
Extra memory required for pointer
-
Used in:
-
OS kernel (process scheduling)
-
Memory management
-
Hash chaining
-
Dynamic queues/stacks
-
8. Common Mistakes (Important!)
* Forgetting to update head
* Losing reference to nodes → memory leak
* Incorrect handling of empty list
* Infinite loop if temp->next not updated
* Not freeing deleted nodes
9. 20 Practice Questions — With Answers
Questions
-
Define Linked List.
-
Why is linked list dynamic?
-
Define node.
-
Give structure of a node.
-
Insert at beginning logic.
-
Insert at end logic.
-
Time complexity of inserting at head?
-
Why arrays are contiguous but linked lists are not?
-
What is a null pointer?
-
Purpose of
headpointer? -
How to check if list is empty?
-
Delete last node logic.
-
Search operation complexity.
-
What is memory leak?
-
Why extra memory is used in linked lists?
-
Draw singly linked list diagram.
-
Difference: array vs linked list.
-
What is garbage value?
-
What is dangling pointer?
-
Why linked lists are not cache-friendly?
Answers
-
Dynamic linear structure using nodes.
-
Because memory is allocated at runtime.
-
Element storing data and pointer.
-
struct Node{int data; struct Node* next;}; -
New node → next = head → head = new node.
-
Traverse to last → link new node.
-
O(1).
-
Because linked list uses scattered memory.
-
Pointer pointing to NULL.
-
Points to first node.
-
If head == NULL.
-
Traverse till second last → free last.
-
O(n).
-
Unfreed memory after losing reference.
-
For storing pointer to next node.
-
[Data|Next]→[Data|Next]→NULL.
-
Array fixed size, linked list dynamic.
-
Random uninitialized memory value.
-
Pointer pointing to a freed memory block.
-
Elements are not contiguous in memory.
ALSO CHECK
ALSO CHECK
Comments
Post a Comment