C++

Forum

 
Linked Lists - Help please!

zCasanova (6)
I can add any amount of values to the initial list and it sorts/prints with no issues. Once I call the print function, I can't go back and add more values to the initial list. 49.0 will not add, but 80.0 will - however, it will not be sorted properly - it will be added to the end of the list.

What am I doing wrong? I'm struggling to wrap my mind around the concept of linked lists, so it's probably something simple.

LIST.H
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
 
#ifndef LIST_H
#define LIST_H

class List
{
	private: // Variables
		
		typedef struct node
		{
			double data;
			node* next;	
		}* nodePtr;
		
		nodePtr head;
		nodePtr curr;
		nodePtr temp;
		
	public: // Functions
		
		// Constructor
		List();
		
		// Adds node
		void AddNode(double addData);
		// Deletes node
		void DeleteNode(double delData);
		// Prints list
		void PrintList();
		
		
};

#endif /* LIST_H */


LIST.CPP
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
 
  #include <cstdlib>
#include <iostream>

#include "List.h"

using namespace std;

// Constructor
List::List()
{
	head = NULL;
	curr = NULL;
	temp = NULL;
}

void List::AddNode(double addData)
{
	nodePtr n = new node;
	
	n->next =  NULL;
	n->data = addData;
	
	if(head != NULL)
	{
		curr = head;
		
		if(head->data > addData)
		{
			temp = head;
			head = n;
			head->next = temp;
			curr = head;
			
			return;
		}
		
		temp = curr;
		
		while(curr->next != NULL)
		{
			if(curr->data < addData)
			{
				temp = curr;
				curr = curr->next;
			}
			else
			{
				temp->next = n;
				n->next = curr;
			}
		}
		
		curr->next = n;	
	}
	else
	{
		head = n;
	}
}

void List::DeleteNode(double delData)
{
	nodePtr delPtr = NULL;
	temp = head;
	curr = head;
	
	while(curr != NULL && curr->data != delData)
	{
		temp = curr;
		curr = curr->next;
	}
	
	if(curr == NULL)
	{
		cout << delData << " was not found!" << endl;
		delete delPtr;
	}
	else
	{
		delPtr = curr;
		curr = curr->next;
		temp->next = curr;
		
		delete delPtr;
		
		cout << "The value " << delData << " has been deleted." << endl;
	}
}

void List::PrintList()
{
	curr = head;
	
	while(curr != NULL)
	{
		cout << curr->data << endl;
		curr = curr->next;
	}
}


MAIN.CPP
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
 
#include <cstdlib>
#include <iostream>
#include "List.h"

using namespace std;

int main()
{
	List Example;
	
	cout << "Initial list:  " << endl << endl;
	
	Example.AddNode(45.0);
	Example.AddNode(49.0);
	Example.AddNode(42.0);
	Example.AddNode(48.0);
	Example.AddNode(52.0);
	Example.AddNode(12.0);
	Example.AddNode(100.0);
	
	Example.PrintList();
	
	cout << "\nList with 49.0 added again:  " << endl << endl;
	
	Example.AddNode(49.0);
	
	Example.PrintList();
	
	return(0);
}
zCasanova (6)
Bump - I'm still trying to understand what's wrong.
bingo1 (31)
Linked lists give me a hell of a time, too. So I tried to run your code, and it just "stopped". Most of the time, this means that the program is stuck in an infinite loop, usually a while-loop.

And it is. It's stuck in the while-loop of addNode().

I've include some cout statements below. Add it to the beginning of the while-loop(before the if-else statements). It allows you to see what everything points to every time that while loop runs. Hope it helps.

1
2
3
4
5
6
7
8
9
 
	cout << "head points to: " << head -> data << endl;
	cout << "head next points to: " << head ->next -> data << endl;
	cout << "curr points to:  " << curr -> data << endl;
	cout << "curr next points to: " << curr ->next -> data << endl;
	cout << "temp points to:  " << temp -> data << endl;
	cout << "temp next points to:  " << temp ->next -> data << endl;
        system("pause");
        system("cls");//This is optional.


