Skip to content

Instantly share code, notes, and snippets.

@ColdMold
Last active November 7, 2018 21:50
Show Gist options
  • Save ColdMold/679e254371f7d6bc42df85cbd5481894 to your computer and use it in GitHub Desktop.
Save ColdMold/679e254371f7d6bc42df85cbd5481894 to your computer and use it in GitHub Desktop.
C++ List Implementation
#include "Linkedlist.h"
#include <cstdlib>
#include <iomanip>
#include <iostream>
using namespace std;
int main(int argc, char** argv)
{
cout << "1. ---Testing constructor and check function \n";
Linkedlist list(4);
list.check();
list.rcheck();
cout << "--------------------------------------\n\n" ;
cout << "2. ---Testing push front 7 \n";
cout << "before push front: " << endl;
list.check();
list.push_front(7);
list.check();
list.rcheck();
cout << "--------------------------------------\n\n" ;
cout << "3. ---Testing push back -1 \n";
cout << "before push back: " << endl;
list.check();
list.push_back(-1);
list.check();
list.rcheck();
cout << "--------------------------------------\n\n" ;
cout << "4. ---Testing insert 5 at position 2 \n";
cout << "before insert: " << endl;
list.check();
list.insert(2, 5);
list.check();
list.rcheck();
cout << "--------------------------------------\n\n" ;
cout << "5. ---Testing front \n";
cout << list.front() << endl;
cout << "--------------------------------------\n\n" ;
cout << "6. ---Testing back \n";
cout << list.back() << endl;
cout << "--------------------------------------\n\n" ;
cout << "7. ---Testing sort \n";
cout << "before sort: " << endl;
list.check();
list.sort();
list.check();
list.rcheck();
cout << "--------------------------------------\n\n" ;
cout << "7. ---Testing clear and empty \n";
cout << "before clear: " << endl;
list.check();
list.clear();
list.check();
if(list.empty())
{
cout <<"Testing empty function...";
cout <<" It's empty!" << endl;
}
cout << "--------------------------------------\n\n" ;
return 0;
}
#include "Linkedlist.h"
#include <cstdlib>
#include <iostream>
#include <iomanip>
Linkedlist::Linkedlist()
{
head = new Node();
tail = new Node();
head = NULL;
tail = NULL;
}
Linkedlist::~Linkedlist()
{
Node* current = head;
//loop through whole list
while (current != NULL)
{
Node* next = current->next;
delete current;
current = next;
}
//same as constructor here
head = NULL;
tail = NULL;
}
bool Linkedlist::empty() const
{
if(head == tail)
return 1;
else
return 0;
}
void Linkedlist::clear()
{
//same
//as
//destructor
Node* current = head;
while (current != NULL)
{
Node* next = current->next;
delete current;
current = next;
}
head = NULL;
tail = NULL;
}
Linkedlist::reference Linkedlist::back()
{
return tail->elem;
}
Linkedlist::const_reference Linkedlist::back() const
{
return tail->elem;
}
Linkedlist::reference Linkedlist::front()
{
return head->elem;
}
Linkedlist::const_reference Linkedlist::front() const
{
return tail->elem;
}
Linkedlist& Linkedlist::operator=(const Linkedlist& l)
{
if(&l == this)
return *this;
if(head != NULL)
clear();
head = new Node();
tail = new Node();
head->elem = l.head->elem;
head->prev = NULL;
head->next = NULL;
tail = head;
// Create a doubly linked list from the nodes
Node* current = l.head;
int n = 0;
while(current != NULL)
{
n++;
current = current->next;
}
current = l.head->next;
for (int i = 1; i < n; i++)
{
// Create the new node
Node* node = new Node();
node->elem = current->elem;
node->prev = tail;
node->next = NULL;
current = current->next;
// Fold it into the list
tail->next = node;
// Move the tail
tail = node;
}
return *this;
}
void Linkedlist::pop_back()
{
Node * tmp = tail;
tail = tail -> prev;
tail -> next = NULL;
tmp -> next = NULL;
delete tmp;
}
void Linkedlist::pop_front()
{
Node * tmp = head;
head = head -> next;
head -> prev = NULL;
tmp -> next = NULL;
delete tmp;
}
void Linkedlist::push_back(const element_type& x)
{
Node* tmp = new Node();
tmp->elem = x;
tmp->prev = tail;
tmp->next = NULL;
//test if list is empty
if(head == NULL)
head = tmp;
else
{
tail->next = tmp;
tail = tmp;
}
}
void Linkedlist::push_front(const element_type& x)
{
//if list is empty
if(head == NULL)
{
head = new Node();
tail = new Node();
head->elem = x;
head->prev = NULL;
head->next = NULL;
tail = head;
}
else
{
Node* tmp = new Node();
tmp->elem = x;
head->prev = tmp;
tmp->next = head;
head = tmp;
}
}
void Linkedlist::sort()
{
Node * current = head;
Node * smallest = head;
Node * newHead = NULL;
Node * newTail = NULL;
while(head != NULL)
{
smallest = head;
current = head;
while(current != NULL)
{
if(current->elem < smallest->elem)
{
smallest = current;
}
current = current->next;
}
//smallest is first node
if(smallest->prev == NULL)
{
//check if smallest is the ONLY node left
//if it is only node left, head = head->next makes head NULL
// so then head->prev = NULL causes segfault
if(smallest->next == NULL)
{
//break leaves while loops
//which is why you have to add the final node
//outside of the while loops
break;
}
else
{
head = head->next;
head->prev = NULL;
}
}
//smallest is last node
else if(smallest->next == NULL)
{
tail = tail->prev;
tail->next = NULL;
}
//smallest is not first or last node
else
{
smallest->prev->next = smallest->next;
smallest->next->prev = smallest->prev;
}
//adding smallest to a new linked list
if(newHead == NULL)
{
smallest->prev = NULL;
smallest->next = NULL;
newHead = smallest;
newTail = smallest;
}
else
{
smallest->prev = newTail;
smallest->next = NULL;
newTail->next = smallest;
newTail = smallest;
}
}
//add final node to newly sorted list
smallest->prev = newTail;
smallest->next = NULL;
newTail->next = smallest;
newTail = smallest;
//point head and tail to the sorted list
head = newHead;
tail = newTail;
}
Linkedlist::Linkedlist(unsigned int n)
{
head = new Node();
tail = new Node();
head->elem = 0;
head->prev = NULL;
head->next = NULL;
tail = head;
// Create a doubly linked list from the nodes
for (int i = 1; i < n; i++)
{
// Create the new node
Node* node = new Node();
node->elem = i;
node->prev = tail;
node->next = NULL;
// Fold it into the list
tail->next = node;
// Move the tail
tail = node;
}
}
void Linkedlist::check() const
{
Node* current = head;
if (current == NULL)
cout << "It is an empty list!" << endl;
int i = 0;
while (current != NULL)
{
cout << "Node " << setw(3) << i << " "
<< "Elem: " << setw(3) << current->elem << " "
<< "Address: " << setw(8) << current << " "
<< "Next Address: " << setw(8) << current->next << " "
<< "Prev Address: " << setw(8) << current->prev << " "
<< endl;
current = current->next;
i++;
}
cout << "------------------------------------------------------------------------------------------" << endl;
}
void Linkedlist::rcheck() const
{
Node* current = tail;
if (current == NULL)
{
cout << "It is an empty list!" << endl;
}
int i = 0;
while (current != NULL)
{
cout << "Node " << setw(3) << i << " "
<< "Elem: " << setw(3) << current->elem << " "
<< "Address: " << setw(8) << current << " "
<< "Next Address: " << setw(8) << current->next << " "
<< "Prev Address: " << setw(8) << current->prev << " "
<< endl;
current = current->prev;
i++;
}
cout << "------------------------------------------------------------------------------------------" << endl;
}
void Linkedlist::insert(unsigned int pos, const element_type& x)
{
//if inserting at beginning, just push_front
if(pos == 0)
push_front(x);
Node* current = head;
int i = 0;
while(current != NULL)
{
current = current -> next;
i++;
}
//if pos is greater than size of list, just push_back
if(pos > i)
push_back(x);
else
{
Node* tmp = new Node();
tmp->elem = x;
current = head;
for(int j = 1; j <= pos; j++)
{
current = current -> next;
}
tmp->next = current->next;
current->next->prev = tmp;
current->next = tmp;
tmp->prev = current;
}
}
void Linkedlist::erase(unsigned int pos)
{
if(pos == 0)
pop_front();
Node* current = head;
int i = 0;
while(current != NULL)
{
current = current -> next;
i++;
}
if(pos > i)
pop_back();
else
{
current = head;
for(int j = 1; j < pos; j++)
{
current = current -> next;
}
current->prev->next = current->next;
current->next->prev = current->prev;
}
}
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
using namespace std;
typedef int element_type;
class Linkedlist
{
public:
typedef element_type& reference;
typedef const element_type& const_reference;
Linkedlist(); //default constructor for empty list
~Linkedlist(); //destructor to free nodes dynamically created to support the linklist
bool empty() const;
void clear();
reference back();
const_reference back() const;
reference front();
const_reference front() const;
Linkedlist& operator=(const Linkedlist& l);
void pop_back ( );
void pop_front ( );
void push_back ( const element_type& x );
void push_front ( const element_type& x );
void sort ( );
// constructor that initializes the linked list with n nodes,
// with elem value from 0 to n-1
explicit Linkedlist(unsigned int n);
// print the linked list in the forward direction,
// similar to the show function of lab6
void check() const;
// print the linked list in the backward direction,
// similar to the reverse_show function of lab7
void rcheck() const;
// insert a node with value specified by x after the node
// specified by pos. The first node has position 0.
// if the number of nodes in the linked list is less than
// pos, the node is inserted at the end.
void insert(unsigned int pos, const element_type& x);
// remove the node specified by pos.
// if the number of nodes in the linked list is less than
// pos, the node at the end if any is removed.
void erase(unsigned int pos);
private:
struct Node
{
element_type elem; // Data
Node * next; // Pointer to the next node in the chain
Node * prev; // Pointer to the previous node in the chain
};
Node * head;
Node * tail;
};
#endif /* LINKEDLIST_H */
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment