Linked list only printing out data of three of the nodes

[vaderboi]

I am trying to fill a list with integers that range from 1 to N. When I try to print out every element in the list, the console repetitively prints out "Index: 1, Data: 1; Index: 99, Data: 99; Index: 100, Data: 100" 33 times and then ends with "Index: 1, Data: 1". I had the program, within void hotPotatoGame::fillList(int numberOfIntegers) within the while loop in the header file, print the current index value and the console out every integer from 1 to 100. Because of this I know that the while loop iterated 100 times.

I just am unsure why it seems like the no new node was ever created or pointed to. I have looked over my doubly linked list and I am confused as to what I did incorrectly. Can anyone tell me what is going on here?

exercise6version4.h

#ifndef EXERCISE6VERSION4_H
#define EXERCISE6VERSION4_H

/*TO DOS:
 * 1) **********DONE***********
 *     constructor
 *    - number of passes
 *    - number of elements
 *    - creates an entire linked 
list using the fillList() function
 *    - defines initial head 
and tail values
 * 2) fillList() function
 * 3) findIntendedInteger() which uses
 * modulo arithmetic to pinpoint how many
 * passes need to be made from 
the index you are at either backwards 
or forwards to delete a specific value 
( essentially whatever will save time )
 * (this may need to be discarded as an 
idea if it takes up too much time)
 * 4) hotPotatoLoop() function
 *    - use findIntendedInteger if the number
 of passes exceeds the number of elements
 *    - otherwise, just iterate through 
the list normally*/

class hotPotatoGame
{
	public:
		hotPotatoGame( int N, int M );
		void fillList( int numOfIntegers );
		//void hotPotatoLoop();
		//int findIntendedInteger();
		void printList();


	private:
		int numOfElements;
		int numOfPasses;
		struct Node
		{
			int data;
			Node *prev;
			Node *next;
			int currentIndex;
		};
		Node *head;
		Node *tail;
};




#endif 

exercise6version4.cpp

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

hotPotatoGame::hotPotatoGame( int N, int M )
{
	numOfElements = N;
	numOfPasses = M;
	head = new Node;
	tail = new Node;

	head->prev = tail;
	head->next = tail;
	head->data = 0;
	head->currentIndex = 1;

	tail->prev = head;
	tail->next = head;
	tail->data = 0;
	head->currentIndex = 0;

	fillList( numOfElements );
}

void hotPotatoGame::fillList( int numberOfIntegers )
{
	Node *traversalNode = new Node;
	traversalNode = head;

	Node *newNode = new Node;
	Node *previousNode = new Node;

	int index = 1;

	/*TO DO: figure out how to make it 
	 * so that while loop stops before 
	 * the tail so that the second to last
	 * node can be linked to it*/
	while( index <= numberOfIntegers )
	{
		/*if-condition points to tail if 
		 * it is the head. Otherwise, it
		 * points to whatever the last
		 * generic Node is*/
		if( traversalNode == head )
		{
			traversalNode->prev = tail;
		}
		else
		{
			traversalNode->prev = previousNode;
		}
		
                previousNode = traversalNode;
		traversalNode->data = index;
		traversalNode->currentIndex = index;

		/*if-condition points to a generic
		 * new Node unless the index is equal
		 * to one less than the number of elements or
		 * equal to the number of elements. If it is
		 * one less than the number of elements then
		 * the current Node points to the tail. If
		 * it is equal to the number of elements then
		 * the current Node points to the head*/
	        if( index == numberOfIntegers - 1 )
		{
			traversalNode->next = tail;
			traversalNode = tail;
		}
		else if( index == numberOfIntegers )
		{
			traversalNode->next = head;
		}
		else
		{
			traversalNode->next = newNode;
			traversalNode = newNode;
			/*ensures that newNode->next points to tail and that
			 * tail->prev points to newNode so as to put tail perpetually
			 * at the end of the list*/
			newNode->next = tail;
			newNode->next->prev = newNode;
			
		}

		/*creates a "previous node" so that it can be pointed
		to in the next iteration of the while loop*/
	        previousNode = traversalNode;	
		std::cout << "Index: " << index << " ";
		++index;
	}
}

void hotPotatoGame::printList()
{
	int index = 1;
	Node *printNode = new Node;
	printNode = head;

	while( index <= numOfElements )
	{
		std::cout << "Index: " << 
printNode->currentIndex << ", Data: " << printNode->data << "; ";
		printNode = printNode->next;
		++index;

	}

	std::cout << '\n';
}

main.cpp

include "exercise6version4.h"
#include <iostream>


int main()
{
	hotPotatoGame potatoGame( 100, 0 );

	potatoGame.printList();


	return 0;
}

[lastchance]

You have a large number of memory leaks.

	Node *traversalNode = new Node;
	traversalNode = head;

	Node *newNode = new Node;
	Node *previousNode = new Node;

The first line accesses new, anonymous, memory space via a pointer ... then loses all access to that memory space by pointing elsewhere. I suspect you meant
Node *traversalNode = head;
but who knows? You don't need a 'new' every time you declare another pointer! Your code suggests that you are under a misapprehension here. That pointer is only required to point to a pre-existing memory location. (I personally prefer the terminology that other languages use: "allocate" rather than "new", to convey the fact that it is used only where extra memory is needed to store something.)

The third and fourth lines also (unnecessarily) create new memory slots via pointers ... but, again, all access to those memory slots is lost later, because the pointers are redirected elsewhere. Maybe you meant something like

Node *nextNode = traversalNode->next;
Node *previousNode = traversalNode->prev;

You could - but don't - make any use of these pointers later.

I don't think you help yourself by calling a variable newNode; one stray blank in the middle ...

In your code snippet

	head->currentIndex = 1;

	tail->prev = head;
	tail->next = head;
	tail->data = 0;
	head->currentIndex = 0;

you are assigning head->currentIndex twice, whilst poor old tail->currentIndex is forgotten.


You don't usually traverse linked lists by counting indices - you usually end when the next pointer is a nullptr.


May I suggest that, to get better help in the forum you:
- combine into a single file, so that it can be run immediately in cpp.sh; you can split it between files LATER if really necessary;
- remove all the extra comments and blank lines, which are confusing and distracting;
- sit down with a piece of paper and draw boxes for each anonymous piece of memory that is accessed with a 'new' statement, making sure that it is permanently pointed to by something (until 'delete'd).

Linked lists are definitely better understood when their operations are drawn out with diagrams.

You can definitely use this forum as an educational resource - typing "doubly linked list" into the search box will pull up many previous posts, and you can observe how linked lists have been built and traversed.

[dhayden]

I'm going to assume that you're using a doubly linked list because the game requires you to go around the loop and occasionally remove individual items from the list.

You should code some basic list functions as private members: insertBefore and/or insertAfter, remove, etc.

It looks like you're coding two sentinel items at the head and tail. This will probably trip you up. When you're going around the list, you'll have to skip these two right? It would probably be better to code it so that an empty list has head == tail == nullptr.

Lots of people come here looking for help with doubly linked lists. A great number of the problems fall into two categories:
1. They forget to update the tail pointer.
2. They forget to update the prev pointer.

Basically, anywhere that you find yourself updating head, consider whether there is a similar case that requires updating tail. Same with the next pointer. If you have to update a next pointer, then you probably have to update a prev pointer too.

[vaderboi]

I meant to thank you both for the help. I haven't been able to return this problem since I posted here since I got really stuck and discouraged. I need to understand nodes better before I think I can ask about them but both of your comments steered me in the right direction.