-
Notifications
You must be signed in to change notification settings - Fork 0
/
list.cc
executable file
·205 lines (183 loc) · 5.27 KB
/
list.cc
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
#include "list.h"
#include <iostream>
using namespace std;
// List node constructors provided by Prof. Campbell
list_node::list_node() : prev(NULL), next(NULL) {}
list_node::list_node(list_node *p, list_node *n) : prev(p), next(n) {}
list_node::list_node(list_node *p, const list_element & d, list_node * n):
prev(p), data(d), next(n) {}
// List constructors/destructor/assignment also provided.
// No need to change these.
list::list()
{
_init();
}
list::~list()
{
_destroy();
}
list::list(const list & orig)
{
_copy(orig);
}
list & list::operator=(const list & rhs)
{
if (this != &rhs) {
_destroy();
_copy(rhs);
}
return *this;
}
// List method stubs provided. Here's where you come in. You delete this
// comment and fill in the method bodies.
// initializes an empty list by creating a front and rear sentinel and
// connecting the two in order to form an empty list.
void list::_init()
{
list_node * sentinel_front = new list_node();
_front = sentinel_front;
list_node * sentinel_rear = new list_node();
_rear = sentinel_rear;
sentinel_front -> next = sentinel_rear;
sentinel_rear -> prev = sentinel_front;
// sets _current to rear sentinel, current index to 0, and size to 0
_current = _rear;
_size = 0;
_current_index = 0;
}
// copy constructor—used to make copies of a list
void list::_copy(const list & orig)
{
// initializes a new list on which to copy the old list
_init();
// copies the data of each individual element of the old list to the new list
for(size_t i = 0; i < orig.size(); i += 1){
// copy only the data, not the node in the old list
list_element data_copy = orig.get(i);
// place data into new node and place node in list
list_node * p = new list_node(_front -> next, data_copy, _rear -> prev);
// adds the first element in the list
if (_front == NULL){
_front -> next = p;
_rear -> next = p;
}
// adds all the elements following the first element
else{
p -> prev = _rear;
_rear -> next = p;
_rear = _rear -> next = p;
}
}
}
// destructor, used to get rid of the list after completion
void list::_destroy()
{
list_node * p = new list_node;
// set p equal to _front and as _front cycles through the list, p gets deleted
while (_front != NULL){
p = _front;
_front = _front -> next;
delete p;
}
}
// get obtains the data in a node by using index by using _set_current_index to
// set _current pointer to the node indicated by index and return the data
list_element list::get(size_t index) const
{
_set_current_index(index);
return _current -> data;
}
// adds element to the list
void list::add(const list_element & item, size_t index)
{
// set _current to index, where you want to place the node
_set_current_index(index);
// create node
list_node * p = new list_node(_current -> prev, item, _current);
// connect node to the list
_current -> prev -> next = p;
_current -> prev = p;
// increase _size by 1
_size = _size + 1;
}
// removes the node at a given index
void list::remove_at(size_t index)
{
// uses _current to find node that you want to remove
_set_current_index(index);
// connect the nodes around _current
_current -> prev -> next = _current -> next;
_current -> next -> prev = _current -> prev;
// delete _current
delete _current;
// decrease _size
_size = _size - 1;
// reset _current to point to the rear sentinel
_set_current_index(_size);
}
// removes the first node containing a given item
void list::remove(const list_element & item)
{
// rotates through list to find item
for (size_t i; i < _size; i += 1){
if (list().get(i) == item){
// removes the item by assigning _current and removing that node while
// reconnecting the adjacent nodes
_set_current_index(i);
_current -> prev -> next = _current -> next;
_current -> next -> prev = _current -> prev;
delete _current;
// decreases size
_size = _size - 1;
_set_current_index(_size);
return;
}
}
}
// finds the node containing a certain item and returns the index.
// if item does not exist, returns _size
size_t list::find(const list_element & item) const
{
for (size_t i = 0; i < _size; i += 1){
if (get(i) == item){
return i;
}
}
return _size;
}
// returns size
size_t list::size() const
{
return _size;
}
// outputs the list by rotating the list with _current
void list::output(std::ostream & ostr) const
{
// sets _current to the first element in the list
_current = _front -> next;
// sets up and prints first item
ostr << '<' << _current -> data;
// rotates through the list and prints each item
while (_current -> next -> next){
_current = _current -> next;
ostr << ", "<< _current -> data;
}
// ends list
ostr << '>';
}
// sets _current to a given index and sets _current_index to index
void list::_set_current_index(size_t index) const
{
// only works if index is less that _size
if (index <= _size){
// sets _current_index to index and sets _current to first element of list
_current_index = index;
_current = _front -> next;
// rotates through list with _current
for (size_t i = 0; i < index; i += 1)
_current = _current -> next;
}
// if _size = 0, set _current to _rear
if (_size == 0)
_current = _rear;
}