C++

Forum

 
Singly Linked List problem

painith (16)
Hi i am trying to figure out how to make a singly linked list class. I am having trouble with some of the function in the class. This is my attempt so far and i need to know if im on the right track.

StringNode.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
#ifndef STRING_NODE_H
#define STRING_NODE_H

#include <string>

// A node in string singly linked list
class StringNode {
private:
	// element value of a node
	std::string elem;
	
	// pointer to the next node in the list
	StringNode *next;
	
	// provide StringLinkedList access
	friend class StringLinkedList;
};

#endif

StringLinkedList.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
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
 
#ifndef STRING_LINKED_LIST_H
#define STRING_LINKED_LIST_H

#pragma warning(disable: 4290)

#include "StringNode.h"
#include "Exception.h"

// String singly linked list
class StringLinkedList {
private:
	// pointer to the head of the list
	StringNode *head;

	// size of the list
	int n;

public:
	// default constructor
	StringLinkedList();

	// destructor 
	~StringLinkedList();

	// ## this function is provided ##
	// return the string representation of the list; each node is seperated
    // by "->"
	//	example: 
	//		"A->B->C" (without quotes)
	//			A is the head node, C is the tail
	//		"" (without quotes)
	//			empty list
	std::string toString();

	// return true if the list is empty, false otherwise
	bool empty() const;

	// return the number of nodes in the list
	//	note: take advantage of the private member we have, implement this
	//		running with O(1)
	int size() const;

	// return the element of front node
	const std::string& front() const throw (EmptyException);

	// return the element of back node
	const std::string& back() const throw (EmptyException);
    
	// return the element of a node at a specific index (index) of the list
	//	EmptyException is thrown if the list is empty
	//	The index should be in range of [0, n-1], which is 0 <= index <= (n-1)
    //  OutOfBoundException is thrown if index is out of that range
	const std::string& get(int index) const throw (EmptyException, OutOfBoundException);

	// add a new node with element e to the front of the list
	void addFront(const std::string& e);

	// add a new node with element e to the back of the list
	void addBack(const std::string& e);
    
	// insert a new node at a specific position (pos) of the list;
	//	the position should be in range of [0, n], which is 0 <= pos <= n. 
    //  OutOfBoundException	is thrown if index is out of that range
	//	
	//	example: 
	//		A->B
	//			position can be inserted is 0 (before A), 1 (between
	//			A and B), 2 (after B); other positions will cause
	//			OutOfBoundException
	void insert(int pos, const std::string& e) throw (OutOfBoundException);
    
	// remove the front node from the list
	//	EmptyException is thrown if the list is empty
	void removeFront() throw (EmptyException);

	// remove the back node from the list
	//	EmptyException is thrown if the list is empty 
	void removeBack() throw (EmptyException);

	// remove a node at a specific index (index) of the list; the 
	//	index should be in range of [0, n-1], which is 0 <= index <= (n-1)
    //  OutOfBoundException is thrown if index is out of that range; 
    //  EmptyException is thrown if the list is empty.
	//	
	//	example: 
	//		A->B
	//			position can be removed is 0 (A), 1 (B); otherwise 
    //          position will cause OutOfBoundException
	void remove(int index) throw (EmptyException, OutOfBoundException);

	// remove the first node that has a matched element e, starting from 
    // the head node; return true if a match is found, false otherwise
	bool remove(const std::string& e);

	// remove the ALL elements that are matched e; return true if a match 
	// is found, false otherwise
	bool removeAll(const std::string& e);

	// reverse the order of the list
	//	example: 
	//		A->B->C->D
	//			after reverse(), D->C->B->A
	void reverse();
};

#endif

StringLinkedList.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
 
#include "StringLinkedList.h"

// default constructor (COMPLETED)
StringLinkedList::StringLinkedList() 
	: head(NULL), n(0) { }

// destructor (INCOMPLETED)
StringLinkedList::~StringLinkedList() {

}

// return the string representation of the list; each node is seperated by "->"
std::string StringLinkedList::toString() {
    // return blank if the list is empty
	if (head == NULL) 
        return "";

    // traverse to each node and append element of each
    // node to final output string
	std::string out = "";
	StringNode *node = head;
	while (node != NULL) {
		out += node->elem + "->";
		node = node->next;
	}

    // return final string without last "->"
	return out.substr(0, out.size()-2);
}
bool StringLinkedList::empty() const
{return head==NULL;}

