Doubly Linked List Implementation with Pointers C++

Alex Barry picture Alex Barry · Oct 21, 2013 · Viewed 36.8k times · Source

I am currently teaching myself C++ and am attempting to implement a doubly-linked list in C++ using pointers which is partially complete. I am aware that the code currently fails to deal with dangling nodes or output errors, both of which I will implement next. However, the code should atleast be able to construct a list object and add elements to it. Currently, I am getting an error when I attempt to call a constructor for the list, which says that I am requesting a conversion from LinkedList* to non scalar type LinkedList. Why is my list being declared as a pointer? Any help would be much appreciated, thank you!

LinkedList.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

struct dataElement {
  int key;
  int id;
};

struct Node
{
    dataElement data;
    Node* next;
    Node* prev;
};


class LinkedList
{
public:
    /** Default constructor */
    LinkedList();
    /** Default destructor */
    virtual ~LinkedList();
    void addAtFront(int newElement);
    void addAtBack(int newElement);
    int removeTop();
    int removeBottom();
    int getTop();
    int getBottom();
    int findKey(int keyToFind);
protected:
private:
    Node* head;
    Node* tail;
    int size;
};

#endif // LINKEDLIST_H


LinkedList.cpp
#include "LinkedList.h"
#include <iostream>
#include <stdlib.h>


LinkedList::LinkedList()
{
size = 0;
}

LinkedList::~LinkedList()
{
//dtor
}

void LinkedList::addAtFront(int newElement)
{
if (size == 0)
{
    Node temp;
    temp.data.id = newElement;
    temp.data.key = 0;
    head = &temp;
    tail = &temp;
    ++size;
}
else
{
    Node temp;
    temp.data.id = newElement;
    temp.data.key = size;
    temp.next = head;
    head->prev = &temp;
    head = &temp;
    ++size;
}
}

void LinkedList::addAtBack(int newElement)
{
if (size == 0)
{
    Node temp;
    temp.data.id = newElement;
    temp.data.key = 0;
    head = &temp;
    tail = &temp;
    ++size;
}
else
{
    Node temp;
    temp.data.id = newElement;
    temp.data.key = 0;
    tail->next = &temp;
    temp.prev = tail;
    tail = &temp;
    ++size;
}
}

LinkedListTest.cpp
#include "LinkedListTest.h"
#include "LinkedList.h"

int main()
{
LinkedList list = new LinkedList();
list.addAtFront(0);
}

Answer

Jack picture Jack · Oct 21, 2013

The error means that somewhere you have a LinkedList list declared not as a pointer, to which you assign a new LinkedList() which is of type LinkedList* (and not LinkedList). It should be:

LinkedList* list = new LinkedList(); // I declare a pointer to a list
list->addAtFront(0); // I call a method on a pointer to an object

or

LinkedList list;
list.addAtFront(0);

They are two different types which are allocated in two different storages and this is important, keep reading.

What I see more importantly is that when you use dynamically allocated memory you should take case of actually allocate on heap objects that should persist the scope in which they are declared.

More specifically, this:

{
  Node temp;
  ..
  head = &temp;
  ..
}

This will cause problems because temp is declared as automatic storage on stack, which means that once you obtained its address and assign it to head or tail or whatever, that address won't be valid anymore once the scope exited. You should allocate it on heap:

Node temp = new Node(value, id);
head = temp;
tail = temp;
++size;

Mind that this requires that you clean up memory by yourself from the heap when the Node is not needed anymore.