Linked Lists

A linked list is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next.

It consists of a collection of nodes, where each node contains: data and a reference or link to the next node in the sequence.

Therefore, it allows efficient insertion and deletion of elements from any position in the sequence while iterating.

Now the question arises why use linked lists instead of the array which can also be used to store linear data types of similar types, but arrays have some limitations.

a) The size of an array is fixed. So we should know the number of elements in advance.

b) Inserting a new element in an array of elements is an expensive task due to the fact that the room has to be created for the new elements so we have to shift existing elements for room.

---

Advantages over an array:

1) Dynamic size.

2) Ease of insertion and deletion.

Drawbacks:

1) Random access is not allowed, we have to access elements sequentially starting from the first node. So, we cannot do a binary search with linked lists efficiently.

2) Extra memory space is required for pointer variables with each element of the list.

---

---

Representation of node of the linked list:

A linked list is represented by a pointer to the first node of the linked list.

The very first node is called HEAD. And if the linked list is empty then the value of the head is NULL.

Every node in a list consists of two parts:

1) Data

2) Pointer to the next node.

In C we can use structures for representing the node.

// A linked list node 
struct Node { 
    int data; 
    struct Node* next; 
};

---

Implementation using C:

#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node*next;
}*head=NULL,*q,*temp;

typedef struct node node;

    void insert_beg();
    void insert_end();
    int insert_pos();
    void display();
    void delete_beg();
    void delete_end();
    int delete_pos();

int main()
{
    int ch;


    while(1)
    {
        printf("\n\n---- Singly Linked List(SLL) Menu ----");
        printf("\n1.Insert\n2.Display\n3.Delete\n4.Exit\n\n");
        printf("Enter your choice(1-4):");
        scanf("%d",&ch);

        switch(ch)
    {
        case 1:
            printf("\n---Insert Menu---");
            printf("\n1.Insert at beg\n2.Insert at end\n3.Insert at position");
            printf("\n\nEnter your choice(1-4): ");
            scanf("%d",&ch);

            switch(ch)
            {
                case 1: insert_beg();
                        break;
                case 2: insert_end();
                        break;
                case 3: insert_pos();
                        break;
                case 4:exit(0);

                default: printf("Wrong choice !!");

            }
            break;

        case 2: display();
                    break;

        case 3: printf("\n---- Delete Menu ----");
                printf("\n1.Delete from beginning\n2.Delete from end\n3.Delete from specified position\n4.Exit");
                printf("\n\nEnter your choice(1-4):");
                scanf("%d",&ch);

                switch(ch)
                {
                    case 1: delete_beg();
                            break;
                    case 2: delete_end();
                            break;
                    case 3: delete_pos();
                            break;
                    case 4: exit(0);
                    default: printf("Wrong Choice!!");
                }
                break;
        case 4: exit(0);
                    default: printf("Wrong Choice!!");
        }
    }
    return 0;
}

void insert_beg()
{

    int num;
    temp=(node*)malloc(sizeof(node));
    printf("Enter data: ");
    scanf("%d",&num);
    temp->data=num;

    if(head == NULL)
    {
        temp->next=NULL;
        head=temp;
    }
    else
    {
        temp->next=head;
        head=temp;
    }
}
void insert_end()
{
    int num;
    temp=(node*)malloc(sizeof(node));
    printf("Enter data: ");
    scanf("%d",&num);
    temp->data=num;
    temp->next=NULL;

    if(head == NULL)
    {
        head=temp;
    }
    else
    {
        q=head;

        while(q->next!= NULL)
            q=q->next;

        q->next=temp;
    }
}

int insert_pos()
{
    int pos,i,num;

    temp=(node*)malloc(sizeof(node));

    printf("Enter data: ");
    scanf("%d",&num);

    printf("Enter position to insert:");
    scanf("%d",&pos);

    temp->data=num;

   if(head == NULL)
   {
       temp->next=NULL;
       head=temp;
   }

    q=head;
    for(i=1;i<pos-1;i++)
    {
        if(q->next == NULL)
        {
            printf("There are less elements in the list !!");
            return 0;
        }
        q=q->next;
    }
    temp->next=q->next;
    q->next=temp;
    return 0;
}

void display()
{
    if(head == NULL)
    {
        printf("List is empty !!");
    }
    else
    {
        q=head;
        printf("Linked list is :  \n");
        while(q != NULL)
        {
            printf("%d -> ",q->data);
            q=q->next;
        }
    }
}

void delete_beg()
{

    if(head == NULL)
    {
        printf("List is empty ");
    }
    else
    {
        q=head;
        head=q->next;
        printf("Deleted element is : %d ",q->data);
        free(q);
    }
}

void delete_end()
{
    if(head == NULL)
    {
        printf("List is empty");
    }
    else
    {
        q=head;
        while(q->next->next != NULL)
            q=q->next;

        temp=q->next;
        q->next=NULL;
        printf("DELETED element is : %d",temp->data);
        free(temp);
    }
}

int delete_pos()
{
    int pos,i;

    if(head == NULL)
    {
        printf("List is empty!!");
        return 0;
    }

    printf("Enter position to delete:");
    scanf("%d",&pos);

    q=head;

    for(i=1;i<pos-1;i++)
    {
        if(q->next == NULL)
        {
            printf("There are less elements ");
            return 0;
        }
        q=q->next;
    }
    temp=q->next;
    q->next=temp->next;
    printf("Deleted element is %d ",temp->data);
    free(temp);

    return 0;
}

---

Follow Programmers Door for more. #programmersdoor #programming #c #blog