A pointer is a variable whose value is the address of another variable. Pointers are essential for implementing linked lists because they store memory addresses of the next node.

Declaring and Using Pointers

#include <iostream>
using namespace std;

int main() {
    int y = 12;
    int *ptr;    // declaration of pointer variable
    
    ptr = &y;    // & returns the address of y
    
    cout << "Value at ptr (address): " << ptr << endl;
    cout << "Value stored at address: " << *ptr << endl;
    cout << "Value of y: " << y << endl;
    
    return 0;
}

Key operators:

• & (reference operator) – returns the memory address of a variable
• * (dereference operator) – accesses the value stored at an address

A linked list is a dynamic data structure where each element (called a node) contains two parts:

1. Data – the actual information to store
2. Next – a pointer (link) to the next node

Unlike arrays, linked lists can grow and shrink during program execution.

Structure of a Linked List Node

// Define a node structure using class
class Node {
public:
    int data;      // data part
    Node* next;    // pointer to next node
};

Creating a Simple Linked List

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

int main() {
    // Create three nodes
    Node* head = new Node();
    Node* second = new Node();
    Node* third = new Node();
    
    // Assign data and link nodes
    head->data = 10;
    head->next = second;
    
    second->data = 20;
    second->next = third;
    
    third->data = 30;
    third->next = NULL;  // NULL indicates end of list
    
    // Traverse and display the linked list
    Node* temp = head;
    cout << "Linked list: ";
    while (temp != NULL) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL" << endl;
    
    return 0;
}

Output: 10 -> 20 -> 30 -> NULL

Insertion Operations in Linked Lists

Inserting at the beginning:

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

void insertAtBeginning(Node** head, int newData) {
    // Create new node
    Node* newNode = new Node();
    newNode->data = newData;
    newNode->next = *head;  // Point to current head
    *head = newNode;        // Update head to new node
}

int main() {
    Node* head = NULL;
    
    // Insert elements at beginning
    insertAtBeginning(&head, 30);
    insertAtBeginning(&head, 20);
    insertAtBeginning(&head, 10);
    
    // Display
    Node* temp = head;
    cout << "Linked list: ";
    while (temp != NULL) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL" << endl;
    
    return 0;
}

Inserting at the end:

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

void insertAtEnd(Node** head, int newData) {
    Node* newNode = new Node();
    newNode->data = newData;
    newNode->next = NULL;
    
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    // Traverse to the last node
    Node* temp = *head;
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = newNode;
}

Deletion Operations in Linked Lists

Delete from beginning:

void deleteFromBeginning(Node** head) {
    if (*head == NULL) {
        cout << "List is empty" << endl;
        return;
    }
    Node* temp = *head;
    *head = (*head)->next;
    delete temp;
}

Delete from end:

void deleteFromEnd(Node** head) {
    if (*head == NULL) {
        cout << "List is empty" << endl;
        return;
    }
    
    Node* temp = *head;
    
    // If only one node
    if (temp->next == NULL) {
        *head = NULL;
        delete temp;
        return;
    }
    
    // Traverse to second last node
    while (temp->next->next != NULL) {
        temp = temp->next;
    }
    delete temp->next;
    temp->next = NULL;
}

Complete Working Example: Student Records Management

#include <iostream>
using namespace std;

class StudentNode {
public:
    int id;
    string name;
    StudentNode* next;
    
    StudentNode(int id, string name) {
        this->id = id;
        this->name = name;
        this->next = NULL;
    }
};

class StudentList {
private:
    StudentNode* head;
    
public:
    StudentList() {
        head = NULL;
    }
    
    void addStudent(int id, string name) {
        StudentNode* newNode = new StudentNode(id, name);
        
        if (head == NULL) {
            head = newNode;
        } else {
            StudentNode* temp = head;
            while (temp->next != NULL) {
                temp = temp->next;
            }
            temp->next = newNode;
        }
    }
    
    void displayStudents() {
        if (head == NULL) {
            cout << "No students in the list." << endl;
            return;
        }
        
        StudentNode* temp = head;
        cout << "\nStudent Records:" << endl;
        cout << "ID\tName" << endl;
        while (temp != NULL) {
            cout << temp->id << "\t" << temp->name << endl;
            temp = temp->next;
        }
    }
    
    bool searchStudent(int searchId) {
        StudentNode* temp = head;
        while (temp != NULL) {
            if (temp->id == searchId) {
                return true;
            }
            temp = temp->next;
        }
        return false;
    }
    
    void deleteStudent(int delId) {
        if (head == NULL) {
            cout << "List is empty." << endl;
            return;
        }
        
        if (head->id == delId) {
            StudentNode* temp = head;
            head = head->next;
            delete temp;
            cout << "Student deleted successfully." << endl;
            return;
        }
        
        StudentNode* temp = head;
        while (temp->next != NULL && temp->next->id != delId) {
            temp = temp->next;
        }
        
        if (temp->next == NULL) {
            cout << "Student not found." << endl;
        } else {
            StudentNode* nodeToDelete = temp->next;
            temp->next = temp->next->next;
            delete nodeToDelete;
            cout << "Student deleted successfully." << endl;
        }
    }
};

int main() {
    StudentList list;
    int choice;
    int id;
    string name;
    
    do {
        cout << "\n=== Student Record Menu ===" << endl;
        cout << "1. Add Student" << endl;
        cout << "2. Display All Students" << endl;
        cout << "3. Search Student by ID" << endl;
        cout << "4. Delete Student" << endl;
        cout << "5. Exit" << endl;
        cout << "Enter your choice: ";
        cin >> choice;
        
        switch(choice) {
            case 1:
                cout << "Enter Student ID: ";
                cin >> id;
                cout << "Enter Student Name: ";
                cin >> name;
                list.addStudent(id, name);
                cout << "Student added successfully!" << endl;
                break;
            case 2:
                list.displayStudents();
                break;
            case 3:
                cout << "Enter ID to search: ";
                cin >> id;
                if (list.searchStudent(id)) {
                    cout << "Student found!" << endl;
                } else {
                    cout << "Student not found." << endl;
                }
                break;
            case 4:
                cout << "Enter ID to delete: ";
                cin >> id;
                list.deleteStudent(id);
                break;
            case 5:
                cout << "Exiting program..." << endl;
                break;
            default:
                cout << "Invalid choice!" << endl;
        }
    } while (choice != 5);
    
    return 0;
}

In Tanzanian secondary schools, a linked list can be used to manage student attendance records dynamically. When students join or leave a class throughout the academic year, a linked list allows easy insertion and deletion of records without the fixed-size limitations of arrays. For example, when a new student transfers to a school in Morogoro, their record can be added to the attendance system instantly—no need to recreate or resize the entire data structure—making the attendance tracking system efficient for classes with changing enrollment numbers.