Posted by frankhale@xxxxxxxx.xxx.xxx on 1999-04-26
To whomever wanted the linkedlist information.
I just sent out some link list code in C. But this one is the same but
in C++ using templates. This makes it generic enough to hold any data
you need.
Again this is for singly linked lists.
Have fun. Happy Coding!!!
to compile:
g++ -o linklist linklist.cc
/////////////////////////////////////////////////////////////////////
// Simple singly linked list in C++ using templates
//
// Frank Hale
// 28,29 Jan 1999
// Original C version 4 Feb 1999
//
// Converted to C++ w/templates on 25 March 1999
//
// website - www.franksstuff.com
// email address - frankhale@xxxxxxxx.xxx.xxx
//
// Description - This was really an exercise to develop linked list
// code that was pretty generic but provides a decent amount of
// functionality to manipulate linked lists.
//
// ******************************************************************
// This code is released under the terms of the GNU license.
// Refer to www.gnu.org for a copy of this license.
// ******************************************************************
/////////////////////////////////////////////////////////////////////
#include <iostream.h>
// Misc new data types
typedef enum _bool { FALSE, TRUE } BOOL;
// Forward declaration of class LinkedList
template <class t> class LinkedList;
// Represents a node (ie. element) in the list
template <class t>
class NODE
{
public:
// This is the data contained in the node.
t data;
// Pointer to the next node
NODE<t> *next;
};
// Represents a list of nodes
template <class t>
class LIST
{
public:
// Pointer to a node structure
NODE<t> *node;
// Number of elements in this list
int elements;
friend class LinkedList<t>;
};
template <class t>
class LinkedList {
public:
LIST<t> list;
NODE<t> Data;
public:
LinkedList() {}
~LinkedList() {}
// These are the member functions to manipulate the linklist
BOOL addElement(LIST<t> *l, NODE<t> *d);
BOOL addAfterElement(LIST<t> *l, int num, NODE<t> *d);
BOOL addBeforeElement(LIST<t> *l, int num, NODE<t> *d);
BOOL updateElement(LIST<t> *l, int num, NODE<t> *d);
void printElements(LIST<t> *l);
void deleteElement(LIST<t> *l, int num);
int numberOfElements(LIST<t> *l);
};
// Adds an element to the list
template <class t>
BOOL LinkedList<t>::addElement(LIST<t> *l, NODE<t> *d)
{
// Declare 3 nodes to work with
NODE<t> *newnode;
NODE<t> *currnode;
NODE<t> *prevnode;
// Allocate the memory for our new node
newnode = new NODE<t>;
// If its NULL then we couldn't allocate memory
if(newnode == NULL)
{
cout << "Couldn't allocated memory for new list node" << endl;
return FALSE;
}
// The next node is the last node so it should be NULL
newnode->next = NULL;
// Add the data to the list
newnode->data = d->data;
// Previous node is NULL because its the head node.
prevnode=NULL;
// Current node equals our global list head node.
currnode = l->node;
// While current node does not equal NULL
// previous node equals the current node
// and the current node equals the next node
// so we are iterating through the list.
while(currnode != NULL)
{
prevnode = currnode;
currnode = currnode->next;
}
// While not end of list go to the end of list
// and add the node there.
// Otherwise we are adding the first element.
if(prevnode != NULL)
{
newnode->next = prevnode->next;
prevnode->next = newnode;
} else {
l->node = newnode;
}
// Increment the number of nodes in the list.
l->elements++;
// Yeah, we successfully added data to the list.
return TRUE;
}
// Iterates through the list until we find the number of the element
// we plan to delete then we delete it, and subract 1 from the number
// of list nodes stored in l->elements.
template <class t>
void LinkedList<t>::deleteElement(LIST<t> *l, int num)
{
NODE<t> *currnode = l->node;
NODE<t> *prevnode;
int count = 0;
if(num > 0)
{
while(currnode && count < num)
{
prevnode = currnode;
currnode = currnode->next;
count++;
}
prevnode->next = currnode->next;
} else {
l->node = l->node->next;
}
free(currnode);
l->elements--;
}
// Adds a new element after a specific element
template <class t>
BOOL LinkedList<t>::addAfterElement(LIST<t> *l, int num, NODE<t> *d)
{
NODE<t> *newnode;
NODE<t> *currnode = l->node;
NODE<t> *prevnode;
int count = 0;
// Allocate the memory for our new node
newnode = new NODE<t>;
// If its NULL then we couldn't allocate memory
if(newnode == NULL)
{
cout << "Couldn't allocated memory for new list node" << endl;
return FALSE;
}
// The next node is the last node so it should be NULL
newnode->next = NULL;
// Add the data to the list
newnode->data = d->data;
// Previous node is NULL because its the head node.
prevnode=NULL;
// Current node equals our global list head node.
currnode = l->node;
while(currnode != NULL && count < num)
{
prevnode = currnode;
currnode = currnode->next;
count++;
}
if(currnode != NULL)
{
newnode->next = currnode->next;
currnode->next = newnode;
} else {
// If we are trying to add an element after the last
// element then all we need to do is call addElement
// and pass it the data.
addElement(l,d);
}
// Increment the number of nodes in the list.
l->elements++;
// Yeah, we successfully added data to the list.
return TRUE;
}
// Adds a new element before a specific element
template <class t>
BOOL LinkedList<t>::addBeforeElement(LIST<t> *l, int num, NODE<t> *d)
{
NODE<t> *newnode;
NODE<t> *currnode = l->node;
NODE<t> *prevnode;
int count = 0;
// Allocate the memory for our new node
newnode = new NODE<t>;
// If its NULL then we couldn't allocate memory
if(newnode == NULL)
{
cout << "Couldn't allocated memory for new list node" << endl;
return FALSE;
}
// The next node is the last node so it should be NULL
newnode->next = NULL;
// Add the data to the list
newnode->data = d->data;
// Previous node is NULL because its the head node.
prevnode=NULL;
// Current node equals our global list head node.
currnode = l->node;
while(currnode != NULL && count < num)
{
prevnode = currnode;
currnode = currnode->next;
count++;
}
if(prevnode != NULL)
{
newnode->next = prevnode->next;
prevnode->next = newnode;
} else {
newnode->next = currnode;
currnode = newnode;
l->node = currnode;
l->node->next = currnode->next;
}
// Increment the number of nodes in the list.
l->elements++;
// Yeah, we successfully added data to the list.
return TRUE;
}
template <class t>
BOOL LinkedList<t>::updateElement(LIST<t> *l, int num, NODE<t> *d)
{
// Search through the list and find the record we want
NODE<t> *newnode = new NODE<t>;
NODE<t> *currnode = l->node;
NODE<t> *prevnode;
int count = 0;
newnode->data = d->data;
if(num > 0) {
while(currnode && count < num)
{
prevnode = currnode;
currnode = currnode->next;
count++;
}
prevnode->next = currnode->next;
// While not end of list go to the end of list
// and add the node there.
// Otherwise we are adding the first element. */
if(prevnode != NULL)
{
newnode->next = prevnode->next;
prevnode->next = newnode;
}
} else {
newnode->next = l->node->next;
l->node = newnode;
}
delete newnode;
return TRUE;
}
// Prints out all the elements in the list.
template <class t>
void LinkedList<t>::printElements(LIST<t> *l)
{
NODE<t> *temp = l->node;
int count=0;
cout << "number of elements = " << list.elements << endl;
while(temp != NULL)
{
cout << "element " << count << " : " << temp->data << endl;
temp = temp->next;
count++;
}
}
// Simply prints the number of elements in the list passed to it
template <class t>
int LinkedList<t>::numberOfElements(LIST<t> *l)
{
return l->elements;
}
// This demonstrates the linked list functions
int main()
{
cout << "This is a list with integers " << endl << endl;
LinkedList<int> *n;
n = new LinkedList<int>;
n->Data.data = 99;
n->addElement(&n->list, &n->Data);
n->Data.data = 76;
n->addElement(&n->list, &n->Data);
n->Data.data = 172;
n->addElement(&n->list, &n->Data);
n->Data.data = 259;
n->addElement(&n->list, &n->Data);
n->printElements(&n->list);
// Another list with char*
cout << endl << "This is another list with char* " << endl << endl;
LinkedList<char*> *a;
a = new LinkedList<char*>;
a->Data.data = "Hello,world!";
a->addElement(&a->list, &a->Data);
a->Data.data = "C++ templates are cool as shit!!!";
a->addElement(&a->list, &a->Data);
a->Data.data = "Look ma I can program";
a->addElement(&a->list, &a->Data);
a->Data.data = "This linked list code was converted from C to C++ in
about 1 hour";
a->addElement(&a->list, &a->Data);
a->printElements(&a->list);
delete n;
delete a;
return 0;
}
--
From: Frank Hale
Email: frankhale@xxxxxxxx.xxx.xxx
ICQ: 7205161
Website: http://www.franksstuff.com
Previous post | Next post | Timeline | Home