0

I've been trying to write my own implementation of linked list, but the code segfaults when I try to access an the third element or anything after it. Adding elements doesn't segfault, but accessing does. I can't find the pointer error in my get() function.

Each node in the list stores data (of Template t) and a pointer leading to the next node. I have two functions for everything- one for the first element, and one for any subsequent elements. The get() function for the subsequent elements always segfaults. I have some debug messages in the function that spit out results I can't explain. For example, if I run a get() request for the second element, an then the third, the code doesn't segfault, but it does return clearly incorrect results. Debug messages I placed indicate the segfault occurs when the second element calls the function to check the third element, if it occurs at all. Try the code with and without the line cout << newList.get(2) << endl; and you'll get very different results.

One possible cause is the pointer storage- I have the get() function output the pointer of each element (except the first) as it cycles through, and compare them to the pointers outputted by the add() function, and and pointers for element 0 and 1 match, but 2 and beyond do not match, and I can't seem to figure out why that would be.

#include <iostream>
using namespace std;



template <class T> class myLinkedList{
T data;
myLinkedList<T> *next = NULL;

public:
    myLinkedList(T input){
        data = input;

    }
    void add(T input){
        if(next == NULL){
            myLinkedList<T> newItem(input);
            next = &newItem;
            cout << "adding to list, data is " << input << ", pointer is " << next << endl;
        }else{
            myLinkedList<T> nextEntry = *next;
            nextEntry.add(input);
        }
    }


    T getData(){
        return data;
    }
    //the start  of the get function, only used by the first entry in the list
    T get(int entry){
        int currentPosition = 0;
        if(entry == currentPosition){
            return getData();
        }else{
            //defrefrence the pointer anc check the next entry
            myLinkedList<T> nextEntry = *next;
           return nextEntry.get(entry, ++currentPosition);
        }
    }

private:
    //this vesion is the hidden, private vesion only used by nodes other than the first one
    //used to keep track of position in the list
    T get(int entry, int currentPosition){
        //cout << currentPosition << endl;
        if(entry == currentPosition){
            return data;
        }else{
            //derefrence the pointer and check the next entry
            cout << next << endl;
            myLinkedList<T> nextEntry = *next;
            currentPosition++;
           T output = nextEntry.get(entry, currentPosition);
           return output;
        }

    }


};
int main(){
myLinkedList<int> newList(3);
newList.add(4);
newList.add(5);
newList.add(7);
newList.add(9);
cout << newList.get(2) << endl;
cout << newList.get(3) << endl;
return 0;
}

Results are clearly erroneous- program should spit oout two macthing sets of pointers, as well as the numbers 5 and 7 ( the list elements)

cpwest
  • 1
  • 1
  • 1
    Before I look at this, I'm going to point out the two best ways to figure out linked list problems. 1) Draw pictures of what the list has to look like. This often suggests how to write the code and when you have a bug, follow your instructions to modify the drawing. If you find yourself drawing something silly, you just found a bug. – user4581301 Dec 29 '18 at 03:00
  • 2) Use whatever debugger comes with your development environment. A debugger allows you to execute the program on your terms. You can advance the program with whatever granularity you want and investigate the variables as you go. If you spot the program doing something unexpected, you just found a bug (or an error in your expectations. You'll need to fix that, too). Debuggers are an essential tool for the working programmer. They are likely the best productivity tool this side of the compiler, so the sooner you get a handle on them, the sooner you reap the rewards. – user4581301 Dec 29 '18 at 03:02
  • 3
    A bug (probably the bug) in `add`, `myLinkedList newItem(input);` declares a local variable, This is an automatic allocation that will be destroyed when it goes out of scope (the program reaches the enclosing close brace). Storing a pointer to this is not useful to you because the data pointed at is gone almost immediately leaving the program with a dangling pointer. – user4581301 Dec 29 '18 at 03:07
  • 1
    Funny, I can't find where you are *allocating* storage for each new node? Am I missing it? – David C. Rankin Dec 29 '18 at 03:09
  • Is the linked list supposed to own the objects it links (and manage their lifetimes) or not? – David Schwartz Dec 29 '18 at 03:13
  • This is one of the reasons the use of bare pointers is discouraged in idiomatic C++. Learn how to use `std::unique_ptr` and `std::shared_ptr`. – Richard Dec 29 '18 at 03:27
  • *I've been trying to write my own implementation of linked list* -- I hate to be the one to throw cold water on this, but -- good luck with this. I have yet to see a non-experienced C++ programmer write a linked list class with no bugs, no memory leaks, etc, unless they get a lot of help from an experienced C++ programmer. – PaulMcKenzie Dec 29 '18 at 03:52
  • Possible duplicate of https://stackoverflow.com/questions/6441218/can-a-local-variables-memory-be-accessed-outside-its-scope – Galik Dec 29 '18 at 04:02
  • I may be in the minority, but I think implementing a linked list -- with simple pointers -- is an excellent exercise. Yes, you will make mistakes, that's how you learn. When you get it working, you will understand pointers and memory allocation. *Then* you can ue `std::list`. – Beta Dec 29 '18 at 19:42

2 Answers2

4

One of your main problems is here:

if(next == NULL){
    myLinkedList<T> newItem(input); // <<<<<<<<<<<<<
    next = &newItem;
    cout << "adding to list, data is " << input << ", pointer is " << next << endl;
}

you allocate an item on stack inside the if scope. Then you make next to point to this item. But... lifetime of the item is bounded by this scope. As son as you exit the scope, this item does not exist any longer. You need to allocate it dynamically by 'new' or other methods.

Serge
  • 11,616
  • 3
  • 18
  • 28
  • Trying to allocate memory with new (myLinkedList newItem = new myLinkedList(input);) leads to some puzzling compile time errors LinkedListTest.cpp:15:33: error: invalid conversion from ‘myLinkedList*’ to ‘int’ [-fpermissive] Basically, calling the add function in main causes some pointer issue myLinkedList newItem = new myLinkedList(input); – cpwest Dec 30 '18 at 04:53
  • `myLinkedList *newItem = new myLinkedList(input);` -- you need to declare a pointer in such a case. – Serge Dec 30 '18 at 14:54
0

I had a breakthrough! Following Serge's solution was helpful, but one more change was needed- rather than create a function reference in the else block of my add function, eg

 myLinkedList<T> nextEntry = *next;
 nextEntry.add(input)

i needed to use the pointer directly, as in

next->add(input)

I didn't know my pointer/object syntax

cpwest
  • 1
  • 1