Linked List Class

[akhi]

I'm having an issue with some functionality of my C++ Code. The program is suppose to generate 5 random integers, and also delete numbers from the randomly generated list, or that are added to the list. Currently, the program is generating 6 random numbers, and will not delete numbers from the list. Here is my code:

linkedlist.h

/*
* Doubly Linked List Node.
*/

struct Node
{
	int info; //element stored in node
	Node* next; //link to next node
	Node* prev; //link to prev node
};

/*
* Doubly Linked List Class.
*/

class DoublyLinkedList
{
public:
	DoublyLinkedList();
	~DoublyLinkedList();
	bool isEmpty();
	void display();
	void add(int);
	void remove(int);
	void displayInReverse();
	void addEnd(int);

private:
	Node* first; //pointer to dummy header node
	Node* last;
};

------------------------------------------------------------------

linkedlist.cpp

#include <iostream>
#include "DoublyLinkedList.h"

using namespace std;

/*
* Initializes empty list creating dummy header node.
*/

DoublyLinkedList::DoublyLinkedList()
{
	first = new Node;
	last = first;
	first->next = NULL;
	first->prev = NULL;
}

/*
* Destructor.
* Deallocates all the nodes of the linked list, including header node.
*/

DoublyLinkedList::~DoublyLinkedList()
{
	Node* temp;

	while (first != NULL)
	{
		temp = first;
		first = first->next;
		delete temp;
	}
}

/*
* Determines whether the list is empty.
* Returns true if the list is empty, otherwise false.
*/

bool DoublyLinkedList::isEmpty()
{
	return first->next == NULL;
}

/*
* Prints the list elements.
*/

void DoublyLinkedList::display()
{
	Node* current = first;

	while (current != NULL)
	{
		cout << current->info << " ";
		current = current->next;
	}

	cout << endl;
}

/*
* Prints the list elements in reverse.
*/

void DoublyLinkedList::displayInReverse()
{
	Node* current = last;

	while (current != NULL)
	{
		cout << current->info << " ";
		current = current->prev;
	}

	cout << endl;
}

/*
* Adds element x to beginning of list.
* x: element to be added to list.
*/

void DoublyLinkedList::add(int x)
{
	Node* p = new Node;

	p->info = x;
	p->next = first;
	p->prev = NULL;

	first->prev = p;
	first = p;
}

/*
* Adds element x to end of list.
* x: element to be added to list.
*/

void DoublyLinkedList::addEnd(int x)
{
	Node* p = new Node;

	p->info = x;
	p->next = NULL;
	p->prev = last;
	last->next = p;
	last = p;
}

/*
* Removes the first occurance of x from list.
* If x is not found, the list remains unchanged.
*
* x: element to be added to list.
*/

void DoublyLinkedList::remove(int x)
{
	Node* old = first->next,
		* p = first;

	//Finding the address of the node before the one to be deleted
	bool found = false;

	while (old != NULL && !found)
	{
		if (old->info == x) found = true;

		else
		{
			p = old;
			old = p->next;
		}

	}

	//If x is in list, remove it.
	if (found)
	{
		p->next = old->next;
		old->next->prev = old-> prev;
		delete old;
		//delete p;
	}
}

---------------------------------------------------------

main.cpp

#include <iostream>
#include "DoublyLinkedList.h"

using namespace std;

int main()
{
    DoublyLinkedList myList;

    int x;

    //Adds 5 random numbers to the list

    for (int i = 0; i < 5; i++)
        myList.add(rand() % 5);

    cout << "1. Display the list elements" << endl;

    cout << "2. Is the list empty?" << endl;

    cout << "3. Add element at beginning of list" << endl;

    cout << "4. Delete element" << endl;

    cout << "5. Display list in reverse" << endl;

    cout << "6. Add element at end of list" << endl;

    cout << "7. Exit" << endl;

    int option;

    //Loop to test the LinkedList class methods

    do
    {
        cout << endl << "Enter your choice: ";

        cin >> option;

        switch (option)
        {
        case 1:
            cout << "List elements: ";
            myList.display();
            break;

        case 2:
            if (myList.isEmpty()) cout << "List is empty" << endl;
            else cout << "List is not empty" << endl;
            break;

        case 3:
            cout << "Enter an element to add at beginning of list: ";
            cin >> x;
            myList.add(x);
            break;

        case 4:
            cout << "Enter an element to delete from the list: ";
            cin >> x;
            myList.remove(x);
            break;

        case 5:
            cout << "Display in reverse: " << endl;
            myList.displayInReverse();
            break;

        case 6:
            cout << "Enter an element to add at end of list: " << endl;
            cin >> x;
            myList.addEnd(x);
            break;

        case 7:
            cout << "Exit" << endl;
            break;

        default: cout << "Invalid Choice!" << endl;
        }
    } while (option != 7);

    return 0;
}

[dutch]

You're not dealing with your dummy node properly.

[akhi]

Can you be a little more specific and show me what I'm doing incorrectly?

[salem c]

You could try it without the dummy node.

What you've basically traded is making your life 'easy' in the one-off case of adding nodes to an empty list, for making your life 'hard' in every other branch of the code which now has to deal with a dummy node.

[dhayden]

I wouldn't use the dummy node unless you're required to. Here are comments on your current code. As you'll see, it's probably easier to remove the dummy node from your code than it is to keep it.

display() shows the dummy node. Also, consider using a for loop. The code will be clearer:

void DoublyLinkedList::display()
{
	for (Node* current = first->next; current; current = current->next) {
		cout << current->info << " ";
	}
	cout << endl;
}

displayInReverse() will also display the dummy node.

add() inserts before the dummy node. Also it should update last when inserting into an empty list

remove() should take advantage of the dummy node.
remove() needs to update last if it removes the last node.

[dutch]

Can you be a little more specific and show me what I'm doing incorrectly?

You're the one using the dummy node.
Figure it out.
Like, you know, maybe don't print it.
Stuff like that.

[ne555]

circular list with dummy node, then you never have to worry about invalid pointers.
also last == dummy->prev->prev

[akhi]

@dhayden - thanks for your help.

is there a reason why i'm getting such a high negative integer count when I display my list?
for instance the list, in this example, displays 0 14 7 1 -842150451

what am i doing wrong for the random integer to display -842150451

can you show me how to correct this?

[ne555]

¿did you change the code?
that may be an uninitialised variable

[dhayden]

Post your updated code. Otherwise the answer is all the stuff you've already been told.

BTW, I really like ne555's idea. If you're going to use a dummy node, then make the list circular.

[akhi]

Thanks for everyone's help while I worked through my troubleshooting. I've updated my code in two ways: first i updated my initialize-rs, then i updated my dummy node--these are my changes, the code is now running properly.

DoublyLinkedList::DoublyLinkedList()
{
	first = new Node;
	first->next = NULL;
	first->prev = NULL;
	last = first;
	first->info = NULL;
}

void DoublyLinkedList::display()
{
	struct Node* ptr;
	ptr = first;
	
	while (ptr != NULL)
	{
		cout << ptr->info << " ";
		ptr = ptr->next;
	}
	
	cout << endl;
}