Code Snippets

C++ Source Code

Welcome to Dream.In.Code
	Become a C++ Expert! Join 300,288 C++ Programmers for FREE! Get instant access to thousands of C++ experts, tutorials, code snippets, and more! There are 2,081 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: 97,736

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).
autumn_storm2216 2009-08-07 04:24:55
it is hard for me to understand as a beginner i just know the language C++ and i guess the language your using is different...
ComputerAnalysis 2009-08-10 14:55:12
@autumn_storm2216: Um no that's C++ alright.
spidercode31337 2009-08-21 14:19:46
I agree with the last comment by ComputerAnalysis, keep reading your text book, you'll see that this is the more advanced stuff.
venkat arun 2009-10-01 02:12:51
Good post, and I wish I had this earlier, it would have saved me so much trouble. I partly disagree about that inefficiency thing with the finding of no. of items, as to maintain a counter, you are iterating it the same no. of times, and count is not something one does often. However I think this should be converted into a library, with a get function (that gets the required object) instead of show, and using templates. Handy code