Algorithm & Program to Create and Traverse a Linked List

A linked list is a fundamental data structure in C and other programming languages. Unlike arrays, linked lists can dynamically grow or shrink as elements are added or removed without requiring element shifting. Each element in a linked list, called a node, consists of two parts: data (which stores the value) and a pointer (which stores the memory address of the next node).

After creating a linked list, we often need to access all its elements. Since linked lists don’t store elements in contiguous memory locations like arrays, we cannot directly access elements by index. Instead, we begin at the head (first node) and sequentially visit each node until reaching the end. This process is called linked list traversal.

Why is Linked List Traversal Necessary?

Traversing a linked list involves visiting each node sequentially from the head to the tail (last node). Traversal is essential because:

1. No Random Access: Linked lists store elements in non-contiguous memory locations, preventing direct indexed access like arrays. To reach any node, we must traverse from the beginning.
2. Displaying Elements: Traversal allows us to view, print, or process all data stored in the list.
3. Performing Operations: Operations like searching, updating, or deleting specific nodes require traversal to locate the target node first.

Linked List Example

The diagram above illustrates a singly linked list. The first node stores value 1 in its data field and contains a pointer to the next node. Each subsequent node follows this pattern: node with value 2 points to node with 3, which points to node with 4, which points to node with 5. The final node contains value 5 and its pointer is NULL, indicating the list’s end. A special pointer called Head references the first node, providing the entry point to the list.

Why Use Linked Lists Over Arrays?

While arrays are straightforward to use, they have significant limitations. Arrays have fixed sizes determined at declaration, preventing dynamic resizing. Additionally, inserting or deleting elements within an array requires shifting subsequent elements, making these operations inefficient (O(n)). Linked lists overcome these limitations by allowing dynamic size adjustment and efficient insertions/deletions through pointer manipulation rather than element shifting.

Types of Linked Lists

1. Singly Linked List

• Each node contains data and a pointer to the next node.
• Supports forward traversal only.
• Example:
  10 → 20 → 30 → NULL

2. Doubly Linked List

• Each node contains data, a pointer to the next node, and a pointer to the previous node.
• Supports both forward and backward traversal.
• Example:
  NULL ← 10 ⇄ 20 ⇄ 30 → NULL

3. Circular Linked List

• The last node points back to the first node instead of NULL.
• Forms a circular chain with no clear beginning or end.
• Example:
  10 → 20 → 30 → (back to 10)

Algorithm to Create and Traverse a Linked List

Creating a Linked List

1. Allocate Memory for the New Node

• Use malloc() to reserve memory for the node.
• If memory allocation fails (malloc() returns NULL), display “Memory allocation failed” and stop execution.

2. Initialize the New Node

• Set the node’s data field to the given value.
• Set the node’s next pointer to NULL.

3. Insert the New Node

• If the list is empty (head == NULL):
  • Set head to point to the new node.
• If the list is not empty:
  • Create a temporary pointer temp and assign it head.
  • Traverse to the last node (temp->next != NULL).
  • Set temp->next to the new node.

Traversing a Linked List

1. Initialize Traversal Pointer
2. Create a temporary pointer temp and set it to head
3. Check for Empty List
4. If head == NULL, print “List is empty” and terminate
5. Iterate Through Nodes
6. While temp != NULL:
7. Access or print the current node’s data (temp->data)
8. Move to the next node (temp = temp->next)
9. End of Traversal
10. When temp == NULL, all nodes have been visited
11. END

C Program to Create and Traverse a Linked List

Below is a complete C program demonstrating linked list creation and traversal:

#include <stdio.h>
#include <stdlib.h>

// Define node structure
struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node
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;
    newNode->next = NULL;
    return newNode;
}

// Function to insert node at the end
void insertAtEnd(struct Node** head, int value) {
    struct Node* newNode = createNode(value);
    
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    struct Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

// Function to traverse and print the linked list
void traverseList(struct Node* head) {
    struct Node* temp = head;
    
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    
    printf("Linked List: ");
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// Main function
int main() {
    struct Node* head = NULL;
    
    // Create and populate the linked list
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    
    // Traverse and display the list
    traverseList(head);
    
    return 0;
}

Output

Linked List: 10 -> 20 -> 30 -> NULL

Code Explanation

1. Structure Definition

struct Node {
    int data;
    struct Node* next;
};
struct Node* head = NULL;

This code defines the structure of a linked list node and initializes an empty list. Each Node contains two fields: data (stores the node’s value) and next (a pointer to the following node). The head pointer serves as the list’s entry point; when set to NULL, it indicates an empty list with no nodes.

2. Node Creation Function

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

The createNode() function dynamically allocates memory for a new node using malloc(). It initializes the node’s data field with the provided value and sets the next pointer to NULL (indicating no subsequent node). The function returns the address of the newly created node for insertion into the list.

3. Insertion at End Function

void insertAtEnd(struct Node** head, int value) {
    struct Node* newNode = createNode(value);
    
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    struct Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

The insertAtEnd() function adds a new node to the list’s end. It first creates a node using createNode(). If the list is empty (*head == NULL), it sets the head to point to the new node. Otherwise, it traverses to the last node (where next is NULL) and updates that node’s next pointer to reference the new node.

4. Traversal Function

void traverseList(struct Node* head) {
    struct Node* temp = head;
    
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }
    
    printf("Linked List: ");
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

The traverseList() function visits each node sequentially. It begins by checking if the list is empty. If not, it initializes a temporary pointer temp to head and iterates through the list. During each iteration, it prints the current node’s data and advances to the next node via temp->next. The loop terminates when temp becomes NULL, indicating the list’s end.

5. Main Function

int main() {
    struct Node* head = NULL;
    
    insertAtEnd(&head, 10);
    insertAtEnd(&head, 20);
    insertAtEnd(&head, 30);
    
    traverseList(head);
    
    return 0;
}

The main() function demonstrates linked list operations. It initializes an empty list (head = NULL), inserts three values (10, 20, 30) using insertAtEnd(), and finally calls traverseList() to display the list contents. The program returns 0 upon successful execution.

Time and Space Complexity of Linked Lists

Time Complexity

Operation	Best Case	Average Case	Worst Case	Description
createNode()	O(1)	O(1)	O(1)	Constant time memory allocation
insertAtEnd()	O(1)	O(n)	O(n)	O(1) for empty list, O(n) otherwise
traverseList()	O(n)	O(n)	O(n)	Must visit all n nodes

Space Complexity

Operation	Auxiliary Space	Total Space	Description
createNode()	O(1)	O(1)	Allocates memory for one node
insertAtEnd()	O(1)	O(n)	Uses constant extra space for pointers
traverseList()	O(1)	O(n)	Uses one temporary pointer

Real-World Example

A linked list operates similarly to a treasure hunt where each clue points to the next location. You start at the first clue (head), follow its instructions to reach the next clue, and continue this process until you find a clue with no further instructions (NULL), marking the hunt’s end. Just as you cannot jump directly to the final clue without following the chain, you cannot access arbitrary nodes in a linked list without traversal.

Conclusion

Linked lists provide dynamic memory management capabilities that arrays lack, making them ideal for applications requiring frequent insertions and deletions. While traversal is necessary due to their sequential nature, understanding this fundamental operation opens doors to more advanced linked list manipulations. The chain-like structure of linked lists, whether visualized as a treasure hunt, train, or paperclip chain, makes them an intuitive and powerful data structure for managing dynamic data collections in programming.