Implementing Singly Linked List in C++ Using Classes: From Struct to Object-Oriented Approach

Linked List Basics and Problem Analysis

A linked list is a fundamental dynamic data structure composed of nodes, each containing a data field and a pointer to the next node. In the user's original code, the list is implemented using a struct Node:

struct Node {
    int x;
    Node *next;
};

The initialization function initNode correctly sets the head node's data and pointer:

void initNode(struct Node *head, int n){
    head->x = n;
    head->next = NULL;
}

However, a critical issue exists in the addNode function:

void addNode(struct Node *head, int n){
    struct Node *NewNode = new Node;
    NewNode-> x = n;
    NewNode -> next = head;
    head = NewNode;
}

Here, head is passed as a pointer parameter; modifying head's direction is only effective within the function and does not affect the external head pointer. This prevents the linked list head from updating correctly, making newly added nodes inaccessible in subsequent operations.

Class-Based Linked List Implementation

To address this issue and enhance encapsulation and maintainability, a class-based approach is adopted. Referencing the best answer, the LinkedList class is defined:

class LinkedList{
    struct Node {
        int x;
        Node *next;
    };
    Node *head;

public:
    LinkedList(){
        head = NULL;
    }

    ~LinkedList(){
        Node *next = head;
        while(next) {
            Node *deleteMe = next;
            next = next->next;
            delete deleteMe;
        }
    }

    void addValue(int val){
        Node *n = new Node();
        n->x = val;
        n->next = head;
        head = n;
    }

    int popValue(){
        Node *n = head;
        int ret = n->x;
        head = head->next;
        delete n;
        return ret;
    }
};

In this implementation, the addValue function directly manages the list head via the class member variable head, avoiding pointer passing issues. New nodes are inserted at the head, forming a last-in-first-out (LIFO) stack-like structure.

Memory Management and Destructor

Dynamic memory allocation is central to linked list operations. The constructor initializes head to NULL, indicating an empty list. The destructor traverses all nodes to free dynamically allocated memory, preventing leaks:

~LinkedList(){
    Node *next = head;
    while(next) {
        Node *deleteMe = next;
        next = next->next;
        delete deleteMe;
    }
}

This ensures all node resources are properly reclaimed when the program ends.

Detailed Insert and Pop Operations

The addValue operation creates a new node, sets its next pointer to the current head, and updates head to point to the new node. For example, after adding 5, 10, and 20 in sequence, the list structure is: 20 -> 10 -> 5 -> NULL.

The popValue operation returns the head node's data, updates head to the next node, and deletes the original head. Note that this implementation lacks error checking; calling popValue on an empty list leads to undefined behavior.

Complete Example and Output

The main function demonstrates basic list usage:

int main() {
    LinkedList list;

    list.addValue(5);
    list.addValue(10);
    list.addValue(20);

    cout << list.popValue() << endl;
    cout << list.popValue() << endl;
    cout << list.popValue() << endl;
    return 0;
}

The output is:

20
10
5

This verifies the LIFO characteristic.

Object-Oriented Advantages and Extensions

The class-based implementation encapsulates the internal list structure, so external code does not need to manipulate node pointers directly, reducing error risk. The reference article further emphasizes class advantages, such as data abstraction, code organization, and extensibility. For instance, adding a print function to traverse and output list contents, or implementing other operations like searching or deleting specific nodes, can be done easily.

Conclusion

By comparing the user's original code with the optimized class implementation, this article illustrates the evolution of singly linked lists in C++ from struct-based to object-oriented approaches. Key improvements include using classes to encapsulate nodes and operations, managing the head pointer via member variables to avoid passing issues, and implementing a destructor for memory safety. This method enhances code robustness and maintainability, laying a foundation for learning more complex data structures.