-
-
Save ColdMold/679e254371f7d6bc42df85cbd5481894 to your computer and use it in GitHub Desktop.
C++ List Implementation
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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; | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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