3

I am trying to code a linked list in C++, but I am running into a problem. When I insert only one item, it works, but when I insert more than one, it goes into an infinite loop. Here is the code:

#include "linkedList.hpp"
#include <iostream>

linkedList::node::node(int value)
{
    internalValue = value;
    next = nullptr;
    previous = nullptr;
};

linkedList::linkedList()
: header{node(-2)}, trailer{node(-2)}
{
    trailer.previous = &header;
    header.next = &trailer;
    size = 0;
}

int linkedList::getLength()
{
    return size;
}

void linkedList::appendElement(int value)
{

    node newNode = node(value);
    newNode.next = &trailer;
    newNode.previous = trailer.previous;
    (trailer.previous)->next = &newNode;
    trailer.previous = &newNode;
    size = size + 1;
}

void linkedList::print()
{
    node * current = header.next;
    while (current -> next != nullptr)
    {
        std::cout << current -> internalValue << "->" << "\n";
        current = current->next;
    }
    std::cout << "v";
}

After trying to debug it, I found that the issue is with the construction of a node. So the first time I try to insert 5, the program creates a node called new node, which is then appended perfectly fine.

What happens next is when a second number is to be appended, lets say 6, the program doesn't really create a new node object. Rather the variable name "newNode" still refers to the node with the value 5 stored in it and it replaces it with a node with the value of 6.

This understandably then creates an infinite loop since it essentially makes the array circular. I don't know how to fix this. Can someone point me in the right direction?

PS: sorry if this is extremely simple, I am very new to C++ (this is only my second day of coding)

Toby
  • 9,696
  • 16
  • 68
  • 132
Abid Rizvi
  • 439
  • 1
  • 5
  • 11
  • 1
    `(trailer.previous)->next = &newNode; trailer.previous = &newNode;` looks suspicious.Why the same node would be both next of previous and previous? – Jean-François Fabre Dec 02 '16 at 09:51
  • I believe that trailer.previous -> get the "next" data field from the node ahead of the trailer. I then set that equal to the new node . I think it basically turns the arrow pointing from the node ahead of trailer to point to the new node. The next part turn the arrow pointing from trailer to the original node to point from the trailer to the new node. – Abid Rizvi Dec 02 '16 at 09:55
  • @Jean-FrançoisFabre: It's usually correct. In a double-linked list, `&newNode` must appear once as `.next` and once as `.previous`, **unless** it's an insertion at the begin or end of the list. – MSalters Dec 02 '16 at 09:59

1 Answers1

3

In linkedList::appendElement(int value) you create a new node on the stack ( or 'automatic storage' ), which means the node will be destroyed when the function returns.

Instead, create the node on the heap ( or 'dynamic storage' ) using the new operator so it is not destroyed when the function returns.

node* newNode = new node(value);

You will also have to remember to destroy nodes yourself when the list is destroyed or truncated, and most C++ developers soon find it better to use smart pointers for that.

Community
  • 1
  • 1
Pete Kirkham
  • 48,893
  • 5
  • 92
  • 171
  • the`newNode` scrambled my vision, I thought a `new` was being done :) Pedantic ones will say that auto variables is not necessarily the stack. It's implementation dependent. – Jean-François Fabre Dec 02 '16 at 09:57
  • thanks for replying. A quick follow up question, I thought we would want the node to be destroyed. Isn't its presence staying behind the problem, or am I thinking about this wrong? – Abid Rizvi Dec 02 '16 at 10:00
  • @AbidRizvi: The problem for you is not _whether_ you want the node deleted, but _when_. Since you're using `new` and dumb pointers, that's entirely your responsibility. – MSalters Dec 02 '16 at 10:01
  • Ok, I think I understand. If not, greater understanding should come with more experience. One more thing I don't understand, why do you have node *? aren't we creating a node type object, not a pointer to a node? – Abid Rizvi Dec 02 '16 at 10:07
  • Operator new creates the object and returns a pointer to it, so you need a pointer variable to store the result. – Pete Kirkham Dec 02 '16 at 10:08