C++

Forum

 
 
Link List - Error

CodeNovice01 (278)
I've been trying to figure out this error on this program, with no luck thus far. The variable 'Node' is a pointer and it's saying the variable 'previous' is uninitialized.

1
2
 
Link List\LinkList\LinkList.cpp(65): error C4703: 
potentially uninitialized local pointer variable 'previous' used


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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
 
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>

using namespace std;

ifstream inf("link.in");
ofstream out("link.out");

class LLname
{
public:
     string name;
     LLname* next;   //pointer to the next node
};

typedef LLname* Node;
Node head;

LLname* newNode()  //function to create a new node
{
     LLname* temp;
     temp = new LLname();
     temp->name = " ";
     temp->next = NULL;
     return temp;
}

//prototypes
bool search(string value);
void insert(string value);
LLname* deleteNode(LLname* head);
void printList(LLname* head);
void fileHeader();
void deleteList(LLname* head);

void insert(string value)  //inserting the value at the front of the list
{
     Node current;
     Node previous;
     Node temp;
     if (head == NULL)  //if empty
     {
          head = newNode();
          head->name = value;
          head->next = NULL;  /* not needed */
     }
     else
     {
          current = head;
          while (current != NULL)
          {
               previous = current;
               current = current->next;
          }
          temp = newNode();
          temp->name = value;
          previous->next = temp;    ///////Error occurs here///////
     }
};

bool search(string value)   //searching for the value
{
     //pointer to current node
     LLname* current = head;

     //pointer to previous node
     LLname* previous = NULL;

     while (current)
     {
          if (current->name == value)
          {
               if (previous != NULL)
               {
                    //move that value to the front
                    previous->next = current->next;
                    current->next = head;
                    head = current;
               }
               return true;
          }
          //continue down the list
          previous = current;
          current = current->next;
     }
     //value not found
     return false;
}

LLname* deleteNode(LLname* head)  //deletes the last item in the buffer
{
     if (head == NULL)
     {
          return NULL;
     }

     if (head->next == NULL)
     {
          delete head;
          return NULL;
     }
     return NULL;
}

void printList(LLname* head) //prints the list
{
     Node current;
     current = head;
     while (current)
     {
          out << current->name << " ";
          current = current->next;
     }
}

//deletes the entire list
void deleteList(LLname* head)
{
     Node current;
     current = head;

     while (current != 0)
     {
          head = current->next;
          delete current;
          current = head;
     }

     delete head;
}

void fileHeader()  //header for top of file output
{
     out << "**********************************" << endl;
     out << "Rachel Coughanour CS 372" << endl;
     out << "Output file for link list program" << endl;
     out << "**********************************" << endl;
}

//variables
int bufferSize;
string name;

//beginning of main
int main()
{
     if (!inf)
     {
          out << "File could not be opened. Please try again.";
          return 0;
     }

     fileHeader();
     int count = 0;
     int memoryAccess = 0;

     cout << "Enter the buffer size" << endl;
     cin >> bufferSize;

     while (inf >> name)
     {
          //if the number of items read in equals the size of the buffer
          //delete the one on the end
          if (count == bufferSize)
          {
               head = deleteNode(head);
               count--;
          }
          //if variable found, move it to the front
          else if (search(name))
          {
          }

          //else, add it to the buffer
          else
          {
               insert(name);
               count++;
               memoryAccess++;
          }
     }

     out << "Buffer size: " << bufferSize << endl;
     out << "Number of memory accesses: " << memoryAccess << endl;
     out << "Items in the buffer: ";
     printList(head);

     //deleting the list
     deleteList(head);

     inf.close();
     out.close();
     return 0;
Last edited on
jonnin (11329)
insert has a ; it does no need on the end.

insert has a logical flaw.
if you remove the fluff statements, you see this pattern:

node previous; //uninit pointer
if(something)
previous = value;
else
previous not touched here (if the while loop is not entered, because othervariable is null)
use previous //error, in some cases, you could get here without having set it.

solution:
node previous = nullptr;
AND be sure that previous really does have a value. The compiler can't be sure that you enter the while loop. If you actually do always enter it, then the code is really fine in spite of compiler fussing. But you need to be certain... if not, you need to handle it. and setting it to null will crash if you get to the usage without setting it...
Last edited on
seeplus (6456)
Use nullptr rather than NULL/0 in C++ code.

If LLName class has constructors, the code can be simplified.

If you also maintain tail as well as head, then inserting at tail can be done without traversing the list.

Why is search altering the list? Surely search is a read-only list operation? If it does something else then perhaps a name change?

In deleteList():

 
 
delete head;


is not needed as head will be nullptr.

deleteNode() says delete last Node. In which case why not name deleteLast(). In any case it will only delete the first node if there is only 1 node. Shouldn't the parameter be called something other than head?

deleteList() and printList() functions don't need an argument as head is a global variable.

The terminology used seems mixed.

head is the first node - the beginning. If used, tail is the last node - the end. The node pointers point to the next node in the link from head to tail.

front/back first/last can be confusing so unless explained are best avoided. Just use head/tail.

Consider (not tried):

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
 
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>

using namespace std;

class LLname
{
public:
	string name;
	LLname* next = nullptr;   //pointer to the next node

	LLname() {}
	LLname(const std::string& nam) : name(nam) {}
};

typedef LLname* Node;

//prototypes
bool search(const string& value);
void insert(const string& value);
Node deleteNode(Node node);
void printList();
void fileHeader();
void deleteList();
Node newNode(const std::string& nam = "");

//globals
ifstream inf("link.in");
ofstream out("link.out");
Node head;

Node newNode(const std::string& nam)  //function to create a new node
{
	return new LLname(nam);
}

void insert(const string& value)  //inserting the value at the front of the list
{
	if (head == nullptr)		//if empty
		head = newNode(value);
	else {
		Node previous = head;

		for (Node current = head; current != nullptr; current = current->next)
			previous = current;

		previous->next = newNode(value);
	}
}

bool search(const string& value)   //searching for the value
{
	//pointer to current node
	Node current = head;

	//pointer to previous node
	Node previous = NULL;

	//???????????
	while (current)
	{
		if (current->name == value)
		{
			if (previous != NULL)
			{
				//move that value to the front
				previous->next = current->next;
				current->next = head;
				head = current;
			}
			return true;
		}
		//continue down the list
		previous = current;
		current = current->next;
	}
	//value not found
	return false;
}

Node deleteNode(Node node)  //deletes the last item in the buffer
{
	// ???
	if (node != nullptr)
		if (node->next == nullptr)
			delete node;

	return nullptr;
}

void printList() //prints the list
{
	for (Node current = head; current != nullptr; current = current->next)
		out << current->name << " ";
}

//deletes the entire list
void deleteList()
{
	for (Node current = head; current != nullptr; current = head) {
		head = current->next;
		delete current;
	}
}

.......

Last edited on
CodeNovice01 (278)
I've altered up the code and it runs and outputs, but the 'cnt' variable within the 'buffer' functions isn't outputting anything other than 0, I know the number must be in the hundreds. Is this issue occuring because I have the functions - 'insert' and 'printList' within the class?

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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
 
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
using namespace std;

ifstream inf("link.in");
//ofstream cout("link.cout");

struct node
{
     string name;
     node* linky;
};

node* head;
node* newNode();
int cnt;
void buffer6();
void buffer7();
void buffer8();
void buffer9();
void buffer10();

class list
{
public:
     string name;
     list* next;   //pointer to the next node
     void insert(string, int);
     void printList();

};



node* newNode()  //function to create a new node
{
     node* temp;
     temp = new node;
     temp->name = " ";
     temp->linky = nullptr;
     return temp;
}

void list::insert(string name, int sz)  //inserting the value at the front of the list
{
     node* cur = head;//starting point
     node* prev = nullptr;//ending point
     node* temp = newNode();
     int i = 1;
     
     temp->name = name;

     if (head == nullptr)
     {
          head = temp;
          cnt++;
     }
     else
     {
          cur = head;
          prev = nullptr;
          while (cur != nullptr && cur->name != name)
          {
               prev = cur;
               cur = cur->linky;
               i++;
               if (i == sz)
                    prev->linky = nullptr;
          }
          if (cur && cur->name == name)
          { 
               if (cur != head)
               {
                     if (prev)
                         prev->linky = cur->linky;
                     cur->linky = head;
                     head = cur;
               }
          }
          else
          {
               temp->linky = head;
               head = temp;
               cnt++;
          }        
     }
     return;
}

void list::printList() //prints the list
{
     node* cur;
     cur = head;
     while (cur)
     {
          cout << cur->name << " ";
          cur = cur->linky;
     }
}

void buffer6()
{
     list i,p;
     string name;
     int buff = 6,
          cnt = 0;

     while (inf >> name)
          i.insert(name, buff);
     cout << "Buffer size of " << buff
           << " memory was accessed  " << cnt << " times.\n";
     p.printList();
}

void buffer7()
{
     list i, p;
     string name;
     int buff = 7,
          cnt = 0;

     while (inf >> name)
          i.insert(name, buff);
     cout << "\nBuffer size of " << buff
          << " memory was accessed  " << cnt << " times.\n";
     p.printList();
}

void buffer8()
{
     list i, p;
     string name;
     int buff = 8,
          cnt = 0;

     while (inf >> name)
          i.insert(name, buff);
     cout << "\nBuffer size of " << buff
          << " memory was accessed  " << cnt << " times.\n";
     p.printList();
}

void buffer9()
{
     list i, p;
     string name;
     int buff = 9,
          cnt = 0;

     while (inf >> name)
          i.insert(name, buff);
     cout << "\nBuffer size of " << buff
          << " memory was accessed  " << cnt << " times.\n";
     p.printList();
}

void buffer10()
{
     list i,p;
     string name;
     int buff = 10,
          cnt = 0;

     while (inf >> name)
          i.insert(name, buff);
     cout << "\nBuffer size of " << buff
          << " memory was accessed  " << cnt << " times.\n";
     p.printList();
}


//beginning of main
int main()
{
     if (!inf)
     {
          cout << "Error with INFILE, check folder!";
          return 0;
     }

     buffer6();
     buffer7();
     buffer7();
     buffer8();
     buffer9();
     buffer10();
     
     inf.close();
     //cout.close();
     return 0;
}
CodeNovice01 (278)
my output:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
Buffer size of 6 memory was accessed  0 times.
windows box estate team photos conditions
Buffer size of 7 memory was accessed  0 times.
windows box estate team photos conditions
Buffer size of 7 memory was accessed  0 times.
windows box estate team photos conditions
Buffer size of 8 memory was accessed  0 times.
windows box estate team photos conditions
Buffer size of 9 memory was accessed  0 times.
windows box estate team photos conditions
Buffer size of 10 memory was accessed  0 times.
windows box estate team photos conditions
C:\Users\Owner\OneDrive\Fall 2020\CS 372 - Data Structures\6th Program - Link List\LinkList\Debug\LinkList.exe (process 11476) exited with code 0.
Press any key to close this window . . .


What the output should look like:
1
2
3
4
5
6
7
8
9
10
 
With buffer size 6, memory was accessed 319 times.
windows   box   estate   team   photos   conditions   
With buffer size 7, memory was accessed 301 times.
windows   box   estate   team   photos   conditions   left   
With buffer size 8, memory was accessed 260 times.
windows   box   estate   team   photos   conditions   left   select   
With buffer size 9, memory was accessed 247 times.
windows   box   estate   team   photos   conditions   left   select   west   
With buffer size 10, memory was accessed 225 times.
windows   box   estate   team   photos   conditions   left   select   west   advanced
CodeNovice01 (278)
This is the infile
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
 
tom sue joe finney tobee total joe joe tom total goo tobee tobee total sid mikey 
tom tobee blue blue blue sue 
goo blue blue miney tobee sumup moreso sid sid mikey mikey 
lesso maybso goo sidtom tom tom sue blue goo sumup 
tobee finney finney tobee joe joe tom total goo tobee tobee total sid mikey 
tom tobee blue blue blue sue
mikey joe where blue tom finney blue goo joe mikey where finney joe mikey
goo blue blue miney tobee cooly sumup moreso sid sid mikey mikey 
lesso maybso goo sid tom mikey lisso maybso goo goo total
where about about tom blue sid finney jojo tobee joe joe tom total goo tobee tobee total sid mikey 
tom tobee blue blue blue sue 
goo blue blue miney tobee sumup lisso maybso goo goo sumup total moreso sid mikey mikey 
cooly lisso goo tobee tobee total sid mikey 
tom tobee blue blue blue sue so so so total tom  
lesso maybso goo ghost sid tom blue sid where joe sue joe sue tom sue 
where sid tom mikey lisso jo sumup jo jo maybso goo goo sumup total
sumup lisso maybso goo goo sumup total cooly about tom blue sid finney tobee ghost ghost cooly joe joe tom total
goo blue bmoreso sid sid mikeylue miney  mikey
tom tobee blue blue blue sue so so so total tom 
lesso goo tobee tom blue sid sid goo maybso goo sid tom blue sid where joe ghost sue joe sue tom sue 
mikey total conditions maybso goo goo sumup total blue tom finney goo sid blue blur blue joe sumup total miney total
categories advanced estate finney goo sid blue blur box west team estate team estate box estate sales look windows photos english estate 
box estate box left conditions select sid tom mikey lisso maybso goo goo total
where about about tom blue sid finney jojo tobee joe joe tom total goo tobee tobee total sid mikey 
tom tobee blue blue blue sue 
goo blue blue miney tobee sumup lisso maybso goo goo sumup total moreso sid mikey mikey 
cooly lisso goo tobee tobee windows photos sid blue blur blue joe sumup team estate box windows  photos team estate photos 
conditions select windows
photos windows  photos team estate photos windows photos west left conditions west photos team estate 
west categories advanced estate box blue sid where joe sue joe sue tom sue 
where sid tom mikey lisso jo sumup jo jo maybso goo goo sumup total
sumup lisso maybso goo goo photos team select windows photos left conditions team estate 
left conditions west west west west select west windows select windows photos team west left conditions 
photos team estate box windows select left  total cooly about tom blue sid finney tobee ghost ghost cooly joe joe tom total
goo blue bmoreso sid sid mikeylue categories 
advanced west estate box select photos team select windows photos left conditions team estate 
left conditions west west west west select west windows select windows photos team west left conditions 
photos team estate box windows select left conditions windows left conditions photos team windows photos 
team estate box windows
CodeNovice01 (278)
Scratch all that above, apologies, but i finally figured it out.

If one doesnt mind could you help simplify the 'insert' method?
dhayden (5795)
head should be part of list.

The name printList is redundant since it's part of class List. Just call it print

You're supposed to insert at the beginning of the list, not the end.

Make a constructor for node.

Your bufferN() functions have a flaw because they all try to read the list. The first one reads the list and thereafter inf is at the end of file so the code doesn't read anything. Since the previous call to buffer() truncated the list, it never grows the way you expect it to.

To fix this, I added a clear(); method to clear out the list, a read() method to read the list from a stream and a destructor to prevent memory leaks.
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
 
#include <iostream>
#include <iomanip>
#include <fstream>
#include <string>
using namespace std;

struct node
{
    node(const string &nm, node *next = nullptr):
	name(nm), linky(next)
    {}
    string name;
    node *linky;
};

int cnt;

class list
{
public:
    node* head = nullptr;
    void insert(string, int);
    void print();
    void read(istream &in, int sz);
    void clear();
    ~list() { clear(); }
};



void list::insert(string name, int sz)  //inserting the value at the front of the list
{
    node* cur;

    int i = 0;
     node **pp;
     for (pp = &head; (cur = *pp); pp = &cur->linky) {
	 if (cur->name == name) {
	     // found it. Move it to the front;
	     *pp = cur->linky;
	     cur->linky = head;
	     head = cur;
	     return;
	 }
	 if (++i == sz) break;
     }
     if (i == sz) {
	 delete cur;
	 *pp = nullptr;
     }

     node* temp = new node(name, head);
     head = temp;
     ++cnt;
}

void list::clear()
{
    node *tmp;
    while (head) {
	tmp = head->linky;
	delete head;
	head = tmp;
    }
}

void list::read(istream &in, int sz)
{
    string name;
    clear();
    while (in >> name) {
	insert(name, sz);
    }
}
	    
    
void list::print() //prints the list
{
     node* cur;
     cur = head;
     while (cur)
     {
          cout << cur->name << " ";
          cur = cur->linky;
     }
     cout << '\n';
}

void buffer(list &p, int buff)
{
     ifstream inf("link.in");
     cnt = 0;
     p.read(inf, buff);
     cout << "Buffer size of " << buff
           << " memory was accessed  " << cnt << " times.\n";
     p.print();
}


//beginning of main
int main()
{
    list p;
     for (int sz = 6; sz <=10; ++sz) {
	 buffer(p, sz);
     }

     return 0;
}

Buffer size of 6 memory was accessed  319 times.
windows box estate team photos conditions
Buffer size of 7 memory was accessed  301 times.
windows box estate team photos conditions left
Buffer size of 8 memory was accessed  260 times.
windows box estate team photos conditions left select
Buffer size of 9 memory was accessed  247 times.
windows box estate team photos conditions left select west
Buffer size of 10 memory was accessed  225 times.
windows box estate team photos conditions left select west advanced

CodeNovice01 (278)
dhayden - what is line 9,10,11(the : and name(nm) linky(next) is throwing me off.
Line 26 whats the ~ for?
line 36 why is there **pp? is pp previous pointer?

Thank you for clarifying the issues. your code is a lot less complicated than mine has turned out to be.

Also, is there an alternative to the **, could implementing one * suffice or will it throw the program haywire?
Last edited on
dhayden (5795)
Thanks for asking clear, specific questions.

Lines 9-11: The ":" syntax in a constructor lets you call a specific constructor when creating the member data of class.:
1
2
3
4
 
    node(const string &nm, node *next = nullptr):
	name(nm), // construct name by calling string(nm). So it makes name a copy of nm
	linky(next)  // construct linky the copy constructor. So linky = next
    {}  // This is the body of the constructor. Since there's nothing to do, the body is empty.


Line 26: ~list() is the destructor for class list. This gets called whenever a list is deleted or goes out of scope. Just as the constructor is called when an object is created, the destructor is called when an object is destroyed.

Line 36: Sorry, I should have explained this. node **pp creates a pointer to a pointer to a node. It takes the place of a "previous pointer." Instead of keeping a pointer to the previous node, it keeps a pointer to the pointer to the current node. In other words, it points to head, or it points to the linky pointer of a previous node. The nice thing about doing it this way is that you don't have to check for previous == nullptr. It may make more sense if I call it headOrLinky instead:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
    int i = 0;
     node **headOrLinky;
     // Walk down the list. Cur points to the current item, and headOrLinky pointers
    // the the pointer to cur (i.e., it points to head, or the previous node's linky pointer.)
     for (headOrLinky = &head; (cur = *headOrLinky); headOrLinky = &cur->linky) {
	 if (cur->name == name) {
	     // found it. Move it to the front;
	     *headOrLinky = cur->linky;  // point headOrLinky to the next node.
	     cur->linky = head;   // point the cur node to the head
	     head = cur;   // point head to the cur node.
	     return;
	 }
	 if (++i == sz) break;
     }
     if (i == sz) {
	 delete cur;
	 *headOrLinky = nullptr;
     }
CodeNovice01 (278)
dhayden, thank you again for the explanations. That is a really neat way of doing the 'head' or 'linky' in the '**'. I've never seen that before, it's a lot easier than carrying the extra variable for previous.
Topic archived. No new replies allowed.