HOME

    Electronics Directory Articles/ Tutorials eBooks

About Us

FORUM Links Contact Us
   

 

 Dynamic memory with C++: Linked Lists

By Murali Krishna

 

 

Arrays can be used to store a series of data when the members of the series is fixed or bounded. But if the length of array is to be decided in the run time, Linked list can be used. This article helps you to start programming with linked lists.

 

 

 

Why Linked lists?

            Let us consider an example of implementation of a STACK or a QUEUE using a linear array then it is necessary to declare the SIZE of the STACK or QUEUE array (at Compile time) this may leads to either memory wastage or insufficient memory. This is the main disadvantage of a linear array. So if we use a linked list, we can allocate the  memory "Dynamically"   ( ie. during Run time). So there will not be any problem of memory wastage or insufficient memory.

           Whenever we want to insert or delete an element from a linear array either we must overwrite the value or we should shift the elements to new location. Where as in a linked list we can directly insert or delete the elements without effecting the other elements.

             In the conventional linear array storage the memory allocation is contiguous. for ex: When we declare an integer array in 'C /C++ language'

int  a[100];   //array declaration int is the data type size is 4

then '&a[0]' or &a is called as the base address .If we want to access the element  through direct addressing then a[1] will be located at a location (&a[0]+ size(int)). Here size of int data type  is 2 bytes. The  addresses of the element  located  in an array at a position ' k' can be calculated using the formula given below

LOC (Array [k])= Base Address (Array) + k * size( data type declared)

'k'  is the index of element . If the base address(&a[0])  is 1000, and data type is integer then next element will be located at the location 1002 (i.e.&a[1]= 1000+ 1*(2)), similarly the address of the element a[4] is 1008.  So whenever we access the data, the computer calculates the address location as mentioned  above . This process is much slower when compared to directly fetching data form memory using a pointer.

                In A linked list ach NODES don't need to be located  in adjacent location. The storage may not be contiguous in a linked list. In a linked list , the access of data is done using a pointer. Thus the data access is much faster in linked list.

        A linked list have an extra field to store the link address .

What is a linked list?

     A linked list is a linear data structure used to organize the data in the memory. As its name indicates linked list is a list of items called the 'NODE' linked using  pointers. A 'NODE' is a structure of List containing  two or more fields called the 'data /Info' field and 'Link/address' field. A linked list can be of any of the following type.

bulletSingly-Linked Lists
bulletDoubly-Linked Lists or Two way Linked List
bulletCircularly-Linked Lists
bulletCircularly-Doubly Linked Lists

NODE A node is user defined structure.  A node has at least two fields  data field and link field. Here the following figure shows a node.

NODE

It is not necessary that a node should have two fields we may have more than one data field.

........

here  data1,data2,...data n  are the data fields. The data field may contain Integer data or string data or a character data.

LINK field is a pointer contains the address of the node related to it. A link is denoted by a arrow symbol as shown below

Every Node will have  an  address. Here 1000 is the address of the second  node. So the link field of the previous node (first node) to it contains the value 1000

The general structure of a NODE is given as

struct tag_name {
type member1;
type member2;
......................
......................
.....................
struct tag_name *linknext;  //pointer stores the address of next node
}
 

In the above given structure member1,member2,...etc are the data fields of node. These member variables need not be of the same data type

example:

struct Node {                     //Node is the tag name given here
int  rollno;                  
//this is of integer type
char name[20];        
//this is of char type
......................
......................
.....................
struct Node *link; 
//stores the address of next node
}
 

 

Now let us see what is a Singly Linked List :

The following figure shows a singly linked list. It has single link field extended as list

 The above picture shows a singly linked list the first node is called the header node . This is the entry point to the  list and the list is terminated when the link field of any of the node is NULL.

Now let us see what is a Doubly-Linked List :

The following figure shows a doubly linked list . The link is two way. Here the NODE contains two pointers LPTR left pointer and the RPTR right pointer. LPTR  points to the previous node and RPTR points to the next node. Please note that whenever there is no node to point then the link is poited to NULL.

The advantage of Two way linked list is that the traversal  becomes easy.

 

 

Now let us see what is a Circularly-Linked List :

A Circularly linked list is similar to singly linked list except that the " 'Link' field of Last NODE points to the first node"

 

Now we shall see the class implementation of a linked list:-

//Implementation of a linked list
#include<iostream.h>
#include<conio.h>
 class linklist{
       private:
                   struct node{
                             int data;
                             node *link;
                    }*p;
       public:
                   linklist();
                   void addend(int num);
                   void addbeg(int num);
                   void addafter(int c,int num);
                   void del(int num);
                   void display();
                   int count();
                   ~linklist();
};

 

//add a new node at the beginning of the linked list


void linklist::addbeg(int num)
{
        node *q;
             //add newnode
         q=new node;
         q->data=num;
         q->link=p;
         p=q;
}

 the above function adds a new node at the beginning

What are the operations that can be performed on Singly-Linked list ?

            The operations that can be performed on a linked list are

bulletInsertion of a new node to the beginning of a list, end of a list, or inserting  In- between two nodes new node at the end of the linked list

// add a node at a specified location in the list
        void linklist::addafter(int c,int num)
        {
             node *q,*t;
             int i;
             q=p;
              for (i=0;i < c;i++)
              {
                q=q->link;
                if(q==NULL)
                   {
                        cout<<"there is no such node existing:"<<endl;
                        return;
                    }
              }
           t=new node;
           t->data=num;
           t->link=q->link;
          q->link=t;
       }

 the above function adds a node at a specified location

// insert at the end

           void linklist::addend(int num)
           {
                node *q,*t;
                //if the list is empty
                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;
                   }
             }

 

  The above function adds a node at the  end of list

bulletDeletion of a  node:

//deletes the specified node from the linked list


                    void linklist:: del(int num)
                       {
                            node *q,*r;
                            q=p;
                            //if node to be deleted is the first node
                            if (q->data==num)
                                 {
                                       p=p->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;
                                 }
                          }

 

 bulletTraversing a node and displaying data: 

                                void linklist::display()
                                    {
                                        node *q;
                                        clrscr();
                                        cout<<endl;
                                         for(q=p;q!=NULL;q=q->link)
                                                      cout<<" "<<q->data;
                                    }

  Here is the main program ;

//This is the main program
           void main()
              {
                  linklist list;
                  cout<<endl;
                  list.addbeg(11);
                  list.addbeg(834);
                  list.addbeg(187);
                  list.addbeg(7);
                  list.addbeg(1);
                  list.addend(1 );
                  list.addafter(0,330);
                  list.display();
                  getch();
              }

 

 

 

Home   |    About Us   |   Articles/ Tutorials   |   Downloads   |   Feedback   |   Links   |   eBooks   |   Privacy Policy
Copyright 2005-2007 electroSofts.com.
webmaster@electroSofts.com