C++

Forum

 
IMPLEMENTING AND EXERCISING A LINKED LIST

studentCJ (6)
Hi I am programming about IMPLEMENTING AND EXERCISING A LINKED LIST, I have finished my code, but the program did not do what I want. 

This program responds to commands the user enters to
manipulate an ordered list of integers, which is
initially empty. In the following commands, k1 is a
position in the list, and v is an integer.
e -- Re-initialize the list to be empty.
i v -- Insert the value v into the list.
r v -- Remove the value v from the list.
m -- Is the list empty ?
l -- Report the length of the list.
p v -- Is the value v present in the list ?
k k1 -- Report the k1th value in the list.
w -- Write out the list.
h -- See this menu.
q -- Quit.
-->i 27
Press any key to continue . . .

The program ends when I input the value in the list. Can you please check my code to find my mistakes? I will be appreciate.
The simpale run should be:

This program responds to commands the user enters to
  manipulate an ordered list of integers, which is
  initially empty. In the following commands, k1 is a
  position in the list, and v is an integer.

    e -- Re-initialize the list to be empty.
    i v -- Insert the value v into the list.
    r v -- Remove the value v from the list.
    m -- Is the list empty?
    l -- Report the length of the list.
    p v -- Is the value v present in the list?
    k k1 -- Report the k1th value in the list.
    w -- Write out the list.
    h -- See this menu.
    q -- Quit.

  --> i 27
  --> i 42
  --> i 15
  --> i 33
  --> i 14
  --> m
  The list is NOT empty.
  --> w
  List: < 14, 15, 27, 33, 42 >
  --> r 33
  --> w
  List: < 14, 15, 27, 42 >
  --> p 22
  The value 22 is NOT present in the list.
  --> p 42
  The value 42 is present in the list.
  --> k 3
  The 3th element of the list is 27.
  --> k 9
  The list does not contain 9 values.
  --> q

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
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
 
  #include <cstdlib>                        
#include <list>
#include <iostream>

using namespace std;
 struct node
{
	int data;
	node* next;

};



void initialize(node*p);
void insert(int data,int n);
void remove(struct node **head_ref, int key);
bool empty(node*);
int length(node*head);
bool valuein(node*head,int x);
int reportvalue(int value);
void printlist(struct node* temp);
int menu();

int main()
{

	node *head = NULL;
	
	char commands=' ';
	int value;
	int pos = 0;

	cout << "This program responds to commands the user enters to\nmanipulate an ordered list of integers, which is\ninitially empty. In the following commands, k1 is a\nposition in the list, and v is an integer." << endl;
	cout << "e -- Re-initialize the list to be empty.\ni v -- Insert the value v into the list.\nr v -- Remove the value v from the list.\nm -- Is the list empty ? \nl -- Report the length of the list.\np v -- Is the value v present in the list ? \nk k1 -- Report the k1th value in the list.\nw -- Write out the list.\nh -- See this menu.\nq -- Quit." << endl;
	


	while (commands != 'q')
	{
		cout << "-->";

		cin >> commands;


		switch (commands)
		{
		case 'e':
		{
					initialize(head->next); 
		}
		case 'i':
		{cin >> value;
		insert(value, pos);
		pos++;
		
		}
		case 'm':
		{ empty(head);
		if (empty(head) == true)
		{
			cout << "it is empty" << endl;
		}
		else
			cout << "not empty" << endl;


		}
		case'p':
		{ cin >> value; 
		
		if (valuein(head, value) == true)
		{
			cout << "it is in the list" << endl;
		} 

		}
		case 'r':
		{cin >> value;
		remove(&head, value);
		}
		case'w':
		{
				   printlist(head);

		}
		case'h':
		{cout << "This program responds to commands the user enters to\nmanipulate an ordered list of integers, which is\ninitially empty. In the following commands, k1 is a\nposition in the list, and v is an integer." << endl;
		cout << "e -- Re-initialize the list to be empty.\ni v -- Insert the value v into the list.\nr v -- Remove the value v from the list.\nm -- Is the list empty ? \nl -- Report the length of the list.\np v -- Is the value v present in the list ? \nk k1 -- Report the k1th value in the list.\nw -- Write out the list.\nh -- See this menu.\nq -- Quit." << endl;

		}
			

		


		}
		
		
	} 
	system("pause");
	return 0;
}
bool empty(node*)
{
	node *root=NULL;
	if (root->next == root)
		return true;
	else
		return false;
}


	void initialize(node*p)
{
	
	node *temp;
	if (p == NULL){
		return;
	}
	temp = p;
	initialize(p->next);
	delete temp;
}
	void insert(int data, int pos)
	{
		node*head = new node;
		node* prev = new node();
		node* curr = new node();
		node* newNode = new node();
		newNode->data = data;

		int tempPos = 0;   // Traverses through the list

		curr = head;      // Initialize current to head;
		if (head != NULL)
		{
			while (curr->next != NULL && tempPos != pos)
			{
				prev = curr;
				curr = curr->next;
				tempPos++;
			}

		}
	}
	bool valuein(node*head, int x)
	{
		bool judge=false;
		struct node* current = head;  // Initialize current 
		while (current != NULL)
		{
			if (current->data == x)
				judge=true;
			current = current->next;
		}
		return judge;
	}
	void remove(struct node **head_ref, int key)
	{

		struct node* temp = *head_ref, *prev;
		prev = NULL;

		if (temp != NULL && temp->data == key)
		{
			*head_ref = temp->next;
			free(temp);
			return;
		}


		while (temp != NULL && temp->data != key)
		{
			prev = temp;
			temp = temp->next;
		}


		if (temp == NULL) return;


		prev->next = temp->next;

		free(temp);
	}
	void printlist(node* temp)
	{
		
		if (empty(temp) == false)
		{
			cout << "here temp(head)" << temp->next << endl;
			while (temp != NULL)
			{
				cout << temp->data << endl;
				temp = temp->next;
			}
		}
	}
	int length(struct node*head)
	{
		int count = 0;  // Initialize count 
		struct node* current = head;  // Initialize current 
		while (current != NULL)
		{
			count++;
			current = current->next;
		}
		return count;
	}

