C++

Forum

 
Having issues with my linear linked list

Spectre216 (8)
I am trying to create both a minimum heap and a linear linked list to store values in order, listing the amount of comparisons that take place in each of them. My program keeps crashing though when inserting values into my linked list. Can someone help point out what I am doing wrong. VS debugger shows that it can't read the info in tempPtr in line 89, but I can't seem to get it working.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
 
  #ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <iostream>

template<class T>
class List
{
private:
	struct ListNode
	{
		ListNode* nextNode;
		T value;
	};

	ListNode* head;
	int length,
	    maxLength,
	    compares;

public:
	List();
	List(int);
	~List();

	void insertNode(T);
	void	deleteNode(T);
	T getNodeValue(int);
};

template<class T>
List<T>::List()
{
	length = 0;
	maxLength = 100;
	head = NULL;
	compares = 0;
}

template<class T>
List<T>::List(int max)
{
	length = 0;
	maxLength = max;
	head = NULL;
	compares = 0;
}

template<class T>
List<T>::~List()
{
	ListNode* deleteNode;
	ListNode* tempPtr;

	tempPtr = head;

	while (tempPtr != NULL)
	{
		deleteNode = tempPtr;
		tempPtr = tempPtr->nextNode;
		delete deleteNode;
	}

	head = NULL;
}

template<class T>
void List<T>::insertNode(T newValue)
{
	ListNode* tempPtr;
	ListNode* newNode;

	if (length == maxLength)
	{
		std::cout << "You must delete an item before a new item can be entered.\n";
	}
	else
	{
		newNode = new ListNode;
		newNode->value = newValue;

		if (head == NULL)
		{
			head = newNode;
		}
		else
		{
			tempPtr = head;

			while (tempPtr != NULL && tempPtr->value < newValue)
			{
				tempPtr = tempPtr->nextNode;
				compares++;
			}

			newNode->nextNode = tempPtr->nextNode;
			tempPtr->nextNode = newNode;
		}
	}
}

template<class T>
void List<T>::deleteNode(T value)
{
	ListNode* tempPtr;
	ListNode* deletePtr;

	tempPtr = head;

	if (tempPtr != NULL)
	{
		std::cout << "There are no values in this list.\n";
	}

	while (tempPtr != NULL && tempPtr->nextNode->value != value)
	{
		tempPtr = tempPtr->nextNode;
	}

	if (tempPtr != NULL)
	{
		deletePtr = tempPtr->nextNode;
		tempPtr->next = tempPtr->nextNode->nextNode;
		delete deletePtr;
	}
	else
	{
		std::cout << "That value is not in the list.\n";
	}

}

template<class T>
T List<T>::getNodeValue(int position)
{
	ListNode* tempPtr;
	int count = 0;

	tempPtr = head;

	while (count < position && tempPtr != NULL)
	{
		tempPtr = tempPtr->nextNode;
		count++;
	}

	if (tempPtr != NULL)
	{
		return tempPtr->value;
	}
	else
	{
		cout << "There are not that many nodes in the list.\n";
	}
}

#endif
Lowest0ne (1536)
It is possible for tempPtr to be null at line 95 and you are dereferencing it.
Spectre216 (8)
Ok I got it to stop crashing, but now it doesn't store the numbers right. Did I mess something up in my loop to compare the values?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
 
template<class T>
void List<T>::insertNode(T newValue)
{
    ListNode* newNode;      //Pointer for the new node.
    ListNode* nodePtr;      //Pointer to traverse the list.


    //Allocates a new node and stores newValue in it.
    newNode = new ListNode;
    newNode->value = newValue;
    newNode->nextNode = NULL;

    //If there are no nodes, the new node will be made the first one in the list.
    if (!head)
    {
        head = newNode;
    }

    //Otherwise the program will loop to the list's end and add the node.
    else
    {
        //Starts at the list's head.
        nodePtr = head;

        //Loops through the list looking for the end.
        while (nodePtr->nextNode && newValue >= nodePtr->value)
            nodePtr = nodePtr->nextNode;

        //Adds the node.
        nodePtr->nextNode = newNode;

	   //Increment length.
	   length++;
    }
}
Lowest0ne (1536)
The while loop at line 26 looks correct, go until the end of the list or the new value is less than the current value.

However, your addition of the node ( line 30 ) does not connect the new node's next to the nodePtr's next. Line 95 and line 96 of your old code is needed.

nodePtr is certain to exist, so nothing fancy is needed:
1
2
 
newNode->nextNode = nodePtr->nextNode; // fine if nodePtr->nextNode == 0
nodePtr->nextNode = newNode;
Spectre216 (8)
Ok, I see where I went wrong with that. However, the list is supposed to be stored in order (smallest to highest), which I though that my newValue >= nodePtr->value (line 26) would make sure of that, but it isn't storing them in that order. Did I mess up the sign or something else?
Spectre216 (8)
Still can't figure this out. Still displaying the values in the wrong order.
Topic archived. No new replies allowed.