Skip to main content

4. Linked Lists

 

Linked Lists

  • Linked List is a linear data structure.
  • A linked list stores its elements separately in non-contiguous locations in the form of nodes.
  • Linked list can be visualized as a chain of nodes, where every node points to the next node.
  • Each node contains two fields, namely, a data field to store an element and a next field which is a pointer used to connect one node to next node.
  • It is used in the implementation of stacks, queues, graphs, etc.
  • Linked list is used in music player, web browser to store the URL of previous and next page, image viewer, etc.

Array V/S Linked List

ArraysLinked List
Array elements are stored in a contiguous memory locations.Linked list elements can be stored anywhere in the memory or randomly stored.
Array elements are independent of each other.Linked list elements are dependent on each other.
We can easily access any element in an array, if the base address is known.To find any node in the linked list, we first need to find the first node and then traverse from the first node.
Time complexity for accessing elements in an array = O(1)Time complexity for accessing elements in a linked list = O(n)
Size of an array is fixed and cannot be changed after creation.Size of the linked list is not fixed. It can be increased or decreased as per requirements.
Array takes more time while performing any other operation like insertion, deletion etc.Linked list takes less time while performing other operation like insertion, deletion etc.
Memory utilization is inefficient in the array.Memory utilization is efficient in the case of a linked list.
To store an element in a linked list, it will take more memory space than an array takes.To store an element in an array, it will take less memory space than a lisnked list takes.

Types of Linked List

  1. Singly Linked List: It is a type of linked list that is unidirectional, that is, it can be traversed in only one direction from head to the last node (tail).
  2. Single Circular Linked List: Data elements are connected to form a circle with no NULL values in last node. Data elements are traversed in only one direction from head to the last node (tail) which points to the head of the linked list.
  3. Doubly Linked List: It is a type of data structure that is bidirectional, that is, it can be traversed in both direction from head to tail and tail to head.
  4. Double Circular Linked List: Data elements are connected to form a circle and the next pointer of the last node points to the first node and the previous pointer of the first node points to the last node.
  5. Header Linked List: It is a variant of linked list, where linked list have a special node present at the beginning to store number of nodes present in the linked list.

Basic Terminologies

  • Start (or head) pointer: Points to the first (or head) node of the linked list.
  • Node: An item in a linked list. Each node contains a data field and a link field location of the next node.
  • Data field: It contains the actual data or information stored in the list.
  • Link field: Point towards the location of the next node or stores the address of the next node.
  • Head node: First node of the linked list.
  • Tail node: Last node of the linked list.

Node Structure of Singly Linked List

struct MyLinkedList
{
    int data;
    struct MyLinkedList *next;
};
struct MyLinkedList *head = NULL;
struct MyLinkedList *tail = NULL;

Algorithm for Creating a Singly Linked List

We assume head and tail are two pointers pointing to the first and last node of the linked list respectively. We also assume that the new node that we will create will be successfully allocated to the memory, if it not then creation of linked list is not possible.

  1. START
  2. Create a new node and store data in it.
  3. Set new->next = NULL
  4. If head == NULL
    • Set head = tail = new.
  5. If head != NULL
    1. tail->next = new
    2. Set tail = new
  6. END
void create()
{
    struct MyLinkedList *new = (struct MyLinkedList *)malloc(sizeof(struct MyLinkedList));
    if (new == NULL)
        printf("Creation of Linked List is not possible...");
    else if (head == NULL)
    {
        printf("Enter value: ");
        scanf("%d", &new->data);
        new->next = NULL;
        head = tail = new;
    }
    else
    {
        printf("Enter value: ");
        scanf("%d", &new->data);
        new->next = NULL;
        tail->next = new;
        tail = new;
    }
}

Algorithm to Traverse a Singly Linked List

We assume head is a pointer pointing to the first node of the linked list.

  1. START
  2. Create a temporary pointer for traversing (ptr).
  3. Set ptr = head
  4. If head == NULL
    • print "linked list is empty"
  5. Else
    • repeat steps 6 and 7 until ptr != NULL
  6. Print the data field of ptr.
  7. Set ptr = ptr->next
  8. END
