An Introduction to Linked Lists in C


Introduction

A linked list is a fundamental data structure in computer science and C programming. It consists of nodes, where each node contains data and a reference to the next node in the sequence. Linked lists provide dynamic memory allocation and efficient insertions and deletions. In this guide, we'll introduce you to the concept of linked lists in C and provide sample code to illustrate their usage.


Key Concepts

Before we dive into examples, let's cover some key concepts related to linked lists:

  • Node: The basic building block of a linked list, containing data and a reference (pointer) to the next node.
  • Head: The first node of the list, used as the entry point for accessing the list.
  • Tail: The last node of the list, where the next reference points to NULL.
  • Singly Linked List: Each node has a reference to the next node in the list.
  • Doubly Linked List: Each node has references to both the next and the previous nodes, allowing for bidirectional traversal.

Sample Code

Let's explore an example of a singly linked list in C:


#include <stdio.h>
#include <stdlib.h>
// Define a node structure
struct Node {
int data;
struct Node* next;
};
int main() {
// Create nodes
struct Node* head = NULL;
struct Node* second = NULL;
struct Node* third = NULL;
// Allocate memory for nodes
head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
// Assign data and set next pointers
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL; // The last node's next is NULL
// Traverse and print the linked list
struct Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
return 0;
}

Conclusion

Linked lists are versatile data structures in C that provide efficient dynamic memory allocation and support various operations like insertions and deletions. This guide introduced you to the concept of linked lists and provided sample code for creating a singly linked list. As you continue your C programming journey, you'll find linked lists to be a valuable tool for managing and manipulating data in various applications.