circular linked list (insert at beginning)

Question

This is my code. A circular linked list has two functions, one to insert at the beginning and the other to insert at end. When I run it, it works, but there is an error that it doesn't display the last node, i think because head=p; not head->next=p; but if I do head->next=p; it is a segmentation error How can I fix this fault?

#include <iostream>
using namespace std;

struct node {
    int info;
    node* next;
};

node* head = NULL;

void insert_b(int data) {
    node* p = new node; //create
    p->info = data; //fill
    if (head == NULL) {
        head=p;
        p->next = head;
        
    }
    else {
        p->next = head->next;
        head->next = p;
    }


void traverse() {
    node* curr = NULL;
    for (curr = head->next; curr != head; curr = curr->next) {
        cout << curr->info << "  ";
    }
}

int main() {
    int data;
    cout << "enter data: ";
    cin >> data;
    insert_b(7);
    insert_b(2);
    insert_b(1);
    traverse();

    return 0;
}

`if(head==NULL)` + `head->next=p;` ==> crash. I think correct is `if (head==NULL) head=p;` — mch, Sep 14 '22 at 13:25
Work it out by drawing boxes and arrows using pen and paper first. — molbdnilo, Sep 14 '22 at 13:46
Dupe1: [Why dereferencing a null pointer is undefined behaviour?](https://stackoverflow.com/questions/6793262/why-dereferencing-a-null-pointer-is-undefined-behaviour) , Dupe2:[dereferencing the null pointer](https://stackoverflow.com/questions/2896689/dereferencing-the-null-pointer) — Jason, Sep 14 '22 at 14:11
Your next step should be to determine the line at which the crash occurs, then find the values of each variable used on that line. A debugger is very helpful for this. — JaMiT, Sep 14 '22 at 14:16
Sorry, I misread the question yesterday. I somehow missed the whole "circular" part (although it's clearly stated in the question more than once). I've now updated my answer to deal with that. — Ted Lyngmo, Sep 15 '22 at 15:37

Ted Lyngmo · Answer 1 · 2022-09-15T16:03:51.503

The logic in insert_b is flawed. if head == NULL you can't dereference it like you do in head->next = p.

You have a similar issue in traverse where you go directly for head->next. First check that head is != nullptr then start by printing. Check if curr reaches head, then break out.

Fixing the logic in insert_b is a bit tricky since it's a circular list. For both insert_b and insert_t you want to insert the new node between the last element and the first element, so you need to traverse the linked list until you find that last node*. For insert_b you also want to move head so that it points at the newly inserted node.

Since the logic is so similar, I suggest creating a common function that can be used for both. This would be the insert_t function:

node* insert_t(int data) {
    node* p = new node;  // or:
    p->info = data;      // node* p = new node{data, nullptr};

    if (head) { // there is at least one node
        node* curr = head;
        // find the last node:
        while(curr->next != head) curr = curr->next;
        // link in the new node between the last node and head
        p->next = head;
        curr->next = p;
    } else { // first node - let it point at itself
        p->next = p;
        head = p;
    }
    return p;
}

The above links the new node in last in the circular linked list and returns a pointer to the inserted node. In order to implement insert_b we only need to call insert_t and move head:

void insert_b(int data) {
    // move head to point at the newly inserted node
    head = insert_t(data);
}

The corrected loop needs to check that head != nullptr first, then print the value of the current node, step to the next - and abort if it's coming back to head:

void traverse() {
    if (head) {
        node* curr = head;
        do {
            std::cout << curr->info << "  ";
            curr = curr->next;
        } while(curr != head);
        std::cout << '\n';
    }
}

circular linked list (insert at beginning)

1 Answers1