void display()
{
    struct MyLinkedList *ptr = head;
    if (head == NULL)
        printf("Linked list is empty, so there is no element to show...");
    else
    {
        printf("Printing the elements of Linked list...\n");
        while (ptr != NULL)
        {
            printf("%d ", ptr->data);
            ptr = ptr->next;
        }
    }
}

Algorithm for Insertion at the Beginning

We assume head is a pointer pointing to the first node of the linked list. We also assume that the new node that we will create will be successfully allocated the memory, if it not then insertion of linked list is not possible.

  1. START
  2. Create a new node and store data in it.
  3. Set new->next = head
  4. Set head = new
  5. END
void insertAtBegin()
{
    struct MyLinkedList *new = (struct MyLinkedList *)malloc(sizeof(struct MyLinkedList));
    if (new == NULL)
        printf("Insertion not possible...");
    else
    {
        printf("Enter value to be inserted: ");
        scanf("%d", &new->data);
        new->next = head;
        head = new;
        printf("Insertion successful");
    }
}

Algorithm for Insertion at the End

We assume tail is a pointer pointing to the last node of the linked list. We also assume that the new node that we will create will be successfully allocated the memory, if it not then insertion of linked list is not possible.

  1. START
  2. Create a new node and store data in it.
  3. Set new->next = NULL
  4. Set tail->next = new
  5. Set tail = new
  6. END
void insertAtEnd()
{
    struct MyLinkedList *new = (struct MyLinkedList *)malloc(sizeof(struct MyLinkedList));
    if (new == NULL)
        printf("Insertion not possible...");
    else
    {
        printf("Enter value to be inserted: ");
        scanf("%d", &new->data);
        new->next = NULL;
        tail->next = new;
        tail = new;
        printf("Insertion successful");
    }
}

Algorithm for Insertion at Specific Position

We assume head is a pointer pointing to the first node of the linked list. We also assume that the new node that we will create will be successfully allocated the memory, if it not then insertion of linked list is not possible. The inserting position of element be pos.

  1. START
  2. Set i = 1
  3. Create a new node and a temporary pointer (ptr).
  4. Set ptr = head
  5. Repeat steps 6, 7 and 8 until ptr->next != NULL
  6. If i == pos - 1
    1. Store the data in the new node.
    2. Set new->next = ptr->next
    3. Set ptr->next = new
    4. Break the loop.
  7. Set i = i + 1
  8. Set ptr = ptr->next
  9. END
void insertAtAny()
{
    int pos, i = 1;
    struct MyLinkedList *new = (struct MyLinkedList *)malloc(sizeof(struct MyLinkedList));
    struct MyLinkedList *ptr = head;
    if (new == NULL)
        printf("Insertion not possible");
    else
    {
        printf("Enter the position you want to insert: ");
        scanf("%d", &pos);
        if (pos == 1)
            insertAtBegin();
        else if (pos == count() + 1)
            insertAtEnd();
        else if (pos <= 0 || pos > count() + 1)
            printf("Insertion not possible...");
        else{
            while (ptr->next != NULL)
        {
            if (i == pos - 1)
            {
                printf("Enter the value to be inserted: ");
                scanf("%d", &new->data);
                new->next = ptr->next;
                ptr->next = new;
                printf("Insertion successful...");
                break;
            }
            i++;
            ptr = ptr->next;
        }
        }
    }
}

Algorithm for Deletion at Beginning

We assume head and tail are two pointers pointing to the first and last node of the linked list respectively.

  1. START
  2. Create a temporary pointer (ptr).
  3. Set ptr = head
  4. If head == NULL
    • print "Linked list is already empty, so deletion not possible..."
  5. If head == tail
    1. print the data field of ptr.
    2. print "Linked list is now empty".
    3. Set head = tail = NULL
  6. Else
    1. Set head = head->next
    2. print the data field of ptr.
  7. Free the temporary pointer.
  8. END
