Linked-list question

calvinfornia (48)
Hi, everyone. I'm working on a linked-list program. Somehow the result wasn't complete. It's missing the last part, but I can't find the reason!

Below is the source code:

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
 
//main.cpp
#include <iostream>
#include "Link_List.h"
using namespace std;

int main()
{
	
    // test default constructor
    Link_List<int> linkList1;
	cout << "Enter an integer: ";
	cin >> linkList1;


    // test copy constructor
    Link_List<int> linkList2(linkList1);
    
    
    // test getSize()
    cout << "linkList2 Size: " << linkList2.getSize() << endl;


    // test insert_node(value), delete_node(), operator<<, operator>>
    Link_List<int> linkList3;
	cout << "Enter a integer: ";
    cin >> linkList3;
	cout << "linkList3: "<< linkList3 << endl;

    linkList3.insert_node(11);
    linkList3.insert_node(12);
    linkList3.insert_node(13);
    linkList3.insert_node(14);
    linkList3.insert_node(15);
    cout << "Insert Boolean: " << linkList3.insert_node(16) << endl;
    cout << "linkList3: " << linkList3 << endl;
    cout << "Delete Boolean: " << linkList3.delete_node() << endl;
    cout << "linkList3: " << linkList3 << endl;


    // test assignment operator =, equality operator ==, 
	//insert_node(index, value), delete_node(index)
    Link_List<int> linkList4 = linkList3;
    cout << "linkList4: " << linkList4 << endl;

    cout << "Insert Boolean: " << linkList4.insert_node(3, 17) << endl;
    cout << "linkList4: " << linkList4 << endl;
    cout << "Delete Boolean: " << linkList4.delete_node(4) << endl;
    cout << "Equality Boolean: " << (linkList4==linkList3) << endl;
    cout << "linkList4: " << linkList4 << endl;


    // test subscript operator []
    const Link_List<int> linkList5 = linkList4;
    cout << "linkList5: " << linkList5 << endl;
    cout << "linkList4[1]: " << linkList4[2] << endl;
    cout << "linkList5[1]: " << linkList5[2] << endl;
    

	return 0;
}


And here's part of the header file due to limit of length:
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
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
 
#ifndef LINK_LIST
#define LINK_LIST
#include <iostream>
using namespace std;

template <typename T>
// All members in struct are default to public 
struct Int_Node					
{
	T value;
	Int_Node<T> *pre, *next;
};


template <typename T>
class Link_List
{
	template <typename U>
        // print all integers in the list
	friend ostream &operator<<(ostream &, const Link_List<U> &);  	
	
	template <typename U>
         // input a value at the back of the list, like insert_node(val);
	friend istream &operator>>(istream &, Link_List<U> &);  

public:
	Link_List();				// default constructor
	Link_List(const Link_List &link_list);	// copy constructor
	~Link_List();
	int getSize() const;
	
	const Link_List & operator=(const Link_List &);	// assignment operator
	bool operator==(const Link_List &) const;	// equality operator
	bool operator!=(const Link_List &right) const	// inequality operator
	{
		return !(*this == right);
	}

	T &operator[](int index);	// subscript operator for non-const objects
	T operator[](int index) const;	// subscript operator for const objects

	bool insert_node(T value);	// insert an integer at the back of link list
	bool delete_node();		// delete the last node
	bool insert_node(int index, T value);	// insert an integer after the i_th position
	bool delete_node(int index);	// delete the i_th node

private:
	int size; 			// Used to store the length of linked-list
	Int_Node<T> *head, *tail;	// pointer to the first and the last element of Link_List
};


#endif // LINK_LIST



/* Constructors */
// Default constructor
template<typename T>
Link_List<T>::Link_List()
:size(0), head(NULL), tail(NULL)
{
	
}// End constructor


// Copy constructor
template<typename T>
Link_List<T>::Link_List(const Link_List &link_list)// link_list is the list to be copied
:size(link_list.size)
{
	if(size == 0)
	{
		head == NULL ;
		tail == NULL ;
	}
	else
	{
		// temp used for create new space and recieve new values
		// old_list used to point at old list
		// new_list used to point at new list
		Int_Node<T> *temp , *old_list , *new_list ;
		temp = new Int_Node<T> ;
		old_list = link_list.head ;
		temp -> value = old_list -> value ;
		temp -> pre   = NULL ;
		temp -> next  = NULL ;
		new_list = temp ;
		head = temp ;
		old_list = old_list -> next ;

		for(int i = 1 ; i < size ; i++ )
		{
			temp = new Int_Node<T> ;
			temp -> value = old_list -> value ;
			temp -> pre   = new_list ;
			temp -> next  = NULL ;
			new_list -> next  = temp ;
			new_list = temp ;
			old_list = old_list -> next ; 
		}
		tail = new_list ;
	}
}
// End constructor 



/* Destructor */
template<typename T>
Link_List<T>::~Link_List()
{
	Int_Node<T> *temp ;
	temp = head ;
	for(int i = 0 ; i < size ; i++ )
	{
		head = temp -> next ;
		delete [] temp ;
		temp = head ;
	}
}// End destructor


/* Operators */
// Operator << overloading, print all integers in the list
template<typename U>
ostream &operator << (ostream &output, const Link_List<U> &link_list)
{
	Int_Node<U> *temp ;
	
	temp = link_list.head ;
	for(int i = 0 ; i < link_list.size ; i++ )
	{
		output << temp -> value << " " ;
		temp = temp -> next ;
	}
	output << endl ;
	
	return output ;
}// End function operator << overloading


