What is a Linked List?
A linked list is a linear data structure where elements (called nodes) are stored in memory and connected using pointers.
Each node contains:
- Data – the actual value.
- Pointer – a reference to the next node in the list.
[Data|Next] -> [Data|Next] -> [Data|Next] -> NULL
Why Use Linked Lists?
- Dynamic size — grows and shrinks at runtime
- Efficient insertion/deletion (no need to shift elements)
- Useful when the number of elements is unknown or changes frequently
Types of Linked Lists in C
- Singly Linked List – Points only to the next node.
- Doubly Linked List – Each node points to both next and previous.
- Circular Linked List – Last node points back to the first.
Structure of a Node in C
#include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; };
How to Create a Node in C
To work with linked lists in C, we define a function to create new nodes:
// Function to create a new node with given value struct Node* createNode(int value) { struct Node* newNode = (struct Node*) malloc(sizeof(struct Node)); if (newNode == NULL) { printf("Memory allocation failed\n"); exit(1); } newNode->data = value; // Assign data newNode->next = NULL; // Initialize next pointer to NULL return newNode; }
Insert Node at the Beginning of the Linked List
// Insert a new node at the beginning of the list void insertAtBeginning(struct Node** head_ref, int value) { struct Node* newNode = createNode(value); newNode->next = *head_ref; // Point new node to current head *head_ref = newNode; // Update head to new node }
Insert Node at the End of the Linked List
// Insert a new node at the end of the list void insertAtEnd(struct Node** head_ref, int value) { struct Node* newNode = createNode(value); if (*head_ref == NULL) { *head_ref = newNode; // If list is empty, new node is head return; } struct Node* temp = *head_ref; while (temp->next != NULL) { temp = temp->next; // Traverse to the last node } temp->next = newNode; // Link last node to new node }
Traversing and Printing the Linked List
// Traverse the linked list and print all elements void printList(struct Node* head) { struct Node* temp = head; while (temp != NULL) { printf("%d -> ", temp->data); temp = temp->next; } printf("NULL\n"); // Indicate end of list }
Deleting a Node by Value (Key)
// Delete the first node with the specified key (value) void deleteNode(struct Node** head_ref, int key) { struct Node* temp = *head_ref; struct Node* prev = NULL; // If head node itself holds the key if (temp != NULL && temp->data == key) { *head_ref = temp->next; // Change head free(temp); // Free old head return; } // Search for the key in the list while (temp != NULL && temp->data != key) { prev = temp; temp = temp->next; } // If key was not found in the list if (temp == NULL) return; // Unlink node from linked list prev->next = temp->next; free(temp); // Free memory }
Sample Main Function
int main() { struct Node* head = NULL; // Start with an empty list insertAtEnd(&head, 10); insertAtBeginning(&head, 5); insertAtEnd(&head, 20); printf("Linked list: "); printList(head); // Expected output: 5 -> 10 -> 20 -> NULL deleteNode(&head, 10); printf("After deleting 10: "); printList(head); // Expected output: 5 -> 20 -> NULL return 0; }
Complete Example of Linked List
#include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; }; struct Node* createNode(int value) { struct Node* newNode = (struct Node*) malloc(sizeof(struct Node)); if (!newNode) { printf("Memory allocation failed\n"); exit(1); } newNode->data = value; newNode->next = NULL; return newNode; } void insertAtEnd(struct Node** head_ref, int value) { struct Node* newNode = createNode(value); if (*head_ref == NULL) { *head_ref = newNode; return; } struct Node* temp = *head_ref; while (temp->next != NULL) temp = temp->next; temp->next = newNode; } void printList(struct Node* head) { while (head != NULL) { printf("%d -> ", head->data); head = head->next; } printf("NULL\n"); } int main() { struct Node* head = NULL; insertAtEnd(&head, 1); insertAtEnd(&head, 2); insertAtEnd(&head, 3); printList(head); return 0; }
Output:
advertisement
Free 30-Day Java Certification Bootcamp is Live. Join Now!
1 -> 2 -> 3 -> NULL
Explanation:
- The program defines a Node structure to represent each element in a singly linked list.
- The createNode() function dynamically allocates memory and initializes a node with a given value.
- The insertAtEnd() function appends a new node at the end of the list, updating pointers accordingly.
- If the list is empty, the new node becomes the head.
- The printList() function traverses the list and prints all node values in order, ending with NULL.
Advantages of Linked Lists
- Dynamic Size: Can grow or shrink in size during execution.
- Efficient Insertions/Deletions: Insertions and deletions are more efficient compared to arrays.
- Memory Utilization: Does not require memory reallocation or reorganization.
Disadvantages of Linked Lists
- Memory Usage: Requires extra memory for pointers.
- Sequential Access: Cannot access elements randomly; must traverse from the head.
- Complexity: More complex to implement compared to arrays.
Sanfoundry Global Education & Learning Series – 1000 C Tutorials.
If you wish to look at all C Tutorials, go to C Tutorials.
advertisement
Related Posts:
- Watch Advanced C Programming Videos
- Apply for Computer Science Internship
- Check Computer Science Books
- Apply for C Internship
- Practice BCA MCQs