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
| #include<iostream>
using namespace std;
template<class T>class List
{
// Attributes
public:
// Implementation
List()
{
// initializes the list object for the first time
_first_node = NULL;
_number_of_nodes = 0;
}
~List();
class invalid_position {};
class out_of_memory {};
// supported exceptions
int get_number_of_items() const;
// returns the list size
// Operations
void add(T* item);
// add the specified item at the end of list
void add(int at_position, T* item);
// add the specified item at specified position
void remove(int at_position);
// remove and deletes the item stored at specified position
T* get_item(int at_position);
// returns the item stored at specified position
protected:
class T_Node
{
public:
T_Node(T* item, T_Node* next_node)
{
_item = item;
_next_node = next_node;
}
~T_Node()
{
delete _item;
}
T* _item;
T_Node* _next_node;
};
public:
// this class is used internally to implement a single linked list
T_Node* _first_node;
// first node of the linked list
int _number_of_nodes;
// number of items stored in list
T_Node* find_node(int node_position) ;
// helper function to retrieve an indexed node
};
template<class T>List::~List()
{
// deletes all stored items
while (_number_of_nodes > 0)
remove(0);
}
template<class T>inline int List::get_number_of_items()
{
// returns list size
return _number_of_nodes;
}
template<class T>inline void List::add(T* item)
{
// adds an item at list tail
add(_number_of_nodes, item);
}
template <class T> void List::add(int at_position, T* item)
{
// adds an item at specified position
// throws an out_of_memory exception in case of low system resources
// or an invalid_position if insertion at specified position is
// impossible
if (at_position == 0)
{
_first_node = new T_Node(item, NULL);
if (_first_node == NULL)
throw out_of_memory();
}
else
{
T_Node* previous_node = find_node(at_position - 1);
// NOTE: find_node() can throw an invalid_position exception
T_Node* next_node = previous_node->_next_node;
previous_node->_next_node = new T_Node(item, next_node);
if (previous_node->_next_node == NULL)
throw out_of_memory();
}
_number_of_nodes++;
}
template <class T> void List::remove(int at_position)
{
// removes and deletes the item indexed by the at_position value
// throws an invalid_position if no item is available at specified
// position
T_Node* node_to_delete;
if (at_position == 0)
{
node_to_delete = _first_node;
_first_node = node_to_delete->_next_node;
}
else
{
T_Node* previous_node = find_node(at_position - 1);
// NOTE: find_node() can throw an invalid_position exception
node_to_delete = previous_node->_next_node;
previous_node->_next_node = node_to_delete->_next_node;
}
delete node_to_delete;
_number_of_nodes--;
}
template<class T> inline T* List::get_item(int at_position) const
{
// returns the requested item
// throws an invalid_position if no item is available at specified
// position
T_Node* node = find_node(at_position);
return node->_item;
}
template <class T>List::T_Node* List::find_node(int node_position) const
{
// searches (by index) a node in the internal single linked list
// throws an invalid_position exception if no item found
if (node_position < 0)
throw invalid_position();
T_Node* node = _first_node;
int node_index = 0;
while (node_index < node_position)
{
if (node == NULL)
throw invalid_position();
node = node->_next_node;
node_index++;
}
return node;
}
int main()
{
} |
