C++ linked list help (pointers)?

Question

template <typename T> class LinkedNode { public: T data; LinkedNode<T> *next; LinkedNode<T> *prev; LinkedNode<T>(); LinkedNode<T>(T); }; // Default constructor template <typename T> LinkedNode<T>::LinkedNode() { next = NULL; prev = NULL; } template <typename T> class LinkedList { private: LinkedNode<T> *head; public: LinkedList<T>(); ~LinkedList<T>(); void addFront(T); void addBack(T); void addAt(T, int); void removeFront(); void removeBack(); void removeAt(int); void printList(); }; // Constructor template <typename T> LinkedList<T>::LinkedList() { head = NULL; } // Add new node to front template <typename T> void LinkedList<T>::addFront(T d) { LinkedNode<T> temp; temp.data = d; if (head == NULL) { head = &temp; } else { temp.next = head; head->prev = &temp; head = &temp; } } // Add new node to back template <typename T> void LinkedList<T>::addBack(T d) { // Find the back of this list LinkedNode<T> *ptr; ptr = head; while (ptr->next != NULL) // <------- DIES HERE, MEMORY ACCESS VIOLATION { ptr = ptr->next; } // Make a new node and join it to the back LinkedNode<T> temp; temp.data = d; temp.prev = ptr; ptr->next = &temp; }

Here is a snippet from my linked list system. The issue is that it throws an error on the indicated line. The debugger says that the "head" pointer is pointing to a legitimate memory address of a LinkedNode with no "next" or "prev", but the "ptr" pointer points to address 0xcccccc, not the address of head? I'm really confused, I thought I understood pointers!

In general, 0xcccccc is the debugger telling you the memory being pointed to is uninitialized garbage. If the debugger is right, since ptr=head is correct, the error is in the loop. ptr became junk after ptr = ptr->next. So somehow there is a mistake in the chain. — VoidStar
– VoidStar, Commented Oct 13, 2011 at 6:38

K-ballo · Accepted Answer · 2011-10-13 05:17:59Z

void LinkedList<T>::addFront(T d) { LinkedNode<T> temp; temp.data = d; ... head = &temp; ... }

temp is a variable of automatic storage, its lifetime will end as soon as the addFront function returns and you will get a pointer to an invalid object. You have to allocate nodes in the heap, do this instead:

 LinkedNode<T>* temp = new LinkedNode<T>; temp->data = d; ... head = temp;

Yes, this is definitely the problem. The heap is the best general way to go, but don't forget to carefully consider how the nodes will be all be deleted in ~LinkedList<T>()!! Make sure not to allow the list to be manipulated such that any nodes become "orphaned" or you will have a memory leak.

Meister Schnitzel · Accepted Answer · 2011-10-13 06:36:07Z

I confirm with the answer from K-ballo. The problem is that the object you add is destroyed when the addFront function leaves its scope. What you have is a list of invalid pointers.

Allocate the elements with new as shown above, but don't forget to clean up when you remove an element from the list (delete the pointer).

Collectives™ on Stack Overflow

C++ linked list help (pointers)?

2 Answers 2

1 Comment

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Related