Linked List in C++ programming

Linked list data structures

Dynamically allocated data structures may be linked together in memory to form a chain. A linked list is a series of connected nodes, where each node is a data structure.

The nodes of a linked list are usually dynamically allocated, used, and then deleted, allowing the linked list to grow or shrink in size as the program runs.

If new information needs to be added to a linked list, the program simply allocates another node and inserts it into the series.

If a particular piece of information needs to be removed from the linked list, the program deletes the node containing that information.

The program below illustrates the creation of a simple linked list.

    #include <iostream>
    using namespace std;
    struct ListNode {
      double value;
      ListNode *next;
    };
    int main()  {
    ListNode *head;
    head = new ListNode; // Allocate new node
    head->value = 16.4; // Store the value
    head->next = NULL; // Signify end of list
    ListNode *secondPtr = new ListNode;
    secondPtr->value = 19.3;
    secondPtr->next = NULL; // Second node is end of list
    head->next = secondPtr; // First node points to second
    
    // Print the list
    cout << "First item is " << head->value << endl;
    cout << "Second item is " << head->next->value << endl;
    return 0;
    }

    Program Output :
    First item is 16.4
    Second item is 19.3

Inserting a node into a sorted list

Suppose that we have a linked list of numbers that is sorted in ascending order. We want to write the add function so that it inserts its argument number in the list at a position that leaves the list sorted.

The entire function, including the code for creating a new node and inserting it at the point just after previousNodePtr but before nodePtr, is given here:

The entire function, including the code for creating a new node and inserting it at the point just after previousNodePtr but before nodePtr:

    //included file header SortedNumberList
    #include "SortedNumberList.h"  
    void SortedNumberList::add(double number){
    ListNode *nodePtr, *previousNodePtr;
    if (head == NULL || head->value >= number) {
    head = new ListNode(number, head);
    }   else
    {
    previousNodePtr = head;
    nodePtr = head->next;
    
    // Find the insertion point
    while (nodePtr != NULL && nodePtr->value < number) {
    previousNodePtr = nodePtr;
    nodePtr = nodePtr->next;
    }
    
    // Insert the new node just before nodePtr
    previousNodePtr->next = new ListNode(number, nodePtr);
    }  
    }

Removing an element from a list

The remove member function uses a pointer nodePtr to search for a node containing the value number that is to be removed.

During this process, a second pointer previousNodePtr trails behind nodePtr, always pointing to the node preceding the one pointed to by nodePtr.

When nodePtr points to the node to be deleted, previousNodePtr->next is set to nodePtr->next. This causes the successor pointers in the list to bypass the node containing number, allowing its memory to be freed using delete.

The entire function is shown here:

    void NumberList::remove(double number) {
    ListNode *nodePtr, *previousNodePtr;
    if (!head) return;
    if (head->value == number){
    nodePtr = head;
    head = head->next;
    delete nodePtr;
    }  else
    {
    nodePtr = head;
    while (nodePtr != NULL && nodePtr->value != number) {
    previousNodePtr = nodePtr;
    nodePtr = nodePtr->next;
    }
    if (nodePtr) {
    previousNodePtr->next = nodePtr->next;
    delete nodePtr;}   
    }   
    }

Notice that the remove() function is a member of NumberList rather than SortedNumber- List. Unlike add(), the remove() function works with both sorted and unsorted lists, and so does not have to be overridden.