You should see how the pointers change(or don't change), causing the while-loop to run forever.
ne555 (10692)
^Or you could simply use a debugger.

You ought to minimize the scope of the variables, ¿why are `temp' and `curr' members?


Also, your design seems overly complicated, requiring a lot of special cases.
Consider instead implementing the linked list as a circular list with a header cell
http://pastebin.com/gb7EdwSM (edit: ignore the [code][/code])

The idea is that for iterating you don't point to the cell that you want, but to the one that it is before that.
It simplifies the insertion and traversing, as you always refer to a valid cell.
Last edited on
zCasanova (6)
This is what I ended up with as a working version -

LIST.H

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
 
#ifndef LIST_H
#define LIST_H

class List
{
	private: // Variables
		
		typedef struct node
		{
			double data;
			node* next;	
		}* nodePtr;
		
		// Nodes used to store and traverse.
		nodePtr head;
		nodePtr curr;
		nodePtr temp;
		
	public: // Functions
		
		// Constructor
		List();
		
		// Adds node
		void AddNode(double addData);
		// Deletes node
		void DeleteNode(double delData);
		// Prints list
		void PrintList();		
};

#endif /* LIST_H */


LIST.CPP

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
 
#include <cstdlib>
#include <iostream>

#include "List.h"

using namespace std;

// Constructor
List::List()
{
	head = NULL;
	curr = NULL;
	temp = NULL;
}

void List::AddNode(double addData)
{
	// Creates a new node to hold input and NULL pointer.
	nodePtr n = new node;
	
	n->next =  NULL;
	n->data = addData;
	
	// Ensures there is a head node.
	if(head != NULL)
	{
		curr = head;
		temp = curr;
		
		// Checks to see if new input should be place before current head node.
		if (head->data >= addData) 
		{
			temp = head;
			head = n;
			head->next = temp;
			curr = head;
		
			return;
		}
		
		// Traverses list.
		while(curr != NULL)
		{
			// Makes sure current node points to another node.
			if(curr->next != NULL)
			{
				// Value comparison of input vs. next node.
				if(curr->next->data >= addData)
				{
					// Swaps nodes.
					temp = curr->next;
					curr->next = n;
					n->next = temp;
					break;
				}	
				else
				{
					// Moves to next node.
					curr = curr->next;
				}			
			}
			else
			{
				break;	
			}
		}	
		// Places node at end of list.
		curr->next = n;	
	}
	else
	{
		// Creates head node.
		head = n;
	}
}

void List::DeleteNode(double delData)
{
	// Temporary node to store node to be deleted.
	nodePtr delPtr = NULL;
	temp = head;
	curr = head;
	
	// Traverses list.
	while(curr != NULL && curr->data != delData)
	{
		temp = curr;
		curr = curr->next;
	}
	
	// Handles value not found.
	if(curr == NULL)
	{
		cout << delData << " was not found!" << endl;
		delete delPtr;
	}
	// Pulls node to be deleted out of list and relinks.
	else
	{
		delPtr = curr;
		curr = curr->next;
		temp->next = curr;
		
		if(delPtr == head)
		{
			head = head->next;
			temp = NULL;
		}
		
		delete delPtr;
		
		cout << "The value " << delData << " has been deleted." << endl;
	}
}

// Prints list.
void List::PrintList()
{
	curr = head;
	
	while(curr != NULL)
	{
		cout << curr->data << endl;
		curr = curr->next;
	}
}


MAIN.CPP

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
 
#include <cstdlib>
#include <iostream>
#include "List.h"

using namespace std;

int main()
{
	List Example;
	
	cout << "Initial list:  " << endl << endl;
	
	Example.AddNode(45.0);
	Example.AddNode(49.0);
	Example.AddNode(42.0);
	Example.AddNode(48.0);
	Example.AddNode(52.0);
	Example.AddNode(12.0);
	Example.AddNode(100.0);
	
	Example.PrintList();
	
	cout << endl;
	system("PAUSE");
	system("CLS");
	cout << "List with 49.0 added again:  " << endl << endl;
	
	Example.AddNode(49.0);
	
	Example.PrintList();
	
	cout << endl;
	system("PAUSE");
	system("CLS");
	
	Example.DeleteNode(42.0);
	Example.DeleteNode(49.0);
	Example.DeleteNode(100.0);
	Example.DeleteNode(52.0);
	
	cout << endl;
	system("PAUSE");
	system("CLS");
	cout << "Final list:  " << endl << endl;
	
	Example.PrintList();
	
	return(0);
}
Last edited on
zCasanova (6)
Doubly linked list that was due this weekend -

LIST.H

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
 
#ifndef LIST_H
#define LIST_H

class List
{
	private: // Variables
		
		typedef struct node
		{
			double data;
			node* next;	
			node* prev;
		}* nodePtr;
		
		// Nodes used to store and traverse.
		nodePtr head;
		nodePtr curr;
		nodePtr temp;
		nodePtr tail;
		
	public: // Functions
		
		// Constructor
		List();
		
		// Adds node
		void AddNode(double addData);
		// Deletes node
		void DeleteNode(double delData);
		// Prints list
		void PrintForward();
		void PrintBackward();
};

#endif /* LIST_H */


LIST.CPP

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
157
158
159
160
161
162
163
164
 
#include <cstdlib>
#include <iostream>

#include "List.h"

using namespace std;

// Constructor
List::List()
{
	head = NULL;
	curr = NULL;
	temp = NULL;
	tail = NULL;
}

void List::AddNode(double addData)
{
	// Creates a new node to hold input and NULL pointer.
	nodePtr n = new node;
	
	n->next = NULL;
	n->data = addData;
	n->prev = NULL;
	
	// Ensures there is a head node.
	if(head != NULL)
	{
		curr = head;
		temp = curr;
		
		// Checks to see if new input should be place before current head node.
		if (head->data >= addData) 
		{
			temp = head;
			head = n;
			head->next = temp;
			temp->prev = head;
			curr = head;
		
			return;
		}
		
		// Traverses list.
		while(curr != NULL)
		{
			// Makes sure current node points to another node.
			if(curr->next != NULL)
			{
				// Value comparison of input vs. next node.
				if(curr->next->data >= addData)
				{
					// Swaps nodes.
					temp = curr->next;
					temp->prev = n;
					curr->next = n;
					n->next = temp;
					n->prev = curr;
					
					break;
				}	
				else
				{
					// Moves to next node.
					curr = curr->next;
				}			
			}
			else
			{
				break;	
			}
		}	
		// Places node at end of list.
		curr->next = n;
		n->prev = curr;
		
		if(addData > tail->data)
		{
			tail = n;
		}
	}
	else
	{
		// Creates head node.
		head = n;
		tail = n;
	}
}

void List::DeleteNode(double delData)
{
	// Temporary node to store node to be deleted.
	nodePtr delPtr = NULL;
	temp = head;
	curr = head;
	
	// Traverses list.
	while(curr != NULL && curr->data != delData)
	{
		temp = curr;
		curr = curr->next;
	}
	
	// Handles value not found.
	if(curr == NULL)
	{
		cout << delData << " was not found!" << endl;
		delete delPtr;
	}
	// Pulls node to be deleted out of list and relinks.
	else
	{
		delPtr = curr;
		curr = curr->next;
		temp->next = curr;
		
		// If tail node points to nothing, no previous pointer needed.
		if(curr != NULL)
		{
			curr->prev = temp;
		}
		
		// Covers deletions of head node.
		if(delPtr == head)
		{
			head = head->next;
			temp = NULL;
		}
		
		// Covers deletion of tail node.
		if(delPtr == tail && temp != NULL)
		{
			tail = temp;
		}
		
		delete delPtr;
		
		cout << "The value " << delData << " has been deleted." << endl;
	}
}

// Prints list forward.
void List::PrintForward()
{
	curr = head;
	
	while(curr != NULL)
	{
		cout << curr->data << endl;
		curr = curr->next;
	}
}

// Prints list backward.
void List::PrintBackward()
{
	curr = tail;
	
	while(curr != NULL)
	{
		cout << curr->data << endl;
		curr = curr->prev;
	}
}


MAIN.CPP

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
 
#include <cstdlib>
#include <iostream>
#include "List.h"

using namespace std;

int main()
{
	List Example;
	
	cout << "Initial list forward:  " << endl << endl;
	
	Example.AddNode(45.0);
	Example.AddNode(49.0);
	Example.AddNode(42.0);
	Example.AddNode(48.0);
	Example.AddNode(52.0);
	Example.AddNode(12.0);
	Example.AddNode(100.0);
	
	Example.PrintForward();
	
	cout << "\nInitial list backward:  " << endl << endl;
	
	Example.PrintBackward();
	
	cout << endl;
	system("PAUSE");
	system("CLS");
	cout << "List printed forward with 49.0 added again:  " << endl << endl;
	
	Example.AddNode(49.0);
	
	Example.PrintForward();
	
	cout << "\nList printed backward with 49.0 added again:  " << endl << endl;
	
	Example.PrintBackward();
	
	cout << endl;
	system("PAUSE");
	system("CLS");
	
	Example.DeleteNode(42.0);
	Example.DeleteNode(49.0);
	Example.DeleteNode(100.0);
	Example.DeleteNode(52.0);
	
	cout << endl;
	system("PAUSE");
	system("CLS");
	cout << "Final list printed forward:  " << endl << endl;
	
	Example.PrintForward();
	
	cout << "\nFinal list printed backward:  " << endl << endl;
	
	Example.PrintBackward();
	
	return(0);
}
Last edited on
Topic archived. No new replies allowed.