void deleteAtBegin()
{
    struct MyLinkedList *ptr = head;
    if (head == NULL)
        printf("Deletion not possible...");
    else if (head == tail)
    {
        printf("Deleted element: %d\nLinked list is now empty...", ptr->data);
        head = tail = NULL;
    }
    else
    {
        head = head->next;
        printf("Deleted element: %d", ptr->data);
    }
    free(ptr);
}

Algorithm for Deletion at End

We assume head and tail are two pointers pointing to the first and last node of the linked list respectively.

  1. START
  2. Create a temporary pointer (ptr).
  3. Set ptr = head
  4. If head == NULL
    • print "Linked list is already empty, so deletion not possible..."
  5. If head == tail
    1. print the data field of ptr.
    2. print "Linked list is now empty".
    3. Set head = tail = NULL
  6. Else
    1. Repeat step 6.ii. until ptr->next != NULL
    2. Set ptr = ptr->next
    3. Set tail = ptr
    4. Set ptr = ptr->next
    5. Set tail->next = NULL
    6. print the data field of ptr.
  7. Free the temporary pointer.
  8. END
void deleteAtEnd()
{
    struct MyLinkedList *ptr = head;
    if (head == NULL)
        printf("Deletion not possible...");
    else if (head == tail)
    {
        printf("Deleted element: %d\nLinked list is now empty...", ptr->data);
        head = tail = NULL;
    }
    else
    {
        while (ptr->next != tail)
        {
            ptr = ptr->next;
        }
        tail = ptr;
        ptr = ptr->next;
        tail->next = NULL;
        printf("Deleted element: %d", ptr->data);
    }
    free(ptr);
}

Algorithm for Deletion at Specific Position

We assume head and tail are two pointers pointing to the first and last node of the linked list respectively. The deleting position of element be pos.

  1. START
  2. Set i = 1
  3. Create two temporary pointers (ptr and prev).
  4. Set ptr = head
  5. Repeat steps 6, 7, 8 and 9 until ptr->next != NULL
  6. Set prev = ptr
  7. Set ptr = ptr->next
  8. Set i = i + 1
  9. If i == pos
    1. Set prev->next = ptr->next
    2. print the data field of ptr.
    3. Free the temporary pointer.
    4. Break the loop.
  10. END
void deleteAtAny()
{
    int i = 1, pos;
    struct MyLinkedList *ptr = head;
    struct MyLinkedList *prev;
    printf("Enter the position to be deleted: ");
    scanf("%d", &pos);
    if (pos == 1)
        deleteAtBegin();
    else if (pos == count())
        deleteAtEnd();
    else if (pos <= 0 ||  pos > count())
        printf("Deletion not possible...");
    else
    {
        while (ptr->next != NULL)
        {
            prev = ptr;
            ptr = ptr->next;
            i++;
            if (i == pos)
            {
                prev->next = ptr->next;
                printf("Deleted element: %d", ptr->data);
                free(ptr);
                break;
            }
        }
    }
}

Algorithm for Searching in Linked List

We assume head is a pointer pointing to the first node of the linked list. Let the item to be searched be value.

  1. START
  2. Set i = 1 and k = 0
  3. Create a temporary pointer (ptr).
  4. Set ptr = head
  5. Repeat steps until ptr != NULL
  6. If ptr->data == value
    1. print "value is founded at position i"
    2. Set k = k + 1
  7. Set ptr = ptr->next
  8. Set i = i + 1
  9. If k == 0
    • print "item not founded".
  10. END
void search()
{
    int item, i = 1, k = 0;
    struct MyLinkedList *ptr = head;
    printf("Enter the element to be searched: ");
    scanf("%d", &item);
    while (ptr != NULL)
    {
        if ((*ptr).data == item)
        {
            printf("%d is founded at position %d\n", item, i);
            k++;
        }
        ptr = (*ptr).next;
        i++;
    }
    if (k == 0)
        printf("%d not founded...", item);
}

Comments

Post a Comment