Linked List - Introduction | Data Structure

 

Link List is a data structure in which each item may be place any where in the memory and we can manage these items by  applying the concept of structure and pointers.

Link means reference, In link list one variable or we can say that node is maintain the location of another variable.

We can say that there are two type of variable declaration in C program.

1. Static variables

2. Dynamic variables

Static variable are those that exist even during compilation of program. But Dynamic variable exist while program is in running state like using pointers

Type of Link List:

👉 Single Link List

👉 Doubly Link List

👉 Circular Link List

Operations Perform on Link List:

INSERTION:

1. Insert a node at beginning of list.

2. Insert a node at last of list.

3. Insert anode from link list at specific position.

DELETION:

1. Delete a node from beginning of list.

2. Delete a node from last of list.

3. Delete a node from link list at specific position.

CONCATENATE / MERGING

1. Concatenate the two link list.

REVERSE

1. Reverse the link list

STACK IMPLEMENTATION

1. Stack implementation using link list.

QUEUE  IMPLEMENTATION

1. Implementation of queue using link list

Graphical Representation of link list

Example: Creating and Inserting Data into Link List

Copy Code

//Complete Program for Creating and Inserting Elements into Link List

#include <stdio.h>

#include <conio.h>

struct node

{

    int data;

    struct node *next;

};

void main()

{

    struct node *newnode,*oldnode,*start,*temp;

    start=NULL;

    int ch=1;

    

    do

    {

        newnode=(struct node *)malloc(sizeof(struct node)); // Allocate memory

        printf("Enter data:");

        scanf("%d",&newnode->data);

        

        if(start==NULL)

        {

            start=newnode;

        }

        else

        {

            oldnode->next=newnode;

        }

        oldnode=newnode;

       

        // Ask Choice From User

        

        printf("Enter Choise:1-Continue 2-Stop");

        scanf("%d",&ch);

        

    }while(ch!=2);

    

    //display List Elements

    temp=start;

    while(temp!=NULL)

    {

        printf("->%d",temp->data);

        temp=temp->next;

    }

    

    getch();

}

Must Remember Some Conditions :

// If we can process every node of Link List

temp=start;

while(temp!=NULL)

{

    // Operation on node whose address is in temp

}

// If we want to identify last node than we perform operation in all node except last node

temp=start;

while (temp->next!=NULL)

{

    //Operation on node whose address is in temp

    temp=temp->next;

}

// If temp contain address of last node and previous contain address of second last node

temp=start

while (temp->next!=NULL)

{

    // Operation on node whose address is in temp

    previous=temp;

    temp=temp->next;

}

// If want to reach the ith location of temp node

i=1;

temp=start;

while(i<pos-1 && temp->next!=NULL)

{

    i++;

    temp=temp->next;

}

// Display Element of Link List

temp=start;

while(temp!=NULL)

{

    temp=temp->next;

}