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);
}
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.