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();
```

Well you can also handle multiplication handling of polynomials using Linked list ,

The following blog will contain the other topics in linked list such as circular , doubly , Stack &Queue implementation of Linked List.

GitHub code :https://github.com/kakabisht/Data-structures

Source of study :

Types of List : https://programmerprodigy.code.blog/2020/04/25/types-of-lists/

Application of Link list :https://programmerprodigy.code.blog/2020/04/22/stacks-and-queues-using-linked-list/

## 2 thoughts on “Linked List”