C Notes
HubApplications of C Programming LanguageFeatures of C Programming LanguageHistory of C Programming LanguageWhat is C Language?Why Learn C Programming in 2024?First C Program - Hello World in C with ExplanationGCC Compiler - Complete Guide to GNU C CompilerInstall C Compiler on Linux - GCC Setup Guide for All DistrosInstall C Compiler on macOS - Xcode Command Line Tools and Homebrew GCCInstall C Compiler on Windows - MinGW, MSYS2, and WSL GuideSetup VS Code for C Programming - Complete Configuration GuideC Syntax Rules — Complete GuideComments in C ProgrammingConstants in C ProgrammingData Types in CIdentifiers in C ProgrammingKeywords in C ProgrammingStructure of a C ProgramVariables in C ProgrammingArithmetic Operators in C ProgrammingAssignment Operators in C ProgrammingBitwise Operators in C ProgrammingIncrement and Decrement Operators in CLogical Operators in C ProgrammingRelational Operators in C ProgrammingTernary Operator in C ProgrammingBreak Statement in C ProgrammingContinue Statement in C ProgrammingDo-While Loop in C ProgrammingFor Loop in C ProgrammingGoto Statement in C Programmingif-else Statement in C Programmingif Statement in C ProgrammingNested if Statements in C ProgrammingSwitch Statement in C ProgrammingWhile Loop in C ProgrammingFunction Arguments in C - Pass by Value vs Pass by ReferenceFunction Call in C ProgrammingFunction Declaration (Prototype) in CFunction Definition in C ProgrammingIntroduction to Functions in C ProgrammingRecursion in C ProgrammingReturn Statement in C ProgrammingStorage Classes in C ProgrammingArray Operations in C - Searching, Sorting, Insert and DeleteArray Programs in C - Reverse, Rotate, Duplicates, MergeIntroduction to Arrays in C ProgrammingMultidimensional Arrays in C ProgrammingOne Dimensional Arrays in C ProgrammingPassing Arrays to Functions in CTwo Dimensional Arrays in C ProgrammingString Comparison in C - strcmp, strncmp, Case-InsensitiveString Functions in C - strlen, strcpy, strcat, strcmpC String Handling Library - Complete string.h ReferenceString Manipulation in C - Reverse, Uppercase, PalindromeString Programs in C - Anagram, Word Count, Vowels, FrequencyStrings in C Programming - Complete IntroductionDouble Pointers in C - Pointer to PointerPointer Arithmetic in C ProgrammingPointer Declaration and Initialization in CPointer Programs in C - Swap, String Reversal, Dynamic AllocationPointers and Arrays in C - The Relationship ExplainedPointers and Functions in C - Pass by ReferenceIntroduction to Pointers in C ProgrammingVoid Pointers in C - Generic Pointers Guidecalloc() in C – Contiguous Memory AllocationDynamic Arrays in C – Runtime-Sized Arraysfree() in C – Releasing Dynamic Memorymalloc() in C – Dynamic Memory AllocationMemory Management Best Practices in Crealloc() in C – Resizing Dynamic MemoryBinary Files in C – fread and fwriteFile Handling in C – IntroductionFile Handling Projects in C – Student Records & Phone BookFile Modes in C – Complete Guidefopen() and fclose() in C – Opening and Closing FilesReading Files in C – fgetc, fgets, fscanf, freadWriting Files in C – fputc, fputs, fprintf, fwriteConditional Compilation in C – #ifdef, #ifndef, #if#define Macros in C – Constants and Macro FunctionsHeader Files in C – Creating Custom Headers#include Directive in C – File InclusionMacro Functions in C – Parameterized MacrosC Preprocessor – Overview and DirectivesGraphs in C – Adjacency Matrix, Adjacency List, BFS, and DFSHash Tables in C – Implementation, Collision Handling, and ChainingLinked List in C – Singly, Doubly, and Circular with ImplementationQueue in C – Linear, Circular, and Priority Queue ImplementationStack in C – Array and Linked List Implementation with ApplicationsTrees in C – Binary Search Tree Implementation with TraversalsC Programming Best Practices – Coding Standards, Safety, and PerformanceBit Fields in C – Definition, Use Cases, and Protocol HeadersC Standard Library Overview – All Headers and Common FunctionsCommand Line Arguments in C – argc and argv ExplainedDebugging Techniques in C – GDB, Valgrind, and SanitizersFunction Pointers in C – Complete Guide with ExamplesMemory Layout of a C Program – Text, Data, BSS, Heap, StackBank Management System in C – Complete Project with File StorageFile Encryption Tool in C – XOR Cipher ImplementationLibrary Management System in C – Complete Project with Source CodeMini Compiler in C – Lexer and Parser for Simple ExpressionsSnake Game in C – Console-Based Game with Source CodeStudent Management System in C – Complete Project with Source CodeC Programming Cheatsheet – Complete Quick Reference GuideTop 50 C Programming Interview Questions with Answers (2025)Memory Management Interview Questions in C with AnswersOutput Prediction Questions in C – What Will This Program Print?Pointer Interview Questions in C – Tricky Problems with AnswersCommon C Programming Errors and Solutions – Debugging GuideImportant C Programs – 50+ Frequently Asked Programs with SolutionsQuick Revision Notes for C Programming – Complete C in 10 MinutesRecommended C Programming Books – From Beginner to ExpertFormat Specifiers in C - Complete Referencegetchar() and putchar() in C Programminggets() and puts() in C ProgrammingC Input Output Programs and Examplesprintf() Function in C Programmingscanf() Function in C ProgrammingArrays of Structures in C – Managing CollectionsEnums in C – Enumerated Data TypesNested Structures in C – Struct Within StructPointers to Structures in C – Arrow OperatorStructures in C – User-Defined Data Typestypedef in C – Creating Type AliasesUnions in C – Shared Memory Data Types
Complete guide to implementing linked lists in C covering singly linked list, doubly linked list, circular linked list, all operations with code examples and output.
A linked list is a dynamic data structure where elements are stored in nodes, and each node points to the next one. Unlike arrays, linked lists don't require contiguous memory and can grow or shrink during runtime. This makes them ideal when you don't know the size of data in advance or need frequent insertions and deletions.
Why Use Linked Lists Over Arrays?
| Feature | Array | Linked List |
|---|---|---|
| Memory allocation | Contiguous, fixed | Non-contiguous, dynamic |
| Size | Fixed at creation | Grows/shrinks at runtime |
| Insertion at beginning | O(n) – shift all elements | O(1) – change one pointer |
| Deletion at middle | O(n) – shift elements | O(1) – after reaching node |
| Random access | O(1) – direct indexing | O(n) – must traverse |
| Memory overhead | None | Extra pointer per node |
| Cache performance | Excellent | Poor (scattered memory) |
Singly Linked List
Each node contains data and a pointer to the next node. The last node points to NULL.
Node Structure
c example
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
// Create a new node
Node* createNode(int data) {
Node *newNode = (Node*)malloc(sizeof(Node));
if (!newNode) {
fprintf(stderr, "Memory allocation failed\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}Complete Singly Linked List Implementation
Example
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node* createNode(int data) {
Node *newNode = (Node*)malloc(sizeof(Node));
if (!newNode) { perror("malloc"); exit(1); }
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Insert at the beginning - O(1)
void insertAtBeginning(Node **head, int data) {
Node *newNode = createNode(data);
newNode->next = *head;
*head = newNode;
}
// Insert at the end - O(n)
void insertAtEnd(Node **head, int data) {
Node *newNode = createNode(data);
if (*head == NULL) {
*head = newNode;
return;
}
Node *temp = *head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
}
// Insert at position - O(n)
void insertAtPosition(Node **head, int data, int position) {
if (position == 0) {
insertAtBeginning(head, data);
return;
}
Node *temp = *head;
for (int i = 0; i < position - 1 && temp != NULL; i++)
temp = temp->next;
if (temp == NULL) {
printf("Position out of range\n");
return;
}
Node *newNode = createNode(data);
newNode->next = temp->next;
temp->next = newNode;
}
// Delete by value
void deleteNode(Node **head, int key) {
if (*head == NULL) return;
// If head node holds the key
if ((*head)->data == key) {
Node *temp = *head;
*head = (*head)->next;
free(temp);
return;
}
Node *prev = *head;
Node *curr = (*head)->next;
while (curr != NULL && curr->data != key) {
prev = curr;
curr = curr->next;
}
if (curr == NULL) {
printf("Value %d not found\n", key);
return;
}
prev->next = curr->next;
free(curr);
}
// Search for a value - O(n)
int search(Node *head, int key) {
int position = 0;
while (head != NULL) {
if (head->data == key) return position;
head = head->next;
position++;
}
return -1;
}
// Reverse the list - O(n)
void reverse(Node **head) {
Node *prev = NULL, *curr = *head, *next = NULL;
while (curr != NULL) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
*head = prev;
}
// Display the list
void display(Node *head) {
while (head != NULL) {
printf("%d -> ", head->data);
head = head->next;
}
printf("NULL\n");
}
// Count nodes
int count(Node *head) {
int c = 0;
while (head != NULL) { c++; head = head->next; }
return c;
}
// Free entire list
void freeList(Node **head) {
Node *temp;
while (*head != NULL) {
temp = *head;
*head = (*head)->next;
free(temp);
}
}
int main() {
Node *head = NULL;
insertAtEnd(&head, 10);
insertAtEnd(&head, 20);
insertAtEnd(&head, 30);
insertAtBeginning(&head, 5);
insertAtPosition(&head, 15, 2);
printf("List: ");
display(head);
printf("Count: %d\n", count(head));
int pos = search(head, 20);
printf("Search 20: found at position %d\n", pos);
deleteNode(&head, 15);
printf("After deleting 15: ");
display(head);
reverse(&head);
printf("Reversed: ");
display(head);
freeList(&head);
return 0;
}
Output
List: 5 -> 10 -> 15 -> 20 -> 30 -> NULL Count: 5 Search 20: found at position 3 After deleting 15: 5 -> 10 -> 20 -> 30 -> NULL Reversed: 30 -> 20 -> 10 -> 5 -> NULL
Doubly Linked List
Each node has pointers to both the next and previous nodes, allowing traversal in both directions.
c example
#include <stdio.h>
#include <stdlib.h>
typedef struct DNode {
int data;
struct DNode *prev;
struct DNode *next;
} DNode;
DNode* createDNode(int data) {
DNode *node = (DNode*)malloc(sizeof(DNode));
node->data = data;
node->prev = NULL;
node->next = NULL;
return node;
}
void insertFront(DNode **head, int data) {
DNode *newNode = createDNode(data);
newNode->next = *head;
if (*head != NULL)
(*head)->prev = newNode;
*head = newNode;
}
void insertBack(DNode **head, int data) {
DNode *newNode = createDNode(data);
if (*head == NULL) { *head = newNode; return; }
DNode *temp = *head;
while (temp->next != NULL) temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
}
void deleteDNode(DNode **head, int key) {
DNode *temp = *head;
while (temp != NULL && temp->data != key)
temp = temp->next;
if (temp == NULL) return;
if (temp->prev) temp->prev->next = temp->next;
else *head = temp->next;
if (temp->next) temp->next->prev = temp->prev;
free(temp);
}
void displayForward(DNode *head) {
printf("Forward: ");
while (head != NULL) {
printf("%d <-> ", head->data);
if (head->next == NULL) break;
head = head->next;
}
printf("NULL\n");
printf("Backward: ");
while (head != NULL) {
printf("%d <-> ", head->data);
head = head->prev;
}
printf("NULL\n");
}
int main() {
DNode *head = NULL;
insertBack(&head, 10);
insertBack(&head, 20);
insertBack(&head, 30);
insertFront(&head, 5);
displayForward(head);
deleteDNode(&head, 20);
printf("\nAfter deleting 20:\n");
displayForward(head);
return 0;
}Output
Forward: 5 <-> 10 <-> 20 <-> 30 <-> NULL Backward: 30 <-> 20 <-> 10 <-> 5 <-> NULL After deleting 20: Forward: 5 <-> 10 <-> 30 <-> NULL Backward: 30 <-> 10 <-> 5 <-> NULL
Circular Linked List
The last node points back to the first node instead of NULL, forming a circle.
c example
#include <stdio.h>
#include <stdlib.h>
typedef struct CNode {
int data;
struct CNode *next;
} CNode;
void insertCircular(CNode **head, int data) {
CNode *newNode = (CNode*)malloc(sizeof(CNode));
newNode->data = data;
if (*head == NULL) {
*head = newNode;
newNode->next = newNode; // Points to itself
} else {
CNode *temp = *head;
while (temp->next != *head)
temp = temp->next;
temp->next = newNode;
newNode->next = *head;
}
}
void displayCircular(CNode *head) {
if (head == NULL) { printf("Empty\n"); return; }
CNode *temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("(back to %d)\n", head->data);
}
int main() {
CNode *head = NULL;
insertCircular(&head, 10);
insertCircular(&head, 20);
insertCircular(&head, 30);
insertCircular(&head, 40);
displayCircular(head);
return 0;
}Output
10 -> 20 -> 30 -> 40 -> (back to 10)
Interview Questions on Linked Lists
Q1: How do you detect a cycle in a linked list? Use Floyd's cycle detection (tortoise and hare): Two pointers, one moving one step and another two steps. If they meet, there's a cycle.
Q2: How to find the middle element in one pass? Use two pointers – slow moves one step, fast moves two steps. When fast reaches the end, slow is at the middle.
Q3: What's the time complexity of inserting at the beginning vs end? Beginning: O(1). End: O(n) for singly linked list, O(1) if you maintain a tail pointer.
Q4: How do you merge two sorted linked lists? Compare head nodes, pick the smaller one, advance that list's pointer, repeat. Use recursion or iteration.
Q5: What's the advantage of doubly linked list over singly linked list? Bi-directional traversal, O(1) deletion when you have the node pointer (no need to find previous), and easier implementation of certain algorithms like LRU cache.
Summary
Linked lists are fundamental data structures that provide dynamic memory allocation and efficient insertions/deletions. Singly linked lists use less memory but only allow forward traversal. Doubly linked lists enable bi-directional movement at the cost of extra memory. Circular linked lists are useful for round-robin scheduling and buffer management. Choose the right variant based on your access patterns and memory constraints.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Linked List in C – Singly, Doubly, and Circular with Implementation.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this C Programming topic.
Search Terms
c-programming, c programming, programming, data, structures, linked, list, linked list in c – singly, doubly, and circular with implementation
Related C Programming Topics
Continue learning this concept
Data Structures In CGraphs in C – Adjacency Matrix, Adjacency List, BFS, and DFSLearn graph data structure in C with adjacency matrix and adjacency list representations, BFS and DFS traversal algorithms, and complete implementation examples.Data Structures In CHash Tables in C – Implementation, Collision Handling, and ChainingLearn hash table implementation in C with hash functions, collision resolution using chaining and open addressing, performance analysis, and practical examples.Data Structures In CQueue in C – Linear, Circular, and Priority Queue ImplementationLearn queue data structure in C with linear queue, circular queue, and priority queue implementations using arrays and linked lists with complete code examples.Data Structures In CStack in C – Array and Linked List Implementation with ApplicationsLearn stack data structure in C with array-based and linked list implementations, push/pop operations, applications like expression evaluation, and interview questions.Data Structures In CTrees in C – Binary Search Tree Implementation with TraversalsLearn tree data structure in C with BST implementation covering insertion, deletion, searching, inorder/preorder/postorder traversals, and tree operations.BasicsComments in C ProgrammingLearn about comments in C — single-line comments, multi-line comments, best practices, nested comments, and when to use comments effectively in your code.