Linked List (Singly)

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 is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains: data, and address of next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. 

Linked List vs Arrays

In arrays, elements are stored in contiguous memory locations. Also the size of the array is fix. So that if we need to extend the size of array, we have to copy the array to some bigger memory location. In case of inserting and deleting elements in array, we need to shift the elements to the left and right, respectively.


10

20

30

40

50

In Arrays, elements are stored in contiguous memory locations

But linked list are stored in non-contiguous memory locations, so there is no limitation in the size of linked list. In case of insertion , we just have to create a new node and link it with the previous element. Similarly in case of deletion, we just have to remove the linking of that element and free the element.


In Linked List, elements are stored in non-contiguous memory locations 

 Note: First node of linked list is pointed by head.

Why Linked Lists?

Memory and the capacity of an array remain fixed, while in linked lists, we can keep adding and removing elements without any capacity constraint.

Advantages of Linked List

  • Uses dynamic memory, so that it can be grow (increase) or shrink (decrease) during the execution of program.
  • Efficient memory utilization i.e. memory is not allocated like static memory.
  • Insertion and deletion are easy and efficient.

Drawbacks of Linked List

  • Extra memory space for pointers is required (for every node, extra space for a pointer is needed)
  • Random access is not allowed as elements are not stored in contiguous memory locations.

Node declaration in Linked List

struct Node
{
int info; // Data values
struct Node *next; // Address of next Node
};


Implementation of the Linked List


  • Linked List Creation and Traversal
Source Code (Linked List Creation and Traversal)

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

// Creation of Node
struct Node
{
    int data;
    struct Node *next;
};

void LinkedListTraversal(struct Node *ptr)
{
    while (ptr != NULL)
    {
        printf("Element : %d\n", ptr->data);
        ptr = ptr->next;
    }
}

int main()
{
    /* code */
    struct Node *head;
    struct Node *second;
    struct Node *third;

    // malloc function in C is used to allocate dynamic memory
    head = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));

    // Allocating value to the data part of Node
    head->data = 31;
    // Linking head Node with second Node
    head->next = second;

    second->data = 25;
    second->next = third;

    third->data = 02;
    third->next = NULL;

    LinkedListTraversal(head);

    return 0;
}

Output

Element : 31
Element : 25
Element : 2


  • Linked List Insertion
Source Code (Linked List Insertion)

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

struct Node
{
    int data;
    struct Node *next;
};

void LinkedListTraversal(struct Node *ptr)
{
    int cnt = 1;
    while (ptr != NULL)
    {
        printf("%d th Element : %d\n", cnt, ptr->data);
        ptr = ptr->next;
        cnt++;
    }
}

struct Node *InsertAtBeginning(struct Node *head, int data)
{
    struct Node *ptr = (struct Node *)malloc(sizeof(struct Node));
    ptr->data = data;
    ptr->next = head;
    return ptr;
}

struct Node *InsertAtIndex(struct Node *head, int index, int data)
{
    struct Node *ptr = (struct Node *)malloc(sizeof(struct Node));
    struct Node *p = head;
    int i = 0;

    while (i != index - 1)
    {
        p = p->next;
        i++;
    }

    ptr->data = data;
    ptr->next = p->next;
    p->next = ptr;

    return head;
}

struct Node *InsertAtLast(struct Node *head, int data)
{
    struct Node *ptr = (struct Node *)malloc(sizeof(struct Node));
    struct Node *p = head;
    while (p->next != NULL)
    {
        p = p->next;
    }
    ptr->data = data;
    p->next = ptr;
    ptr->next = NULL;
    return head;
}

struct Node *InsertAfterNode(struct Node *head, struct Node *node, int data)
{
    struct Node *ptr = (struct Node *)malloc(sizeof(struct Node));
    ptr->data = data;
    ptr->next = node->next;
    node->next = ptr;
    return head;
}

