Friday, October 11, 2013

I need single linked list implementation using templates in c++. it should have basic functions including swap(), append(), display(),delete().addatbeg() and addafter()?

// This program demonstrates the linked list template in c++.
#include <iostream.h>
#include "LinkedList.h"

void main(void)
{
LinkedList<int> list;
int a,b,position;

// Build the list
list.appendNode(2);
list.appendNode(4);
list.appendNode(6);
cout << "Here are the initial values:\n";
list.displayList();
cout << endl;
cout << "Now inserting the value 5.\n";
list.insertNode(5);
cout << "Here are the nodes now.\n";
list.displayList();
cout << endl;

cout << "Now deleting the last node.\n";
list.deleteNode(6);
cout << "Here are the nodes left.\n";
list.displayList();

cout<<"adding at begining";
list.addatbeg(18);
cout << "Here are the modified values:\n";
list.displayList();

cout<<"**********INSERTING ELEMENT AFTER SOME GIVEN NODE***********************";
cout<<endl;
cout<<"Enter the element to be inserted after some given node:";
cin>>a;

cout<<"Enter the position after which this element is inserted: ";
cin>>position;
list.addafter(a,position);


cout << "Here are the modified values:\n";
list.displayList();

cout<<"***************VISITING DATA OF SOME PARTICULAR NODE*********************";
cout<<endl;
cout<<"enter node no, whose data you want to visit";
cin>>a;
list.displayatnode(a);

cout<<"****************SWAPPING*************";
cout<<endl;
cout<<"enter nodes for which you want to swap data:";
cin>>a;
cout<<endl;
cin>>b;
list.swap(a,b);
cout<<"displaying after swapping"<<endl;
list.displayList();


}

//LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

template <class T>
class LinkedList
{
private:
// Declare a structure for the list
struct ListNode
{
T value;
struct ListNode *next;
};

ListNode *head;// List head pointer

public:

LinkedList(void)

// Constructor

{ head = NULL; }
~LinkedList(void); // Destructor
void appendNode(T);
void insertNode(T);
void deleteNode(T);
void displayList(void);
void addatbeg(T);
void addafter(T,T);
void displayatnode(int);
void swap(int,int);
};
// appendNode appends a node containing the
// value passed into num, to the end of the list.

template <class T>
void LinkedList<T>::appendNode(T num)
{
ListNode *newNode, *nodePtr;

// Allocate a new node & store num
newNode = new ListNode;
newNode->value = num;
newNode->next = NULL;
// If there are no nodes in the list
// make newNode the first node
if (!head)
head = newNode;

else

// Otherwise, insert newNode at end

{
// Initialize nodePtr to head of list
nodePtr = head;

// Find the last node in the list
while (nodePtr->next)
nodePtr = nodePtr->next;

// Insert newNode as the last node
nodePtr->next = newNode;
}
}
// DisplayList shows the value
// stored in each node of the linked list
// pointed to by head.

template <class T>
void LinkedList<T>::displayList(void)
{
ListNode *nodePtr;

nodePtr = head;
while (nodePtr)
{
cout << nodePtr->value << endl;
nodePtr = nodePtr->next;
}
}
template <class T>
void LinkedList<T>::addatbeg(T a)
{
ListNode *newNode;
newNode = new ListNode;
newNode->value=a;
newNode->next=head;
head=newNode;
}/*End of addatbeg( )*/

template <class T>
void LinkedList<T>::addafter(T data,T pos)
{
ListNode *tmp,*q;
tmp = new ListNode;
q = new ListNode;
q=head;
for(int i=0;i<pos-1;i++)
{
q=q->next;
if(q == NULL)
{
cout<<"There are less nodes";
return;
}
}/*End of for*/

tmp->next=q->next;
tmp->value=data;
q->next=tmp;

}/*End of addafter( )*/
template <class T>
void LinkedList<T>::swap(int node1,int node2)
{
ListNode *q,*p; int tempvalue;
//tmp = new ListNode;
q = new ListNode;
p = new ListNode;

q=head;
p=head;
for(int i=0;i<node1-1;i++)
{
q=q->next;

}/*End of for*/
for( i=0;i<node2-1;i++)
{
p=p->next;
}
tempvalue=p->value;
p->value=q->value;
q->value=tempvalue;
}/*End of addafter( )*/

template <class T>
void LinkedList<T>::displayatnode(int pos)
{
ListNode *k;
k= new ListNode;

if (head == NULL)
{
cout<<"List is empty";
return;
}
k=head;
for(int i=0;i<pos-1;i++)
{
k=k->next;
if(k == NULL)
{
cout<<"There are less nodes";
return;
}
}/*End of for*/

cout<<"value at this position is"<<":";
cout<< k->value;

}/*End of displayatnode( )*/

// The insertNode function inserts a node with
// num copied to its value member.
template <class T>
void LinkedList<T>::insertNode(T num)
{
ListNode *newNode, *nodePtr, *previousNode;

// Allocate a new node & store Num
newNode = new ListNode;
newNode->value = num;

// If there are no nodes in the list
// make newNode the first node
if (!head)
{
head = newNode;
newNode->next = NULL;
}
else

// Otherwise, insert newNode at end

{
// Initialize nodePtr to head of list
nodePtr = head;

// Skip all nodes whose value member is less
// than num.
while (nodePtr != NULL && nodePtr->value < num)
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}
// Insert the node after the one pointed to
// by previousNode and before the one pointed to
// by nodePtr.
previousNode->next = newNode;
newNode->next = nodePtr;
}
}
// The deleteNode function searches for a node
// with Num as its value. The node, if found, is
// deleted from the list and from memory.

template <class T>
void LinkedList<T>::deleteNode(T num)
{
ListNode *nodePtr, *previousNode;
// If the list is empty, do nothing.
if (!head)
return;
// Determine if the first node is the one.
if (head->value == num)
{
nodePtr = head->next;
delete head;
head = nodePtr;
}
else
{
// Initialize nodePtr to head of list
nodePtr = head;

// Skip all nodes whose value member is
// not equal to num.
while (nodePtr != NULL && nodePtr->value != num)
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
}
// Link the previous node to the node after
// nodePtr, then delete nodePtr.
previousNode->next = nodePtr->next;
delete nodePtr;
}
}
// Destructor
// This function deletes every node in the list.

template <class T>
LinkedList<T>::~LinkedList(void)
{
ListNode *nodePtr, *nextNode;

nodePtr = head;
while (nodePtr != NULL)
{
nextNode = nodePtr->next;
delete nodePtr;
nodePtr = nextNode;
}
}
#endif

1 comment:

  1. Pretty section of content. I just stumbled upon your
    blog and in accession capital to assert that I acquire actually enjoyed account your blog posts.

    Anyway I'll be subscribing to your augment and even I achievement you access consistently quickly.


    Here is my blog; minecraft games

    ReplyDelete