C++ File
/*
Linked List
Created: dec 22, 2012
Author: Mathias Beke - http://denbeke.be
*/
#include <iostream>
#include "LinkedList.h"
/*******
* Node *
*******/
Node::Node() {
//Constructor
number = 0;
next = NULL;
}
Node::Node(int value, Node* next_node) {
//Constructor with values
number = value;
next = next_node;
}
/**************
* Linked List *
**************/
LinkedList::LinkedList() {
//Constructor
head = NULL;
length = 0;
}
void LinkedList::insert(int value, int index) {
//Insert element with given 'value' on position 'index'.
//The first element has index 1.
if(index > getLength()+1 || index < 1) {
//ERROR: index out of range
return;
}
else if (getLength() == 0) {
//Insert item on first position in empty list
Node *newNode;
newNode = new Node;
newNode->number = value;
newNode->next = NULL;
head = newNode;
}
else {
//List not empty
if (index == 1) {
//Insert item on first position of 'normal' list
Node *newNode;
newNode = new Node;
newNode->number = value;
newNode->next = head;
head = newNode;
}
else if (index == length+1){
//Insert item on last position
Node *cur = head;
for (int i = 1; i < index-1; i++) {
cur = cur->next;
}
Node *newNode;
newNode = new Node;
newNode->number = value;
newNode->next = NULL;
cur->next = newNode;
}
else {
//Insert item on regular position
Node *prev = head;
Node *cur;
for (int i = 1; i < index-1; i++) {
//Move the 'previous' pointer 'index-2' steps forward
prev = prev->next;
}
cur = prev->next; //Go 1 step forward
Node *newNode;
newNode = new Node;
newNode->number = value;
newNode->next = cur;
prev->next = newNode;
}
}
length++; //Increment length of list
}
void LinkedList::remove(int index) {
//Remove item from Linked List
if (getLength() == 0) {
//ERROR: can't remove item from empty list
return;
}
else if(index > getLength() || index < 1) {
//ERROR: index out of range
return;
}
else {
//List not empty
if (index == 1) {
//Remove first item from list
if (getLength() == 1) {
//Remove first and last item from list
delete head;
head = NULL;
}
else {
//Remove first item where length > 0
Node* cur;
cur = head;
head = head->next;
delete cur;
}
}
else if (index == length){
//Remove item from last position
Node *cur = head->next;
Node *prev = head;
while ( cur->next != NULL ) {
cur = cur->next;
prev = prev->next;
}
prev->next = NULL;
delete cur;
}
else {
//Remove item from regular position
Node *cur = head->next;
Node *prev = head;
for (int i = 1; i < index-1; i++) {
//Move the 'previous' and 'cur' pointer 'index-2' steps forward
cur = cur->next;
prev = prev->next;
}
prev->next = cur->next;
delete cur;
}
}
length--; //Decrement length of list
}
int LinkedList::getLength() {
//Get Length of Linked List
return length;
}
bool LinkedList::isEmpty() {
//Check if Linked List is empty
return getLength() == 0;
}
int LinkedList::retrieve(int index) {
//Retrieve value on position 'index'
Node *cur = head;
for (int i = 1; i < index; i++) {
//Move index-1 steps forward
cur = cur->next;
}
return cur->number;
}
void LinkedList::print() {
//Print Linked List
int counter = 1;
for (int i = 1; i < getLength()+1; i++) {
std::cout << counter << ". " << retrieve(i) << std::endl;
counter++;
}
}
LinkedList::~LinkedList() {
//Destructor
while ( !isEmpty() ) {
remove(1);
}
std::cout << "Destruction List" << std::endl;
print();
}
int main() {
/****************************
* Test Data for Linked List *
****************************/
std::cout << "Testing Linked List" << std::endl;
std::cout << "___________________" << std::endl;
std::cout << std::endl;
LinkedList list;
std::cout << "Linked List Empty? " << list.isEmpty() << std::endl;
list.insert(11,1);
list.insert(19,1);
list.insert(3,3);
list.insert(5,4);
list.insert(9,5);
list.insert(21,6);
list.insert(15,7);
list.insert(50,8);
std::cout << std::endl;
std::cout << "insert(11,1)" << std::endl;
std::cout << "insert(19,1)" << std::endl;
std::cout << "insert(3,3)" << std::endl;
std::cout << "insert(5,4)" << std::endl;
std::cout << "insert(9,5)" << std::endl;
std::cout << "insert(21,6)" << std::endl;
std::cout << "insert(15,7)" << std::endl;
std::cout << "insert(50,8)" << std::endl;
std::cout << std::endl;
std::cout << "Item on first position: " << list.retrieve(1) << std::endl;
std::cout << "Item on second position: " << list.retrieve(2) << std::endl;
std::cout << "Length: " << list.getLength() << std::endl;
std::cout << "Linked List Empty? " << list.isEmpty() << std::endl;
std::cout << std::endl << "Current Linked List" << std::endl;
list.print();
std::cout << std::endl << "Remove(1) " << std::endl;
list.remove(1);
list.print();
std::cout << std::endl << "Remove(3) " << std::endl;
list.remove(3);
list.print();
std::cout << std::endl << "Remove(2) " << std::endl;
list.remove(2);
list.print();
std::cout << std::endl << "Remove(5) " << std::endl;
list.remove(4);
list.print();
}
Header file
/*
Linked List
Created: dec 22, 2012
Author: Mathias Beke - http://denbeke.be
*/
class Node {
//Class Node
public:
int number;
Node* next;
Node();
Node(int, Node*);
};
class LinkedList {
//Class Linked List
Node* head;
int length;
public:
LinkedList();
void insert(int, int);
void remove(int);
int retrieve(int);
void print();
int getLength();
bool isEmpty();
~LinkedList();
};