can anyone help me with my linked list error please?

Question

There is an issue with my code. I need to write a program that creates a linked list and performs insertion, deleting from the beginning, deleting from the end, and printing. Everything in the program works fine, but the delete the first node function. It throws an error in the printing function (posted a picture of the error below). Does anyone know what seems to be the problem? The function that deletes the last node works and prints perfectly.

LINKED LIST PROGRAM:

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

void insert(Node** head,int n) //insertion method
{
    Node* newNode = new Node;
    newNode->data = n;
    newNode->next = (*head);
    (*head) = newNode;
}

Node* deleteFront(struct Node* head)//deleting first node in the list
{
    if (head == NULL)
        return NULL;
    else
    {
        Node* t = head;
        head = head->next;
        free(t);
        t = NULL;
    }

    return head; 
}

Node* deleteEnd(struct Node* head)//deleting last node in the list
{
    if (head == NULL)
        return NULL;
    else if (head->next == NULL) {
        free(head);
        head = NULL;
    }
    else {
        Node* prev = head;
        Node* prev2 = head;

        while (prev->next != NULL)
        {
            prev2 = prev;
            prev = prev->next;
        }

        prev2->next = NULL;
        free(prev);
        prev = NULL;
    }

    return head;
}

void printLL(Node* h)
{
    while (h != NULL)
    {
        cout << h->data << " ";
        h = h->next;
    }

    cout << endl;
}

int main()
{
    cout << "Linked list question 2: " << endl;
    //linked list question 2
    Node* n = NULL;
    insert(&n, 60);
    insert(&n, 40);
    insert(&n, 20);
    printLL(n);

    deleteFront(n);
    cout << "after deleting first node: ";
    printLL(n);

    deleteEnd(n);
    cout << "after deleting last element: ";
    printLL(n);
}

A picture of the error:

error

output

Answer 1

The bugs in your code have been mentioned in other answers and there were proposals to fix.

I would like to add an additional observation regarding your design of the Linked List. In standard implementations, Node is not visible to the outside world. The Node is not the LinkedList. The linked list contains Nodes. So, you would create a class List and it would contain the definition of a Node and a head pointer to the first node instance.

Then you would add all you functions as methods to the outer class List. These methods would work with the internal Node-chain. According to object oriented model you would encapsulate the interna of the methods and expose only what is needed to the outside world.

What you should also note is that your list is a forward list only. It has only one link to the next element. This makes some operations difficult, because you may need to always go from the beginning the list through the element what you what operate on. See your function delete_end. Here you even need to remember the previous element.

In double linked list, you could simply access also the previous element.

Therefore, if you check the CPP reference for a std::forward_list, you will find some maybe strange sounding functions like insert_after or erase_after or an iterator before_begin. This is all the result of having just forward references. A function like delete_last which would be pop_back in CPP language, is even not existing.

Therefore you maybe need to confirm, if you should implement a singly linked list or maybe a double linked list.

To make this more visible for you, I created some complete example code for a singly linked list for you.

Here I added also simple iterator functionality, which allows to use the class in a convenient way, e.g. with range based for loops or std::algorithms.

You may take this code to get some ideas for your own implementation.

#include <iostream>
#include <iterator>
#include <initializer_list>
#include <algorithm>

// Very simple implementation of a forward list
class SinglyLinkedList {

    // The node
    struct Node {
        int data{};     // Data. Would normally be a templated argument
        Node* next{};   // And the pointer to the next node
       
        Node(int i, Node* n=nullptr) : data(i), next(n) {}; // Simple constructor to set a value and next pointer
    };

    Node* head{};       // This is the start of the list
    // It would be advisable to have a tail pointer. We use the more inefficient approach here
    Node* getLast() { Node* n{ head }; while (n and n->next) n = n->next; return n; }

public:
    // Constructor / Destructor --------------------------------------------------------------------------------------------------------
    ~SinglyLinkedList() { clear(); }

    // Default constuctor
    SinglyLinkedList() {}   // Default

    // From an initialization list
    SinglyLinkedList(const std::initializer_list<int>& il) { clear();  for (const int i : il) push_back(i); } // From initializer list

    // Copy constructor
    SinglyLinkedList(const SinglyLinkedList& other) { clear(); for (const int i : other) push_back(i); }

    // Move constructor. Will steal the elements from the other 
    SinglyLinkedList(SinglyLinkedList&& other) noexcept { head = other.head; other.head = nullptr; }

    // Assignment operator
    SinglyLinkedList& operator = (const SinglyLinkedList& other) { clear(); for (const int i : other) push_back(i); }

    // Move assignment operator 
    SinglyLinkedList& operator = (SinglyLinkedList&& other) { head = other.head; other.head = nullptr; }

    // Housekeeping --------------------------------------------------------------------------------------------------------------
    void clear() { Node* tmp{ head }; while (tmp) { Node* toDelete{ tmp }; tmp = tmp->next; delete toDelete; } head = nullptr; }
    int empty() { return head == nullptr; }
    int size() { int k{}; Node* n{ head }; while (n) { ++k; n = n->next; } return k; }

    // Modify content --------------------------------------------------------------------------------------------------------------
    void push_front(int i) { Node* n = new Node(i); n->next = head; head = n; };
    void push_back(int i) { Node* n = new Node(i); Node* l = getLast();if (l) l->next = n; else head = n; }
    void pop_front() { if (head) { Node* tmp = head->next; delete head; head = tmp; } }
    void pop_back() { // This is a little bit more difficult in a singly linked list
        if (head) {
            Node* n{ head }, *previous{};
            while (n and n->next) {
                previous = n;
                n = n->next;
            }
            delete n;
            if (previous)
                previous->next = nullptr;
            else
                head->next = nullptr;
        }
    }

    // Access elements --------------------------------------------------------------------------------
    int front() { return head ? head->data : 0; };
    int back() { Node* n = getLast(); return n ? n->data: 0; }

    // Add iterator properties to class ---------------------------------------------------------------
    struct iterator {                           // Local class for iterator
        Node* iter{};                           // Iterator is basically a pointer to the node
 
        // Define alias names necessary for the iterator functionality
        using iterator_category = std::forward_iterator_tag;
        using difference_type = std::ptrdiff_t;
        using value_type = int;
        using pointer = int*;
        using reference = int&;

        // Constructor
        iterator() {}
        iterator(Node* n) : iter(n) {}

        // Dereferencing
        reference operator *() const { return iter->data; }
        pointer operator ->() const { return &iter->data; }

        // Aithmetic operations
        iterator& operator ++() { if (iter) iter = iter->next; return *this;  }
        iterator operator ++(int) { iterator temp{ *this }; ++* this; return temp; }
        iterator operator +(const difference_type& n) const { iterator temp{ *this };  difference_type k{ n }; while (k--)++temp; return temp; }
        iterator& operator +=(const difference_type& n) { difference_type k{ n }; while (k--)++* this; return *this; };

        // Comparison
        bool operator != (const iterator& other) const { return iter != other.iter; }
        bool operator == (const iterator& other) const { return iter == other.iter; }
        bool operator < (const iterator& other) const { return iter < other.iter; }
        bool operator > (const iterator& other) const { return iter > other.iter; }
        bool operator <= (const iterator& other) const { return iter <= other.iter; }
        bool operator >= (const iterator& other) const { return iter >= other.iter; }

        // Difference. Also complicated, because no random access
        difference_type operator-(const iterator& other) const {
            difference_type result{};
            Node* n{ iter }; 
            while (n and n != other.iter) { 
                ++result; 
                n = n->next; 
            } 
            return result;
        }
    };

    // Begin and end function to initialize an iterator
    iterator begin() const { return iterator(head); }
    iterator end() const { return iterator(); }
    