coder777 (8444)
There are plenty of problems.

A switch case normally requires a break;, otherwise it falls through to the next case.

Your insert(...) function basically does nothing but creating a memory leak. Instead of line 127 you need to have a further parameter which is supposed to be the head.
It does not make sense that you create new object for prev/curr. Set them to NULL.

The function empty(...) will crash because you access a member of root which is set to NULL. Use the provided parameter instead. Line 107: Check against NULL not root.
Handy Andy (5051)
Hello studentCJ,

To go along with and in addition to what coder77 has said some tips that might help:

In your subject line do not shout. Using all caps is considered shouting and a bit rude.

In your program the line using namespace std; is a bad idea and best not to use. There have been many posts here on the subject. Do a search if you want to know more.

For the struct; it is generally accepted the the name of a class or a struct should start with a capital letter. Regular variables should start with a lower case letter and anything defined as a constant should be in all caps.

The "insert" function gives the impression that this is a doubly linked list, but yhe struct is set up for a singly linked list.

Your functions need to be reworked. Most of what I see is just wrong.

I think you need to reread your book and get a better understanding of linked lists. These links may be of some help:
https://www.google.com/search?source=hp&ei=cTRsXPeYKoXHjwTZ74vYDA&q=c%2B%2B+doubly+linked+list&oq=c%2B%2B+doubly&gs_l=psy-ab.1.0.0l10.2918.13645..17290...0.0..0.86.825.11......0....1..gws-wiz.....0..35i39j0i131.LHlcJ54BT_Q

https://www.youtube.com/watch?v=k0pjD12bzP0
The youtube video that comes up after this should also help.

Of the two functions I looked at "initialize" should be called "reInitialize" based on the menu choice. This function should delete all nodes except head and set head's "next" and "prev" pointers to "nullptr" with the last step of setting "head" to "nullptr". Without deleting the current linked list as coder777 says you are creating a memory leak.

The "insert" function is misleading. At first I thought it was to insert in the middle of the list, but when looking at the variable "pos" it is actually adding to the end. Inside the function you create a block of memory for head. This should have been done long before you get here. Creating a block of memory for "prev" is not necessary because if it is not the "head" node, which has no previous, then previous already exists. The variables "curr" should be just a pointer then yo can use "newNode" to add to the list.

The if statement and while loop appear to be finding the end of the list, but you do nothing to add the "newNode" to the list.

I suggest working in small parts. First get the "insert", i.e., "add" function working properly before you tackle the other functions. Until you create a linked list that you can use there is no point on working on the other functions and once you have a proper linked list the other functions will be easier to change.

For what its worth when I first learned about linked lists we were taught to create a "head" and "tail" node pointers to work with. this way it makes it easier to start at the tail if you need to.

Hope that helps,

Andy
Topic archived. No new replies allowed.