// Operator >> overloading, input a value at the back of 
// the list, like insert_node(val);
template<typename U>
istream &operator >> (istream &input, Link_List<U> &link_list)
{
	Int_Node<U> *temp ;
	temp = new Int_Node<U> ;
	input >> temp -> value ;
	temp -> next = NULL ;
	temp -> pre  = link_list.tail ;
	if( link_list.size == 0 )
	{
		link_list.tail = temp ;
		link_list.head = temp ; 
	}
	else
	{
		link_list.tail -> next = temp ;
		link_list.tail = temp ;
	}
	
	link_list.size++ ;
	
	return input ;
}// End function operator >> overloading


// Operator = overloading, assignment operator
template<typename T>
const Link_List<T>& Link_List<T>::operator = (const Link_List &link_list)
{
	size = link_list.size ;
	if(size == 0)
	{
		head == NULL ;
		tail == NULL ;
	}
	else
	{
		Int_Node<T> *temp1 , *temp2 , *temp3 ;
		temp1 = new Int_Node<T> ;
		temp2 = link_list.head ;
		temp1 -> value = temp2 -> value ;
		temp1 -> pre   = NULL ;
		temp1 -> next  = NULL ;
		temp3 = temp1 ;
		head = temp1 ;
		temp2 = temp2 -> next ;
		
		for(int i = 1 ; i < size ; i++ )
		{
			temp1 = new Int_Node<T> ;
			temp1 -> value = temp2 -> value ;
			temp1 -> pre   = temp3 ;
			temp1 -> next  = NULL ;
			temp3 -> next  = temp1 ;
			temp3 = temp1 ;
			temp2 = temp2 -> next ; 
		}
		tail = temp3 ;
	}
	return *this;
}// End function operator = overloading	


// Subscript operator for non-const objects
template <typename T>
T & Link_List<T>::operator [] (int index)
{
	if (index < 0 || index >= size)
	{
		cout<< "Error: Subscript "<< index 
			<< " is out of range"<<endl;
			exit(1);
	}
	else
	{
		// Return reference
		Int_Node<T> *ptr ;
		ptr = head ;
		for(int i = 0 ; i < index ; i++)
		{
			ptr = ptr -> next ;
		}
		
		return ptr -> value ;
	}
}// End subscript operator for non-const objects


// Subscript operator for const objects
template <typename T>
T Link_List<T>::operator [] (int index) const
{
	if (index < 0 || index >= size)
	{
		cout<< "Error: Subscript "<< index 
			<< " is out of range"<<endl;
			exit(1);
	}
	else
	{
		// Return reference
		Int_Node<T> *ptr ;
		ptr = head ;
		for(int i = 0 ; i < index ; i++)
		{
			ptr = ptr -> next ;
		}
		
		return ptr -> value ;
	}
}// End subscript operator for const objects


It comes out with
Enter an integer: 2
linkList2 Size: 1
Enter a integer: 3
linkList3: 3

Insert Boolean: 1
linkList3: 3 11 12 13 14 15 16

Delete Boolean: 1
linkList3: 3 11 12 13 14 15

linkList4: 3 11 12 13 14 15

Insert Boolean: 1
linkList4: 3 11 12 17 13 14 15

Delete Boolean: 1
Equality Boolean: 0
linkList4: 3 11 12 13 14 15
--------------------------------
Process exited after 3.932 seconds with return value 3221225477


Thanks for your help in advance!!
Last edited on
salem c (3700)
Well if you want people to debug your code, you really need to find a way of posting something that compiles.
1
2
3
4
5
6
7
8
9
10
11
12
13
 
main.cpp:(.text.startup+0x7e): undefined reference to `Link_List<int>::getSize() const'
main.cpp:(.text.startup+0x11e): undefined reference to `Link_List<int>::insert_node(int)'
main.cpp:(.text.startup+0x12b): undefined reference to `Link_List<int>::insert_node(int)'
main.cpp:(.text.startup+0x138): undefined reference to `Link_List<int>::insert_node(int)'
main.cpp:(.text.startup+0x145): undefined reference to `Link_List<int>::insert_node(int)'
main.cpp:(.text.startup+0x152): undefined reference to `Link_List<int>::insert_node(int)'
/tmp/ccNiXINA.o:main.cpp:(.text.startup+0x15f): more undefined references to `Link_List<int>::insert_node(int)' follow
/tmp/ccNiXINA.o: In function `main':
main.cpp:(.text.startup+0x1bc): undefined reference to `Link_List<int>::delete_node()'
main.cpp:(.text.startup+0x268): undefined reference to `Link_List<int>::insert_node(int, int)'
main.cpp:(.text.startup+0x2cb): undefined reference to `Link_List<int>::delete_node(int)'
main.cpp:(.text.startup+0x303): undefined reference to `Link_List<int>::operator==(Link_List<int> const&) const'
collect2: error: ld returned 1 exit status


Like for example, commenting out calls to methods which don't actually change the problem, but do mean you can post enough code to work with.

Then there's compiling with as many warnings as possible enabled, then fixing dumb mistakes like confusing comparison with assignment.
1
2
3
4
5
6
7
8
9
10
 
$ g++ -Wall -Wextra -O2 main.cpp
In file included from main.cpp:4:0:
Link_List.h: In instantiation of ‘Link_List<T>::Link_List(const Link_List<T>&) [with T = int]’:
main.cpp:17:39:   required from here
Link_List.h:70:3: warning: statement has no effect [-Wunused-value]
   head == NULL ;
   ^
Link_List.h:71:3: warning: statement has no effect [-Wunused-value]
   tail == NULL ;
   ^

Your head and tail are garbage, not NULL;

Topic archived. No new replies allowed.