I'm making an unrolled linked list (linked list with an array of 50 in each Node) for a class project with an iterator. In addition, whenever more than half of the arrays are unused (they would all be at the end of the chain), I should deallocate half the unused arrays. Please review!
#ifndef _CDAL_H_
#define _CDAL_H_
#include <iostream>
#include <stdexcept>
#include <cstddef>
namespace COP3530 {
template <class T>
class CDAL {
private:
struct Node {
int array_size = 0; //Array 's current number of items
T *array; //Pointer to Node's array
Node *next = NULL; //Defines the pointer that this node is pointing to
Node() { //Node constructor
array = new T[50]; //Dynamically allocates a new array of size 50
}
~Node() { //Array destructor
delete[] array;
}
};
//---------------------------------------------------------------------------------------------------------------------------------------------------------
size_t nodeCount() const {
if(head == NULL) {
return 0;
}
else {
int nodeCount = 0;
Node * currentNode = head;
while(currentNode != NULL) {
++nodeCount;
currentNode = currentNode->next;
}
return nodeCount;
}
}
Node * lastNode() const {
Node * currentNode = head; //Set Current node as head to traverse
int nodeNum = size() / 50; //finds last node number to go to
if(size() % 50 == 0) { //makes it so it doesnt go past node number
--nodeNum;
}
for(int i = 0; i < nodeNum; ++i) { //Traverses to node number with last element
currentNode = currentNode->next;
}
return currentNode;
}
void cleanup() {
int usedNodes = size() / 50;
int un_usedNodes = nodeCount() - usedNodes;
if(un_usedNodes > usedNodes) {
int finalUsedNode = un_usedNodes / 2;
int nodeNum = size() / 50;
if(size() % 50 == 0) {
--nodeNum;
}
nodeNum += finalUsedNode;
Node * currentNode = head;
for(int i = 0; i < nodeNum; ++i) {
currentNode = currentNode->next;
}
tail = currentNode;
currentNode = currentNode->next;;
Node * next = NULL;
while(currentNode != NULL) {
next = currentNode->next;
delete currentNode;
currentNode = NULL;
currentNode = next;
}
tail->next = NULL;
}
}
Node *head = NULL; //Head node
Node *tail = NULL; //Tail node
//---------------------------------------------------------------------------------------------------------------------------------------------------------
public:
class CDAL_Iter : public std::iterator<std::forward_iterator_tag, T>
{
public:
typedef T value_type;
typedef std::ptrdiff_t difference_type;
typedef T& reference;
typedef T* pointer;
typedef std::forward_iterator_tag iterator_category;
typedef CDAL_Iter self_type;
typedef CDAL_Iter& self_reference;
private:
Node * currentNode; //Stores the Node the iterator is currently on
int currentIndex;
public:
explicit CDAL_Iter( Node* start, int index) : currentNode( start ), currentIndex( index ) {} //Constructor which sets current node to beginning of list
CDAL_Iter( const CDAL_Iter& src ) : currentNode( src.currentNode ), currentIndex( src.currentIndex) {} //copy constructor
reference operator*() const { //overloaded operator for access to current iterators contents
return currentNode->array[currentIndex];
}
pointer operator->() const {
return &(currentNode->array[currentIndex]);
}
self_reference operator=( const CDAL_Iter& src ) { //overloaded operator for copy assignment
this->currentNode = src.currentNode;
this->currentIndex = src.currentIndex;
return *this;
}
self_reference operator++() { // preincrements iterator
++currentIndex;
if(currentIndex % 50 == 0) {
currentNode = currentNode->next;
currentIndex = 0;
}
return *this;
}
self_type operator++(int) { // postincrements iterator
self_type temp (*this);
++(*this);
return temp;
}
bool operator==(const CDAL_Iter& rhs) const { //checks two iterators for equality
if(this->currentNode == rhs.currentNode && this->currentIndex == rhs.currentIndex) {
return true;
}
else {
return false;
}
}
bool operator!=(const CDAL_Iter& rhs) const { //checks two iterators for inequality
if(this->currentNode == rhs.currentNode && this->currentIndex == rhs.currentIndex) {
return false;
}
else {
return true;
}
}
}; // end CDAL_Iter
class Const_CDAL_Iter : public std::iterator<std::forward_iterator_tag, T>
{
public:
typedef T value_type;
typedef std::ptrdiff_t difference_type;
typedef T& reference;
typedef T* pointer;
typedef std::forward_iterator_tag iterator_category;
typedef Const_CDAL_Iter self_type;
typedef Const_CDAL_Iter& self_reference;
private:
Node * currentNode; //Stores the Node the iterator is currently on
int currentIndex;
public:
explicit Const_CDAL_Iter( Node* start, int index) : currentNode( start ), currentIndex( index ) {} //Constructor which sets current node to beginning of list
Const_CDAL_Iter( const Const_CDAL_Iter& src ) : currentNode( src.currentNode ), currentIndex( src.currentIndex) {} //copy constructor
reference operator*() const { //overloaded operator for access to current iterators contents
return currentNode->array[currentIndex];
}
pointer operator->() const {
return &(currentNode->array[currentIndex]);
}
self_reference operator=( const CDAL_Iter& src ) { //overloaded operator for copy assignment
this->currentNode = src.currentNode;
this->currentIndex = src.currentIndex;
return *this;
}
self_reference operator++() { // preincrements iterator
++currentIndex;
if(currentIndex % 50 == 0) {
currentNode = currentNode->next;
currentIndex = 0;
}
return *this;
}
self_type operator++(int) { // postincrements iterator
self_type temp (*this);
++(*this);
return temp;
}
bool operator==(const Const_CDAL_Iter& rhs) const { //checks two iterators for equality
if(this->currentNode == rhs.currentNode && this->currentIndex == rhs.currentIndex) {
return true;
}
else {
return false;
}
}
bool operator!=(const Const_CDAL_Iter& rhs) const { //checks two iterators for inequality
if(this->currentNode == rhs.currentNode && this->currentIndex == rhs.currentIndex) {
return false;
}
else {
return true;
}
}
}; // end Const_CDAL_Iter
typedef std::size_t size_type;
typedef T value_type;
typedef CDAL_Iter iterator;
typedef Const_CDAL_Iter const_iterator;
iterator begin() { return CDAL_Iter( head, 0 ); } //returns iterator to beginning of list
iterator end() { return CDAL_Iter( lastNode(), size() % 50 ); } //returns iterator (pointer) to end of list
const_iterator begin() const { return Const_CDAL_Iter( head, 0 ); } //returns const iterator (pointer) to beginning of list
const_iterator end() const { return Const_CDAL_Iter( lastNode(), size() % 50 ); } //returns const iterator (pointer) to end of list
CDAL() {}
CDAL(const CDAL& src ) {
for(int i = 0; i < src.size(); ++i) { // populate this CDAL with copies of the other CDAL's contents
this->push_back(src.item_at(i));
}
}
~CDAL() {
if(!is_empty()) {
clear();
}
}
CDAL& operator=(const CDAL& rhs) {
if ( &rhs == this ) // check for self-assignment
return *this; // do nothing
this->~CDAL(); // safely dispose of this CDAL's contents
for(int i = 0; i < rhs.size(); ++i) { // populate this CDAL with copies of the other CDAL's contents
this->push_back(rhs.item_at(i));
}
return *this;
}
T replace(const T& element, int position) {
if(position>= size() || position < 0 || is_empty()) { //If invalid position, throws exception
throw std::domain_error("not a valid position!");
}
else {
int nodeNum = position / 50; //Position of node to insert at
int index = position % 50; //Position of index in node to insert at
Node * currentNode = head;
for(int i = 0; i < nodeNum; ++i) { //Traverse the node until desired node is reached
currentNode = currentNode->next;
}
T temp = currentNode->array[index];
currentNode->array[index] = element;
return temp;
}
}
void insert(const T& element, int position) {
if(position> size() || position < 0) { //If invalid position, throws exception
throw std::domain_error("not a valid position!");
}
else if(position == size()) { //If position equals size, append to end of list
push_back(element);
}
else {
int nodeNum = position / 50; //Position of node to remove from
int index = position % 50; //Position of index in remove at
Node * currentNode = head;
for(int i = 0; i < nodeNum; ++i) { //Navigates to node to insert to
currentNode = currentNode->next;
}
if(currentNode->array_size < 50) { //If there's space on the array to shift, do so
for(int i = currentNode->array_size-1; i >= index; --i) {
std::swap(currentNode->array[i+1], currentNode->array[i]); //Shift elements up the list
}
currentNode->array[index] = element; //Inserts new element into desired position
++currentNode->array_size; //Increase size of list
}
else { //If there is not space in current node to shift, spill over into next nodes
T last = currentNode->array[49]; //Save last element of array as temp to spill over to next node
for(int i = currentNode->array_size-1; i >= index; --i) {
std::swap(currentNode->array[i+1], currentNode->array[i]); //Shift elements up the list
}
currentNode->array[index] = element; //Inserts new element into desired position
int finishNode = (size()/50) - nodeNum; //Finds all elements to right of deleted position, and shifts to left
if(size() % 50 == 0) {
--finishNode;
}
for(int c = 0; c < finishNode; ++c) {
currentNode = currentNode->next;
T newLast = currentNode->array[49];
for(int i = currentNode->array_size-1; i >= 0; --i) {
std::swap(currentNode->array[i+1], currentNode->array[i]); //Shift elements up the list
}
currentNode->array[0] = last;
last = newLast;
}
if(currentNode->array_size != 50 ) {
++currentNode->array_size;
}
else {
if(currentNode->next == NULL) {
tail->next = new Node();
tail = tail->next;
tail->array[0] = last;
++tail->array_size;
}
else {
currentNode = currentNode->next;
currentNode->array[0] = last;
++currentNode->array_size;
}
}
}
}
}
void push_front(const T& element) {
if(head == NULL) {
head = new Node();
tail = head;
head->array[head->array_size] = element;
++head->array_size;
}
else {
insert(element, 0);
}
}
void push_back(const T& element) { //Appends element to last position
if(head == NULL) {
head = new Node(); //If head is NULL, sets head to a new node with array sized 50
tail = head;
head->array[0] = element;
++head->array_size; //Increases Head nodes array size
}
else if(size() == 0 && nodeCount() != 0) {
head->array[0] = element;
++head->array_size;
}
else if(size() % 50 == 0) { //If at end of current nodes array and no space for more, add new node to tail
int nodeNum = size() / 50;
--nodeNum;
Node * currentNode = head;
for(int i = 0; i < nodeNum; ++i) { //Traverse the node until desired node is reached
currentNode = currentNode->next;
}
if(currentNode->next != NULL) {
currentNode->next->array[0] = element;
++currentNode->next->array_size;
}
else {
currentNode->next = new Node();
tail = currentNode->next;
tail->array[0] = element;
++tail->array_size;
}
}
else {
int nodeNum = size() / 50; //Position of node to append to
Node * currentNode = head;
for(int i = 0; i < nodeNum; ++i) { //Traverse the node until desired node is reached
currentNode = currentNode->next;
}
currentNode->array[currentNode->array_size] = element; //Adds element
++currentNode->array_size;
}
}
T pop_front() {
T temp = remove(0);
cleanup();
return temp;
}
T pop_back() {
if(is_empty()) {
throw std::out_of_range("List is empty, cannot remove from back"); //If list empty, cannot remove any elements
}
else {
Node * currentNode = head; //Set Current node as head to traverse
int nodeNum = size() / 50; //finds last node number to go to
if(size() % 50 == 0) { //makes it so it doesnt go past node number
--nodeNum;
}
for(int i = 0; i < nodeNum; ++i) { //Traverses to node number with last element
currentNode = currentNode->next;
}
T temp = currentNode->array[currentNode->array_size];
--currentNode->array_size;
cleanup();
return temp;
}
}
T remove (int position) {
if(position>= size() || position < 0) { //If invalid position, throws exception
throw std::domain_error("not a valid position!");
}
else if(is_empty()) {
throw std::out_of_range("list already empty!");
}
else if(position == size() - 1) {
T temp = pop_back();
cleanup();
return temp;
}
else {
int nodeNum = position / 50; //Position of node to remove from
int index = position % 50; //Position of index in remove at
Node * currentNode = head;
for(int i = 0; i < nodeNum; ++i) { //Navigates to node to remove from
currentNode = currentNode->next;
}
T temp = currentNode->array[index]; //Stores element to be delete into a temporary variable
for(int i = index; i < currentNode->array_size-1; ++i) { //Shifts elements in array in node to the left
std::swap(currentNode->array[i+1], currentNode->array[i]);
}
if(currentNode->next == NULL || currentNode->next->array_size == 0) {
--currentNode->array_size;
}
else {
int finishNode = (size() - 1 - position) / 50; //Finds all elements to right of deleted position, and shifts to left
for(int c = 0; c < finishNode-1; ++c) {
currentNode->array[49] = currentNode->next->array[0];
currentNode = currentNode->next;
for(int i = 0; i < currentNode->array_size-1; ++i) { //Shifts elements in array to the left
std::swap(currentNode->array[i+1], currentNode->array[i]);
}
}
currentNode->array[49] = currentNode->next->array[0];
for(int i = 0; i < currentNode->next->array_size; ++i) {
std::swap(currentNode->next->array[i+1], currentNode->next->array[i]);
}
--currentNode->next->array_size;
}
cleanup();
return temp;
}
}
T item_at(int position) const {
if(position>= size() || position < 0 || is_empty()) { //If invalid position, throws exception
throw std::domain_error("not a valid position!");
}
else {
int nodeNum = position / 50; //Position of node to insert at
int index = position % 50; //Position of index in node to insert at
Node * currentNode = head;
for(int i = 0; i < nodeNum; ++i) { //Traverse the node until desired node is reached
currentNode = currentNode->next;
}
T temp = currentNode->array[index];
return temp;
}
}
bool is_empty() const { //Returns true if list is empty, else false
return (size() == 0);
}
size_type size() const { //Returns number of items in list
if(head == NULL) {
return 0;
}
else {
int count = 0;
Node * currentNode = head;
while(currentNode != NULL) {
for(int j = 0; j < currentNode->array_size; ++j) {
++count;
}
currentNode =currentNode->next;
}
return count;
}
}
void clear() {
if(head == NULL) {
return;
}
Node * currentNode = head;
Node * next = NULL;
while(currentNode != NULL) {
next = currentNode->next;
delete currentNode;
currentNode = NULL;
currentNode = next;
}
head = NULL;
tail = NULL;
}
bool contains(const T& element, bool (*fpr)(const T& a,const T& b)) const {
bool ans = false;
Node * currentNode = head;
while(currentNode != NULL) {
for(int j = 0; j < currentNode->array_size; ++j) {
ans = fpr(element, currentNode->array[j]);
if(ans) {
return true;
}
}
currentNode =currentNode->next;
}
return false;
}
std::ostream& print(std::ostream& out) { //Prints out all items in list
if(is_empty()) {
out << "<empty list>";
}
else if(size() == 1) {
out << "<[" << head->array[0] << "]>";
}
else {
Node * currentNode = head;
out << "<" << "[" << currentNode->array[0];
int set = 0;
if(size() >= 1) {
while(currentNode != NULL) {
for(int j = 0; j < currentNode->array_size; ++j) {
if(set == 0) {
j = 1;
++ set;
}
out << "," << currentNode->array[j];
}
currentNode =currentNode->next;
}
}
out << "]>";
}
return out;
}
T operator[](const int index) {
return item_at(index);
}
};
}
#endif
