Linked List

A linked list may be defined if all the block are linked to each other ,using address of the blocks . It’s different from an array , as an array is a collection of simultaneous boxes , where as list is collection of boxes which are connected by a string .

An Example of Linked list ,will be people pointing to the next person in a line ,where the last person is not pointing to anyone.

Sequential Representation

Then it’s physical data structure might look like :

Linked list will look like :

*A linked list is unidirectional.

A general representation of Linked list class will be

 class Node{
             int data;
             Node *next;
// next is a pointer pointing towards an object of class Box.
}

Now that we have a class node and class LinkedList , we can start linking the various objects of class LinkedList.

I have created 8 functions , each function has a particular use :

Take a look at our Node constructor , it’s a parameterized constructor . One of it’s parameters is the data variable. Also listptr is our pointer which points at first node of linked list and temp is a temporary pointer to hold values or iterate .

Algorithm for each function :

1. Create () :    
 1.1 if listptr == NULL => that means the Link list has not been initialized .
 1.2  else temp currently points towards current block ,you store the value of address of the new node in temp->next, now temp-> next points towards  new node.

if(listptr == NULL)
listptr = temp = newnode;
else
{
temp -> next = newnode;//temp currently points towards current block
temp = temp->next;
}

2. Display():
  2.1  if listptr==NULL , it means the List is empty 
  2.2 else current_node =listptr , it iterates until current_node reaches last block , 

while (current_node != NULL) //iterate till it reaches last block
{
cout << current_node->data << "--->";
current_node = current_node->next; /* move temp to the next node */
}
cout<< "NULL";
cout<<"\n";
}

3.Insert() : 
  3.1 There are three ways you can insert values in the list .
         
3.1.A : At beginning

3.2.B : At middle

3.3.C : At End

4.Delete () :
    4.1 : There are two ways to delete values in a List , either by value or position

4.1.1 By position : There are three ways:

4.1.1.A : At beginning

4.1.1.B : At middle

4.1.1.C : At End

4.1.2 By value :
Node *current_node=lp;
while (current_node->next!=NULL)
{
if (current_node->next->data==val)
{
Node *tempo;
tempo==current_node->next;
current_node->next=current_node->next->next;
free(tempo);
find=1;
}
current_node=current_node->next;

}
if(find ==0)
cout<<"\n Value Not present";

Application of Linked List :

1.Manipulation of Polynomials : Addition example , 2 ways of doing it ,

1.Comparing the linked list element by element using coef ,

void polynomial::add(polynomial &p1,polynomial &p2)
{
    PolyNode *ptr1,*ptr2;
    int powe;
    float coef;
    ptr1=p1.head;
    ptr2=p2.head;
    while((ptr1!=NULL)&&(ptr2!=NULL))
    {
        if(ptr1->power > ptr2->power)
        {
            coef=ptr1->coef;
            powe=ptr1->power;
            ptr1=ptr1->next;
        }
        else if(ptr1->power < ptr2->power)
        {
            coef=ptr2->coef;
            powe=ptr1->power;
            ptr2=ptr2->next;
        }
        else
        {
            coef=ptr1->coef+ptr2->coef;
            powe=ptr1->power;
            ptr1=ptr1->next;
            ptr2=ptr2->next;
        }
        if(coef!=0)
            addnodeatend(coef,powe);
    }
        if(ptr1==NULL)
        {
            for(;ptr2!=NULL;ptr2=ptr2->next)
                addnodeatend(ptr2->coef,ptr2->power);
        }
        else if(ptr2==NULL)
        {
            for(;ptr1!=NULL;ptr1=ptr1->next)
                addnodeatend(ptr1->coef,ptr1->power);
        }
}
void polynomial::addnodeatend(float coef,int power)
{
    PolyNode *ptr1,*ptr2;
    ptr1=new PolyNode;
    ptr1->coef=coef;
    ptr1->power=power;
    ptr1->next=NULL;
    if(head==NULL)
    {
        head=ptr1;
    }
    else
    {
        ptr2=head;
        while(ptr2->next!=NULL)
        {
            ptr2=ptr2->next;
        }
        ptr2->next=ptr1;
    }
}

2.Adding elements in to the same list and then , select same coef power and add elements and delete the duplicates :


    PolyNode * current_node1=lk1.listptr;
    PolyNode * current_node2=lk2.listptr;

    //copy elements of first Polynode
    while (current_node1!=NULL)
    {
    	lk3.Create(current_node1->coef, current_node1->exp);
        current_node1=current_node1->next;        
    }
    //copy elements of second Polynode
    while (current_node2!=NULL)
    {
    	lk3.Create(current_node2->coef, current_node2->exp);
        current_node2=current_node2->next;
    }
	lk3.Display();
    PolyNode * c3_1=lk3.listptr;
	while(c3_1!=NULL){
	    PolyNode * c3_2_prev=c3_1;
	    PolyNode * c3_2=c3_1->next;
		while(c3_2!=NULL){
			if(c3_1->exp == c3_2->exp){
				c3_1->coef += c3_2->coef;  
				c3_2_prev->next = c3_2->next;
			}else{
				c3_2_prev=c3_2;
			}
			c3_2=c3_2->next;
		}
		c3_1=c3_1->next;
	}
	lk3.Display();