int main()
{

    struct Node *head;
    struct Node *second;
    struct Node *third;

    head = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));

    head->data = 31;
    head->next = second;

    second->data = 25;
    second->next = third;

    third->data = 02;
    third->next = NULL;

    // Linked List Traversal : Printing all data of Linked List
    printf("\nLinked List Traversal : \n");
    LinkedListTraversal(head);
    printf("\n");

    // Insertion at beginning
    printf("\nLinked List Insertion At The Beginning : \n");
    head = InsertAtBeginning(head, 100);
    LinkedListTraversal(head);
    printf("\n");

    // Insertion at the given index
    printf("\nLinked List Insertion At The Index : \n");
    head = InsertAtIndex(head, 3, 125);
    LinkedListTraversal(head);
    printf("\n");

    // Insertion at the end of Linked List
    printf("\nLinked List Insertion At The End : \n");
    head = InsertAtLast(head, 500);
    LinkedListTraversal(head);
    printf("\n");

    // Insertion after a given node of Linked List
    printf("\nLinked List Insertion After a Node : \n");
    head = InsertAfterNode(head, second, 3125);
    LinkedListTraversal(head);
    printf("\n");

    return 0;
}


Output

Linked List Traversal :
1th Element : 31
2th Element : 25
3th Element : 2


Linked List Insertion At The Beginning :
1th Element : 100
2th Element : 31
3th Element : 25
4th Element : 2


Linked List Insertion At The Index :
1th Element : 100
2th Element : 31
3th Element : 25
4th Element : 125
5th Element : 2


Linked List Insertion At The End :
1th Element : 100
2th Element : 31
3th Element : 25
4th Element : 125
5th Element : 2
6th Element : 500


Linked List Insertion After a Node :
1th Element : 100
2th Element : 31
3th Element : 25
4th Element : 3125
5th Element : 125
6th Element : 2
7th Element : 500


  • Linked List Deletion
Source Code (Linked List Deletion)

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

struct Node
{
    int data;
    struct Node *next;
};

void LinkedListTraversal(struct Node *head)
{
    struct Node *p = head;

    while (p != NULL)
    {
        printf("\nElement : %d", p->data);
        p = p->next;
    }
}

struct Node *DeleteAtBeginning(struct Node *head)
{
    struct Node *p = head;
    head = head->next;
    free(p);
    return (head);
}

struct Node *DeleteAtIndex(struct Node *head, int index)
{
    if (index == 0)
    {
        head = DeleteAtBeginning(head);
    }
    else
    {
        int i = 0;
        struct Node *p = head;
        struct Node *q = head;
        while (i != index)
        {
            q = p;
            p = p->next;
            i++;
        }

        q->next = p->next;
        free(p);
    }
    return (head);
}

struct Node *DeleteAtLast(struct Node *head)
{
    struct Node *p = head;
    struct Node *q;

    while (p->next != NULL)
    {
        q = p;
        p = p->next;
    }
    q->next = NULL;
    free(p);
    return (head);
}

struct Node *DeleteAfterNode(struct Node *head, struct Node *p)
{
    struct Node *q = head;
    while (q->next != p)
    {
        q = q->next;
    }
    q->next = p->next;
    free(p);
    return (head);
}

struct Node *DeleteGivenValue(struct Node *head, int value)
{
    struct Node *p = head->next;
    struct Node *q = head;
    while (p->data != value && p->next != NULL)
    {
        p = p->next;
        q = q->next;
    }
    if (p->data == value)
    {
        q->next = p->next;
        free(p);
    }
    return (head);
}

