I have created a linked list in C++, I suspect there is a good chance I have made some larger errors in this code as I am working with a few concepts new to me. Please be very hard on me as I want to eventually be good at this.
#include <iostream>
// basic linked list implimentation in C++ using templates
template <class T>
class linkedList
{
public:
linkedList(); //constructor
~linkedList(); //destructor
void push_back(const T &value);
void deleteNodes(const T &value);
void printList();
void reverseList();
void deleteList();
private:
struct _node
{
T val;
linkedList *next;
};
struct _node node ;
linkedList *root = NULL;
};
template<class T>
linkedList<T>::linkedList(){};
template<class T>
linkedList<T>::~linkedList(){};
template<class T>
void linkedList<T>::deleteList()
{
linkedList *t = root;
while (t)
{
t = root->node.next;
delete root;
root = t;
}
}
template<class T>
void linkedList<T>::printList()
{
if(!root) std::cout<<"List is empty"<<std::endl;
else
{
linkedList *t = root;
while (t)
{
std::cout<<t->node.val<<std::endl;
t = t->node.next;
}
}
}
template <class T>
void linkedList<T>::reverseList()
{
linkedList *temp = NULL, *prev = NULL, *current = root;
while (current != NULL)
{
temp = current->node.next;
current->node.next = prev;
prev = current;
current = temp;
}
root = prev;
}
template <class T>
void linkedList<T>::deleteNodes(const T &value)
{
linkedList *prev = NULL, *active = NULL;
if(!root) std::cout<<"List is empty"<<std::endl;
else
{
if (root&& root->node.val == value)
{
linkedList *t = root;
root = t->node.next;
delete t;
}
}
prev = root;
active = root->node.next;
while (active)
{
if (active->node.val == value)
{
prev->node.next = active->node.next;
delete active;
active = prev->node.next;
}
else
{
prev = active;
active = active->node.next;
}
}
}
template<class T>
void linkedList<T>::push_back(const T &value)
{
if (!root)
{
root = new linkedList<T>();
root->node.val = value;
}
else
{
linkedList *ptr = root;
while (ptr->node.next)
{
ptr = ptr->node.next;
}
ptr->node.next = new linkedList<T>();
ptr = ptr->node.next;
ptr->node.val = value;
}
}
int main()
{
linkedList <int> example;
for (int i = 1; i<=20; i++)
example.push_back(i);
example.deleteNodes(20);
example.deleteNodes(1);
example.deleteNodes(10);
example.reverseList();
example.printList();
example.deleteList();
return 0;
}
Compiled with GCC v 4.7.3 on ubuntu 13.04 with the command:
g++ linkedlist.cpp -Wall -std=c++0x -o linkedlist.o
Here is the latest version I have made with the suggested changes. I still need to implement iterators.
#include <iostream>
// basic linked list implementation in C++ using templates
template <class T>
class linkedList
{
public:
~linkedList(); //destructor
void push_back(const T &value);
void delete_nodes(const T &value);
void print_list() const;
void reverse_list();
void clear();
void erase(size_t pos);
private:
struct _node
{
T val;
_node *next;
};
_node *root = NULL;
};
template <class T>
linkedList<T>::~linkedList<T>()
{
clear();
}
template <class T>
void linkedList<T>::clear()
{
struct _node *t =NULL;
while (t)
{
t = root->next;
delete root;
root = t;
}
}
template <class T>
void linkedList<T>::erase(size_t pos)
{
struct _node *current = root;
struct _node *prev = NULL;
size_t i = 0;
while (current != NULL)
{
if (pos == i)
{
struct _node *t = current->next;
prev->next = t;
delete current;
}
++i;
prev = current;
current=current->next;
}
}
template <class T>
void linkedList<T>::reverse_list()
{
struct _node *t = NULL, *prev = NULL, *current = root;
while (current != NULL)
{
t = current->next;
current->next = prev;
prev = current;
current = t;
}
root = prev;
}
template <class T>
void linkedList<T>::delete_nodes(const T &value)
{
struct _node *prev = NULL;
struct _node *active = NULL;
if (root == NULL) return; //list is empty
else
{
if (root != NULL && root->val == value)
{
struct _node *t = root;
root = t->next;
delete t;
}
}
prev = root;
active = root->next;
while (active)
{
if(active->val == value)
{
prev->next = active->next;
delete active;
active = prev->next;
}
else
{
prev = active;
active = active->next;
}
}
}
template <class T>
void linkedList<T>::push_back(const T &value)
{
if (root == NULL)
{
root = new _node;
root->val = value;
}
else
{
struct _node *ptr = root;
while (ptr->next != NULL)
{
ptr = ptr->next;
}
//now ptr is at the last spot in the list
ptr->next = new _node;
ptr = ptr->next;
ptr->val = value;
ptr->next = NULL;
}
}
template <class T>
void linkedList<T>::print_list() const
{
struct _node *t = root;
while (t)
{
std::cout<<t->val<<std::endl;
t = t->next;
}
}
int main()
{
linkedList <int> example;
for (int i = 1; i<=20; i++)
example.push_back(i);
example.delete_nodes(1);
example.delete_nodes(10);
example.delete_nodes(20);
example.erase(2);
example.reverse_list();
example.print_list();
return 0;
}