list.cpp (Linked list code)
#include <iostream>
#include <cassert>
using namespace std;
class Node {
public:
double value;
Node* pnext;
};
class List {
public:
Node* first;
int count;
};
// return a pointer to the i'th node
Node* node_at(List* list, int i)
{
assert(i < list->count);
Node* n = list->first;
for(int j = 0; j < i; j++)
{
n = n->pnext;
}
return n;
}
double val_at(List* list, int i)
{
return (node_at(list, i))->value;
}
// add a new node at the beginning of a list
void insert_front(List* list, double value)
{
Node* n = new Node;
n->value = value;
n->pnext = list->first;
list->first = n;
list->count++;
}
// add a new node to the end of the list
void push_back(List* list, double value)
{
if(list->count == 0)
{
insert_front(list, value);
}
else
{
Node* n = new Node;
n->value = value;
Node* nlast = node_at(list, list->count - 1);
nlast->pnext = n;
list->count++;
}
}
// insert a new node before the i'th node in the list
void insert_before(List* list, int i, double value)
{
// don't bother if i is too small or too large
if(i < 0 || i > list->count) return;
if(i == 0)
{
Node* n = new Node;
n->value = value;
n->pnext = list->first;
list->first = n;
list->count++;
}
else
{
Node* n = node_at(list, i-1);
Node* n2 = new Node;
n2->value = value;
n2->pnext = n->pnext;
n->pnext = n2;
list->count++;
}
}
void remove_at(List* list, int i)
{
if(i < 0 || i >= list->count) return;
if(i == 0)
{
Node* toDelete = list->first;
list->first = toDelete->pnext;
delete toDelete;
list->count--;
}
else
{
Node* prev = node_at(list, i-1);
Node* toDelete = prev->pnext;
prev->pnext = toDelete->pnext;
delete toDelete;
list->count--;
}
}
// print all the values
void print_list(List* list)
{
cout.precision(1);
cout.setf(ios::fixed, ios::floatfield);
cout << "{";
Node* n = list->first;
for(int i = 0; i < list->count; i++)
{
cout << n->value;
if(i < (list->count - 1))
{
cout << ", ";
}
n = n->pnext;
}
cout << "}" << endl;
}
// free up all the memory used by the list
void delete_list(List* list)
{
Node* n = list->first;
Node* n2;
for(int i = 0; i < list->count; i++)
{
n2 = n;
n = n->pnext;
delete n2;
}
list->count = 0;
}
int main()
{
List* mylist = new List;
mylist->count = 0;
cout << "empty list: ";
print_list(mylist);
cout << "insert front 7.3: ";
insert_front(mylist, 7.3);
print_list(mylist);
cout << "insert 1.2 before position 0: ";
insert_before(mylist, 0, 1.2);
print_list(mylist);
cout << "insert 9.3 before position 1: ";
insert_before(mylist, 1, 9.3);
print_list(mylist);
cout << "delete list, then print: ";
delete_list(mylist);
print_list(mylist);
cout << "add 4.0, 3.0 to front, 5.0 to back: ";
insert_front(mylist, 4.0);
insert_front(mylist, 3.0);
push_back(mylist, 5.0);
print_list(mylist);
cout << "val_at(0): " << val_at(mylist, 0) << endl;
cout << "val_at(1): " << val_at(mylist, 1) << endl;
cout << "add 2.0 to front, 6.0 to back: ";
insert_front(mylist, 2.0);
push_back(mylist, 6.0);
print_list(mylist);
cout << "insert 4.5 before position 3: ";
insert_before(mylist, 3, 4.5);
print_list(mylist);
cout << "insert 0.0 before position 6 (i.e., at end): ";
insert_before(mylist, 6, 0.0);
print_list(mylist);
cout << "remove_at(0): ";
remove_at(mylist, 0);
print_list(mylist);
cout << "remove_at(2): ";
remove_at(mylist, 2);
print_list(mylist);
cout << "remove_at(4) (i.e., remove end): ";
remove_at(mylist, 4);
print_list(mylist);
cout << "remove_at(-1) (should do nothing): ";
remove_at(mylist, -1);
print_list(mylist);
cout << "remove_at(2): ";
remove_at(mylist, 2);
print_list(mylist);
cout << "delete list, then print: ";
delete_list(mylist);
print_list(mylist);
return 0;
}
CSE 2122 material is licensed under a Creative
Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License.
Source code for this website available at GitHub.