# Smart Array (Linked List template implementation using C++)

As we have discussed about the Smart Array (Linked List) in our previous post and showed the Node class as well as the header file for the linked list. Below is the actual implementation of Linked List template in C++.

Any questions welcomed!

#include “list.h”

template <class T>

// in constructor we add a head node in the class as well as the cursor which we called current node.

// head node and current node set to null as there are no other nodes to point to.

List<T>::List()

{

headNode = new Node<T>();

headNode->setNext(NULL);

headNode->setLast(NULL);

currentNode = NULL;

size = 0;

}

//in destructor we do memory management as we did made nodes dynamically.

template <class T>

List<T>::~List ()

{

while (size != 0)

{

remove_node();

}

delete currentNode;

delete headNode;

}

// this function simply call remove_node function until all nodes are deleted.

template <class T>

bool List<T>::clear_list ()

{

while (size != 0)

{

remove_node ();

}

delete currentNode;

}

// this is the main addition of a node function.

template <class T>

void List<T>::add (T addObject)

{

Node<T> *newNode = new Node<T>();

newNode->set(addObject);

size ++;

if(currentNode != NULL) // in case we already have other nodes in the list

{

lastNode = currentNode;

newNode->setNext(currentNode->getNext()); // pointer will be adjusted for the new node.

if (newNode->getNext()!= NULL) // if the node is not at the end of the list.

{

currentNode = currentNode->getNext();

currentNode->setLast(newNode);

}

newNode->setLast(lastNode);

currentNode = newNode;

lastNode->setNext(newNode);

newNode->setIndex(size);

}

else // if this the very first node to be added in the list. this else part will be executed once in the life span of list.

{

newNode->setNext(NULL);

headNode->setNext(newNode);

newNode->setLast(headNode);

currentNode = newNode;

newNode->setIndex(size);

}

}

// this function return the current node value.

template <class T>

T List<T>::get()

{

if (currentNode != NULL)

{

return currentNode->get();

}if (currentNode == headNode) // if cursor is pointing towards head node. we cannot return anything as head node doesn’t

// have any value.

{

return false;

}

}

// move the cursor to next node only if the cursor is not reached on the last node.

template <class T>

bool List<T>::move_next()

{

if (currentNode->getNext() == NULL) return false ;

currentNode = currentNode->getNext();

}

//move the cursor to backwards only if the cursor is not reached till head node.

template <class T>

bool List<T>::move_back ()

{

if (currentNode->getLast() == headNode) return false;

currentNode = currentNode->getLast();

}

//move the cursor to very first node after head node, if there are any nodes in the list.

template <class T>

bool List<T>::move_first()

{

if (headNode->getNext()!=NULL)

currentNode = headNode->getNext();

}

//move the cursor to last node.

template <class T>

bool List<T>::move_last()

{

while (currentNode->getNext() != NULL)

{

currentNode= currentNode->getNext();

}

return currentNode;

}

//delete current node where cursor pointing to.

template <class T>

bool List<T>::remove_node()

{

Node<T> *temp = currentNode;

if (currentNode != NULL) // if cursor is actually pointing to a valid node

{

if (currentNode->getLast() == headNode) // if cursor is on the very first node after head node.

{

currentNode = headNode;

currentNode->setNext(NULL);

currentNode->setLast(NULL);

delete temp;

size–;

return true;

}else if (currentNode->getNext() == NULL) //if cursor is pointing to the very last node of the list.

{

move_back();

currentNode->setNext(NULL);

delete temp;

size–;

return true;

}else // if the cursor is not at the start or end of the list but somewhere in the middle.

{

move_back();

currentNode->setNext(temp->getNext());

move_next();

currentNode->setLast(temp->getLast());

delete temp;

size–;

return true;

}

}

}

//move the cursor to next node.

template <class T>

Node<T> List<T>::operator++()

{

move_next();

return *currentNode;

}

//move theh cursor to last node.

template <class T>

Node<T> List<T>::operator–()

{

move_back();

return *currentNode;

}

// add one node and assign rvalue to it. the name of list instance is used as lvalue.

template <class T>

Node<T> List<T>::operator=(T i)

{

add(i);

}

//cout object can be used to display list values.

template <class T>

std::ostream& operator << (std::ostream& leftOpr, List<T>& rhs)

{

leftOpr << rhs.get();

return leftOpr;

}

//cin can be used to add one node and assign it a value directing getting input from user.

template <class T>

std::istream& operator >> (std::istream& leftOpr, List<T>& rhs)

{

int i = 0;

leftOpr >> i;

rhs.add(i);

return leftOpr;

}

//return size of the list. number of nodes in the list.

template <class T>

int List<T>::get_size()

{

return size;

}

//return node value by index.

template <class T>

Node<T> List<T>::return_node(int i)

{

move_first();

while (currentNode->getNext() != NULL)

{

if (currentNode->getIndex() == i)

return *currentNode;

else

move_next();

}

}

//brackets can be used to access list elements by giving index as used in simple array.

template <class T>

Node<T> List<T>::operator[](int i)

{

return_node(i);

}

###### Related articles

- Data Structures implemantation in C++ (alikhuram.wordpress.com)
- Intersecting Linked Lists Faster (twistedoakstudios.com)
- doublelinkedBag (daniweb.com)

Posted on March 27, 2013, in A library re-written., C++, Data Structures and tagged Array List, C++, DataStructure, Linked list, Operator overloading. Bookmark the permalink. 4 Comments.

I’m just writing to let you understand of the exceptional experience my cousin’s girl enjoyed visiting your web page. She came to understand too many details, including how it is like to possess an excellent giving style to make folks without difficulty completely grasp certain grueling topics. You actually exceeded her expected results. I appreciate you for delivering those warm and helpful, healthy, educational and even cool thoughts on the topic to Lizeth.

I’m truly enjoying the design and layout of your site.

It’s a very easy on the eyes which makes it much more pleasant foor me

to come her and viisit more often. Did you hire out a

developer to create your theme? Great work!

Generally I don’t read post on blogs, but I would

like to say that this write-up very pressured me to

try and do it! Your writing taste has been surprised me.

Thanks, quite nice post.

Fantastic goods from you, man. I have take into account your stuff previous to and you are just too great.

I actually like what you’ve bought right here, certainly

like what you are saying and the best way by which you assert it.

You make it enjoyable and you continue to care for to keep it wise.

I can’t wait to learn much more from you. That is actually a terrific site.