const string& StringLinkedList::front() const throw (EmptyException)
{
	if(head==0)throw EmptyException("Empty head");
	return head->elem;
}
void StringLikedList::addFront(const std::string& e)
{
	StringNode* v= new StringNode;
	v->elem=e;
	v->next=head;
	head=v;
}
void StringLinkedList::addBack(const std::string& e)
{
	StringNode* node=head;
	while(node->next!=NULL)
		node=node->next;
	StringNode* v=new StringNode;
	v->elem=e;
	v->next=NULL;
	node->next=v;
}
TheKingOfTyrants (232)
Appears to be fine. Any particular problems you've been running into?
painith (16)
I am just having trouble with the other functions. LIke i dont know how to write them. Here is an update for my cpp file. the header file is the same as above.
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
 
#include "StringLinkedList.h"

// default constructor (COMPLETED)
StringLinkedList::StringLinkedList() 
	: head(NULL), n(0) { }

// destructor (INCOMPLETED)
StringLinkedList::~StringLinkedList()

{
	while(!empty()) removeFront();
}

// return the string representation of the list; each node is seperated by "->"
std::string StringLinkedList::toString() {
    // return blank if the list is empty
	if (head == NULL) 
        return "";

    // traverse to each node and append element of each
    // node to final output string
	std::string out = "";
	StringNode *node = head;
	while (node != NULL) {
		out += node->elem + "->";
		node = node->next;
	}

    // return final string without last "->"
	return out.substr(0, out.size()-2);
}
bool StringLinkedList::empty() const
{return head==NULL;}

const string& StringLinkedList::front() const throw (EmptyException)
{
	if(head==0)throw EmptyException("Empty head");
	return head->elem;
}
const std::string& back() const throw (EmptyException)
{
	if(tail==0)throw EmptyException("empty tail");
	return tail->elem;
}
void StringLikedList::addFront(const std::string& e)
{
	StringNode* v= new StringNode;
	v->elem=e;
	v->next=head;
	head=v;
}
void StringLinkedList::addBack(const std::string& e)
{
	StringNode* node=head;
	while(node->next!=NULL)
		node=node->next;
	StringNode* v=new StringNode;
	v->elem=e;
	v->next=NULL;
	node->next=v;
}
void StingLinkedList::removeFront() throw (EmptyException)
{
	if(head==0) throw EmptyException("empty");
	else
	{
		StringNode* remove;
		remove=head;
		if(head==tail)
		{
			head=NULL;
			tail=NULL;
		}
		else
		{
			head=head->next;
		}
		delete remove;
	}

}


void StringLinkedList::removeBack() throw (EmptyException)
{
	if (tail==0)throw EmptyException("empty");
	else
	{
		StringNode* remove;
		remove=tail;
		if(head==tail)
		{
			head=NULL;
			tail=NULL;
		}
		else 
		{
			StringNode* previousToTail=head;
			while(previousToTail->next !=tail)
				previousToTail=previousToTail->next;
			tail=previousToTail;
			tail->next=NULL;
		}
		delete remove;
	}
}
void StringLinkedList::reverse()
{
	StringNode* tempHead=head;
	StringNode* nodes=NULL;
	StringNode* nextNode=NULL:
	if (head==NULL)
		return;
	tail=head;
	nodes=head->next;
	while(nodes!=NULL)
	{
		nextNode=nodes;
		nodes=nodes->next;
		nextNode->next=tempHead;
		tempHead=nextNode;
	}
	head=tempHead;
	tail->next=NULL;
}
Zhuge (4664)
Which function do you want to start with? Tell us what you are trying and what isn't working.
painith (16)
I need help with these functions:
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
 
// return the number of nodes in the list
	//	note: take advantage of the private member we have, implement this
	//		running with O(1)
int size() const;

// return the element of a node at a specific index (index) of the list
	//	EmptyException is thrown if the list is empty
	//	The index should be in range of [0, n-1], which is 0 <= index <= (n-1)
    //  OutOfBoundException is thrown if index is out of that range
const std::string& get(int index) const throw (EmptyException, OutOfBoundException);

// remove a node at a specific index (index) of the list; the 
	//	index should be in range of [0, n-1], which is 0 <= index <= (n-1)
    //  OutOfBoundException is thrown if index is out of that range; 
    //  EmptyException is thrown if the list is empty.
	//	
	//	example: 
	//		A->B
	//			position can be removed is 0 (A), 1 (B); otherwise 
    //          position will cause OutOfBoundException
void remove(int index) throw (EmptyException, OutOfBoundException);

// remove the first node that has a matched element e, starting from 
 // the head node; return true if a match is found, false otherwise
bool remove(const std::string& e);

// remove the ALL elements that are matched e; return true if a match 
// is found, false otherwise
bool removeAll(const std::string& e);


(The description for each function is commented above the function name)
Zhuge (4664)
Hm. The size() method ought to be really easy, since you have a private member for the size. Have you tried that one?
painith (16)
ok here is an update of cpp file 
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
 
#include "StringLinkedList.h"

// default constructor (COMPLETED)
StringLinkedList::StringLinkedList() 
	: head(NULL), n(0) { }

// destructor (INCOMPLETED)
StringLinkedList::~StringLinkedList()

{
	while(!empty()) removeFront();
}

// return the string representation of the list; each node is seperated by "->"
std::string StringLinkedList::toString() {
    // return blank if the list is empty
	if (head == NULL) 
        return "";

    // traverse to each node and append element of each
    // node to final output string
	std::string out = "";
	StringNode *node = head;
	while (node != NULL) {
		out += node->elem + "->";
		node = node->next;
	}

    // return final string without last "->"
	return out.substr(0, out.size()-2);
}

bool StringLinkedList::empty() const
{return head==NULL;}

int StringLinkedList::size() const
{
	int n = 0;
	while (current != null)
	{
		n++;
		current = current->next;
	}
	return n;
}
const std::string& StringLinkedList::front() const throw (EmptyException)
{
	if(head==0)throw EmptyException("Empty head");
	return head->elem;
}
const std::string& StringLinkedList::back() const throw (EmptyException)
{
	if(tail==0)throw EmptyException("empty tail");
	return tail->elem;
}
const std::string& get(int index) const throw (EmptyException, OutOfBoundException)
{
	int cur_index = 0;
	if (cur_index=NULL) throw EmptyException("empty list");
	if(cur_index>index) throw EmptyException("out of bounds");
	while ((current != null) && (cur_index < index))
	{
		cur_index++;
		current = current->next;
	}
	return current->data;
}

void StringLikedList::addFront(const std::string& e)
{
	StringNode* v= new StringNode;
	v->elem=e;
	v->next=head;
	head=v;
}
void StringLinkedList::addBack(const std::string& e)
{
	StringNode* node=head;
	while(node->next!=NULL)
		node=node->next;
	StringNode* v=new StringNode;
	v->elem=e;
	v->next=NULL;
	node->next=v;
}
void StingLinkedList::removeFront() throw (EmptyException)
{
	if(head==0) throw EmptyException("empty");
	else
	{
		StringNode* remove;
		remove=head;
		if(head==tail)
		{
			head=NULL;
			tail=NULL;
		}
		else
		{
			head=head->next;
		}
		delete remove;
	}

}


void StringLinkedList::removeBack() throw (EmptyException)
{
	if (tail==0)throw EmptyException("empty");
	else
	{
		StringNode* remove;
		remove=tail;
		if(head==tail)
		{
			head=NULL;
			tail=NULL;
		}
		else 
		{
			StringNode* previousToTail=head;
			while(previousToTail->next !=tail)
				previousToTail=previousToTail->next;
			tail=previousToTail;
			tail->next=NULL;
		}
		delete remove;
	}
}
void StringLinkedList::reverse()
{
	StringNode* tempHead=head;
	StringNode* nodes=NULL;
	StringNode* nextNode=NULL:
	if (head==NULL)
		return;
	tail=head;
	nodes=head->next;
	while(nodes!=NULL)
	{
		nextNode=nodes;
		nodes=nodes->next;
		nextNode->next=tempHead;
		tempHead=nextNode;
	}
	head=tempHead;
	tail->next=NULL;
}
dhayden (5795)
The header file in your original post has 
1
2
 
	// size of the list
	int n;

Do you still have that? If so you need to update n in your methods where appropriate.

addFront() needs to set tail if the list is initially empty.
addBack() will crash if the list is empty. This should be easy since you're keeping a tail pointer. If tail != NULL then just append the item to tail and update tail.

removeFront needs to update tail near line 100.

removeBack will fail if there is just one item on the list. Be sure to update head in this case too.

Basically, you need to keep in mind that you have 2 data members: head and tail. You need to think about updating both of them in each method that changes the list. In those methods, consider 3 cases: (1) the list is initially empty (2) the list initially has 1 item and (3) the list initially has 2 or more items.
Topic archived. No new replies allowed.