Implementing Linked List Data Structure in C++

A linked list is a type of linear data structure consisting of a series of nodes. Each node contains two parts: a data field and a pointer to the next node. Unlike arrays, linked lists do not require contiguous memory space, making them more efficient for insertion and deletion operations.

This article will detail how to implement a simple singly linked list in C++, providing relevant code examples and explanations.

1. Node Structure

First, we need to define the node structure in the linked list. In C++, we can use <span>struct</span> to represent a node. Each node will store an integer value and a pointer to the next node.

struct Node {    int data;       // Data field    Node* next;     // Pointer to the next node    // Constructor    Node(int value) : data(value), next(nullptr) {}};

Explanation:

• <span>data</span>: Used to store the element value.
• <span>next</span>: Used to point to the next node, initialized to <span>nullptr</span> by default.
• The constructor is used to conveniently create new node instances.

2. Linked List Class Definition

Next, we define a linked list class to manage these nodes. This class will include basic functionalities such as insertion, deletion, and searching.

class LinkedList {private:    Node* head; // Pointer to the head nodepublic:    LinkedList() : head(nullptr) {} // Initialize as an empty linked list    void insert(int value);           // Insert new value    void remove(int value);           // Remove specified value    bool search(int value);           // Search for specified value    void display();                   // Print linked list elements    ~LinkedList();                    // Destructor, free memory};

Explanation:

• <span>head</span>: Points to the first element (head node) of the linked list.
• Various member functions are used to perform operations such as insertion, deletion, searching, and displaying all current elements.

3. Implementing Functionalities

Now we will implement these functionalities one by one:

Insertion Operation

Here we implement adding a new element to the end of the list, creating a new Node and updating the link.

void LinkedList::insert(int value) {    Node* newNode = new Node(value);    if (!head) {   // If the current list is empty, the new node becomes the head.        head = newNode;        return;    }    Node* temp = head;    // Traverse to the last item and link the new item:    while (temp->next != nullptr) {        temp = temp->next;    }    temp->next = newNode;}

Deletion Operation

This method searches for the target number, and if found, removes it and adjusts the links accordingly:

void LinkedList::remove(int value) {    if (!head)        return;    if (head->data == value) {      // If the head node is to be deleted.        Node* toDelete = head;        head = head->next;        delete toDelete;        return;    }    Node* current = head;    while (current->next && current->next->data != value)        current = current->next;    if (current->next) {            Node* toDelete = current->next;        current->next = toDelete->next;        delete toDelete;    }}

Search Operation

This checks for the existence of the data to be searched by traversing each node:

bool LinkedList::search(int value) {    Node* temp = head;    while (temp != nullptr) {        if (temp->data == value)            return true;     // Return true if found.        temp = temp->next;    }   return false;}

Display Output

This allows the user to see all current values, providing a clear understanding of the entire list’s contents:

void LinkedList::display() {    Node* temp = head;    while (temp != nullptr) {        std::cout << temp->data << " ";        temp = temp->next;    } std::cout << std::endl; }

4. Destructor

When the object is destroyed, we should free the occupied memory to avoid memory leaks:

LinkedList::~LinkedList() {    Node *current = head, *toDelete;    while (current != nullptr) {        toDelete = current;        current = current->next;        delete toDelete;    }}

5. Complete Program Example

Below is the complete code combining all the above parts:

#include <iostream>struct Node{   int data;   Node *next;   Node(int val) : data(val), next(nullptr){} };class LinkedList{private :   Node *head ;public:            LinkedList():head(nullptr){}   void insert( int val );          void remove( int val );         bool search( int val );   void display();              ~LinkedList(){                      while(head!=nullptr){          remove(head->data); }            }};void LinkedList :: insert( int val ){      auto node=new(Node)(val);      if(!head){            head=node;            return;}     auto iter=head;     while(iter->next ){                     iter=iter->next; }     iter->next=node;}int main() {    LinkedList ll{};    ll.insert(10);    ll.insert(20);    ll.insert(30);    std::cout << "Current List: ";    ll.display();    std::cout << "Searching for 20: " << (ll.search(20)? "Found" : "Not Found") << std::endl;    ll.remove(20);    std::cout << "After Removing: ";    ll.display();}</iostream>