Code Snippets

C++ Source Code

Welcome to Dream.In.Code
	Become a C++ Expert! Join 244,287 C++ Programmers for FREE! Get instant access to thousands of C++ experts, tutorials, code snippets, and more! There are 974 people online right now. Registration is fast and FREE... Join Now! Chat LIVE With a C++ Expert

Linked List Class

Implements the Linked List Data Structure.

Submitted By: born2c0de

Actions:

Rating:

Views: 79,675

Language: C++

Last Modified: January 18, 2008

Snippet

#include <iostream>
using namespace std;
class linklist
{
private:
struct node
{
int data;
node *link;
}*p;
public:
linklist();
void append( int num );
void add_as_first( int num );
void addafter( int c, int num );
void del( int num );
void display();
int count();
~linklist();
};
linklist::linklist()
{
p=NULL;
}
void linklist::append(int num)
{
node *q,*t;
if( p == NULL )
{
p = new node;
p->data = num;
p->link = NULL;
}
else
{
q = p;
while( q->link != NULL )
q = q->link;
t = new node;
t->data = num;
t->link = NULL;
q->link = t;
}
}
void linklist::add_as_first(int num)
{
node *q;
q = new node;
q->data = num;
q->link = p;
p = q;
}
void linklist::addafter( int c, int num)
{
node *q,*t;
int i;
for(i=0,q=p;i<c;i++)
{
q = q->link;
if( q == NULL )
{
cout<<"\nThere are less than "<<c<<" elements.";
return;
}
}
t = new node;
t->data = num;
t->link = q->link;
q->link = t;
}
void linklist::del( int num )
{
node *q,*r;
q = p;
if( q->data == num )
{
p = q->link;
delete q;
return;
}
r = q;
while( q!=NULL )
{
if( q->data == num )
{
r->link = q->link;
delete q;
return;
}
r = q;
q = q->link;
}
cout<<"\nElement "<<num<<" not Found.";
}
void linklist::display()
{
node *q;
cout<<endl;
for( q = p ; q != NULL ; q = q->link )
cout<<endl<<q->data;
}
int linklist::count()
{
node *q;
int c=0;
for( q=p ; q != NULL ; q = q->link )
c++;
return c;
}
linklist::~linklist()
{
node *q;
if( p == NULL )
return;
while( p != NULL )
{
q = p->link;
delete p;
p = q;
}
}
int main()
{
linklist ll;
cout<<"No. of elements = "<<ll.count();
ll.append(12);
ll.append(13);
ll.append(23);
ll.append(43);
ll.append(44);
ll.append(50);
ll.add_as_first(2);
ll.add_as_first(1);
ll.addafter(3,333);
ll.addafter(6,666);
ll.display();
cout<<"\nNo. of elements = "<<ll.count();
ll.del(333);
ll.del(12);
ll.del(98);
cout<<"\nNo. of elements = "<<ll.count();
return 0;
}

Copy & Paste

#include <iostream>

using namespace std;

class linklist
{
     private:

struct node
         {
              int data;
            node *link;
         }*p;

public:

linklist();
         void append( int num );
         void add_as_first( int num );
         void addafter( int c, int num );
         void del( int num );
         void display();
         int count();
         ~linklist();
};

linklist::linklist()
{
     p=NULL;
}

void linklist::append(int num)
{
     node *q,*t;

if( p == NULL )
   {
        p = new node;
      p->data = num;
      p->link = NULL;
   }
   else
   {
        q = p;
      while( q->link != NULL )
           q = q->link;

t = new node;
      t->data = num;
      t->link = NULL;
      q->link = t;
   }
}

void linklist::add_as_first(int num)
{
     node *q;

q = new node;
   q->data = num;
   q->link = p;
   p = q;
}

void linklist::addafter( int c, int num)
{
     node *q,*t;
   int i;
   for(i=0,q=p;i<c;i++)
   {
        q = q->link;
      if( q == NULL )
      {
           cout<<"\nThere are less than "<<c<<" elements.";
         return;
      }
   }

t = new node;
   t->data = num;
   t->link = q->link;
   q->link = t;
}

void linklist::del( int num )
{
     node *q,*r;
   q = p;
   if( q->data == num )
   {
        p = q->link;
      delete q;
      return;
   }

r = q;
   while( q!=NULL )
   {
        if( q->data == num )
      {
           r->link = q->link;
         delete q;
         return;
      }

r = q;
      q = q->link;
   }
   cout<<"\nElement "<<num<<" not Found.";
}

void linklist::display()
{
     node *q;
   cout<<endl;

for( q = p ; q != NULL ; q = q->link )
        cout<<endl<<q->data;

}

int linklist::count()
{
     node *q;
   int c=0;
   for( q=p ; q != NULL ; q = q->link )
        c++;

return c;
}

linklist::~linklist()
{
     node *q;
   if( p == NULL )
        return;

while( p != NULL )
   {
        q = p->link;
      delete p;
      p = q;
   }
}

int main()
{
     linklist ll;
   cout<<"No. of elements = "<<ll.count();
   ll.append(12);
   ll.append(13);
   ll.append(23);
   ll.append(43);
   ll.append(44);
   ll.append(50);

ll.add_as_first(2);
   ll.add_as_first(1);

ll.addafter(3,333);
   ll.addafter(6,666);

ll.display();
   cout<<"\nNo. of elements = "<<ll.count();

ll.del(333);
   ll.del(12);
   ll.del(98);
   cout<<"\nNo. of elements = "<<ll.count();
   return 0;
}

Comments
everest_01 2008-08-17 21:33:11
Nice job It is to the point, clear and useful
NevilleDNZ 2008-11-27 05:09:16
Hi... I revengineered your Linked List Data Structure code sinppet http://www.dreamincode.net/forums/showtopic73767.htm in an "earlier" language. N
rissvann 2008-12-23 15:13:53
that is good, i wish i can do things like that
witnessmenow 2009-03-18 19:00:13
I found this very useful, thanks
ComputerAnalysis 2009-07-01 09:58:13
Serious improvements could be made. For example why are you traversing the whole list to find the size when you can just keep an int count variable and increment it each time you add a node and decrement for each delete. That would turn an O(n) to a O(1) operation. Also there do exists implementations of lists where every operation is O(1).