void main()
{

    struct Node *head;
    struct Node *second;
    struct Node *third;
    struct Node *fourth;
    struct Node *fifth;
    struct Node *sixth;

    int index;

    head = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));
    fourth = (struct Node *)malloc(sizeof(struct Node));
    fifth = (struct Node *)malloc(sizeof(struct Node));
    sixth = (struct Node *)malloc(sizeof(struct Node));

    head->data = 10;
    head->next = second;

    second->data = 20;
    second->next = third;

    third->data = 30;
    third->next = fourth;

    fourth->data = 40;
    fourth->next = fifth;

    fifth->data = 50;
    fifth->next = sixth;

    sixth->data = 60;
    sixth->next = NULL;

    // Linked List Traversal : Printing all data of Linked List
    printf("\nLinked List Traversal : \n");
    LinkedListTraversal(head);
    printf("\n");

    // Deletion at beginning
    printf("\nLinked List Deletion At The Beginning : \n");
    head = DeleteAtBeginning(head);
    LinkedListTraversal(head);
    printf("\n");

    // Deletion of the given value
    int val = 40;
    printf("\nLinked List Deletion of The Given Value : (%d)\n", val);
    head = DeleteGivenValue(head, val);
    LinkedListTraversal(head);
    printf("\n");

    // Deletion at the given index
    index = 2;
    printf("\nLinked List Deletion At The Index : %d\n", index);
    head = DeleteAtIndex(head, index);
    LinkedListTraversal(head);
    printf("\n");

    // Deletion at the end of Linked List
    printf("\nLinked List Deletion At The End : \n");
    head = DeleteAtLast(head);
    LinkedListTraversal(head);
    printf("\n");

    // Deletion after a given node of Linked List
    printf("\nLinked List Deletion After a Node : third(%d)\n",           third->data);
    head = DeleteAfterNode(head, third);
    LinkedListTraversal(head);
    printf("\n");
}


Output

Linked List Traversal :

Element : 10
Element : 20
Element : 30
Element : 40
Element : 50
Element : 60

Linked List Deletion At The Beginning :

Element : 20
Element : 30
Element : 40
Element : 50
Element : 60

Linked List Deletion of The Given Value : (40)

Element : 20
Element : 30
Element : 50
Element : 60

Linked List Deletion At The Index : 2

Element : 20
Element : 30
Element : 60

Linked List Deletion At The End :

Element : 20
Element : 30

Linked List Deletion After a Node : third(30)

Element : 20

Comments

Post a Comment

Popular posts from this blog

Searching Algorithms in Data Structure

Searching is a process of retriving or locating or finding information matching with some specific value. In data structure there are two types of searching. Linear or sequencial search Binary search   Linear or Sequencial Search It is a simplest form of searching and can be applied for sequencial storage such as array, stack, queue, linked list. Algorithm Linear/Sequencial Search Step 1: Start Step 2: Set 0 to i Step 3: Read and store value to search in val Step 4: if a(i) = val, print value is found at (i+1) position and go to step 8 Step 5: Set i to i + 1 Step 6: If i is less than n then, go to Step 4 Step 7: Print element not found Step 8: Stop n - size of array a - array val - value to be searched in array Source Code #include <stdio.h> #include <conio.h> #include <stdlib.h> int main() { int n; printf("Enter the size of array : "); scanf("%d", &n); int arr[n]; for...
Read more

Sorting Algorithms in Data Structure

Sorting is a process of arranging information either in ascending or in descending order of key values. In data structures there are techniques available to sort the data. Types of sorting algorithms Bubble sort Insertion sort Selection sort Quick sort Radix sort Merge sort   1. Bubble Sort It is one of the simplest & popular sorting method. The basic idea of this sorting is that in each pass we have to compare a successive pair of element i.e. a[i] & a[i+1]. Interchange these two values, if they are not place in proper order. Place the element in it's correct position in each pass. In first pass largest element is shifted at bottom. In second pass second largest will be shifted to the second last position & so on. Thus to sort n values n-1 passes are required. Algorithm Bubble Sort Step 1: Start Step 2: Set 1 to pass Step 3: Set o to i Step 4: if a[i]> a[i+1] then, Swap a[i] & a[i+1] Step 5: Add I to i. Step 6: If i...
Read more

Circular Linked List

Image
I n a Circular Linked List the first and the last elements are adjacent. A linked list can be made circular by storing the address of the first node in the next field of the last node. In a circular linked list, last node is connected back to the first node. In some applications, it is convenient to use circular linked list. A queue data structure can be implemented using a circular linked list, with a single pointer "rear" as the front node can be accessed through the rear node. Implementation of Circular Linked List Circular Linked List Creation and Traversal Algorithm for traversing a circular list is slightly different than the same algorithm for a singly linked list because "NULL" is not encountered. Source Code (Circular Linked List Creation and Traversal) #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node *next; }; void CircularLinkedListTraversal(stru...
Read more