    // Functions typcical for forward lists ----------------------------------------------------------------------
    // Easy, becuase we can operate form the current iterator and do not need the "previous" element
    iterator insertAfter(iterator& pos, const int i) {
        iterator result{};
        if (pos.iter and pos.iter->next) {
            Node* n = new Node(i, pos.iter->next);
            pos.iter->next = n;
            result = n;
        }
        return result;
    }
    iterator eraseAfter(iterator& pos) {
        iterator result{};
        if (pos.iter and pos.iter->next) {
            Node* tmp = pos.iter->next->next;
            delete pos.iter->next;
            pos.iter->next = tmp;
            result = pos.iter->next;
        }
        return result;
    }
};
// Test/Driver Code
int main() {

    // Example for initilizer list
    SinglyLinkedList sllbase{5,6,7,8,9,10,11,12,13,14,15};
    // Show move constructor
    SinglyLinkedList sll(std::move(sllbase));

    // Add some values in the front
    sll.push_front(4);
    sll.push_front(3);
    sll.push_front(2);
    sll.push_front(1);

    // Delete 1st element (Number 1)
    sll.pop_front();
    // Delete last element
    sll.pop_back();

    // Use a std::algorithm on our custom linked list. Works because we have an interator
    SinglyLinkedList::iterator iter = std::find(sll.begin(), sll.end(), 8);

    // Now add an element after 8
    iter = sll.insertAfter(iter,88);
    // End delete the 9
    iter = sll.eraseAfter(iter);

    // Use range based for loop. Works because, we have iterators
    for (int i : sll)
        std::cout << i << ' ';
}

Answer 2

Take it easy. I read your code and there are no errors in logic. However, there are some mistakes in the selection of parameters. It is not necessary to use ** in the insert. Using * can meet the requirements, and use & to achieve assignment to the linked list. The same is true for deleteFront and deleteEnd. I modified your code and now the program can run normally, hope it helps.

#include<iostream>
using namespace std;
struct Node {
    int data;
    Node* next;
};

void insert(Node*& head, int n) //insertion method
{
    Node* newNode = new Node;
    newNode->data = n;
    newNode->next = head;
    head = newNode;
}

Node* deleteFront(struct Node*& head)//deleting first node in the list
{
    if (head == NULL)
        return NULL;
    else
    {
        Node* t = head;
        head = head->next;
        free(t);
        t = NULL;
    }

    return head;
}

Node* deleteEnd(struct Node*& head)//deleting last node in the list
{
    if (head == NULL)
        return NULL;
    else if (head->next == NULL) {
        free(head);
        head = NULL;
    }
    else {
        Node* prev = head;
        Node* prev2 = head;

        while (prev->next != NULL)
        {
            prev2 = prev;
            prev = prev->next;
        }

        prev2->next = NULL;
        free(prev);
        prev = NULL;
    }

    return head;
}

void printLL(Node* h)
{
    while (h != NULL)
    {
        cout << h->data << " ";
        h = h->next;
    }

    cout << endl;
}

int main()
{
    cout << "Linked list question 2: " << endl;
    //linked list question 2
    Node* n = NULL;
    
    insert(n, 60);
    insert(n, 40);
    insert(n, 20);
    printLL(n);

    deleteFront(n);
    cout << "after deleting first node: ";
    printLL(n);

    deleteEnd(n);
    cout << "after deleting last element: ";
    printLL(n);
}

Answer 3

Since you're returning head in deleteFront(n) and deleteLast(n), however you're not updating head in main(). That's why its n is pointing to some garbage memory. Update your main() by storing head in n variable.

int main()
{
    cout << "Linked list question 2: " << endl;
    //linked list question 2
    Node* n = NULL;
    insert(&n, 60);
    insert(&n, 40);
    insert(&n, 20);
    printLL(n);

    n = deleteFront(n);
    cout << "after deleting first node: ";
    printLL(n);

    n = deleteEnd(n);
    cout << "after deleting last element: ";
    printLL(n);

}