Linked List in Data Structures

  • If the memory is allocated before the execution of a program, it is fixed and cannot be changed. We have to adopt an alternative strategy to allocated memory only when it is required.
  • There is a special data structure called Linked list that provides a more flexible storage system and it does not require the use of arrays.
  • When dealing with many problems we need a dynamic list, dynamic in the sense that the size requirement need not be known at compile time. Thus, the list may grow or shrink during runtime.
  • A linked list is a data structure that is used to model such a dynamic list of data items, so the study of the linked lists as one of the data structures is important.
  • Linked list is a data structure that is free from the aforementioned restrictions.
  • A linked list does not store its elements in consecutive memory locations and the user can add any number of elements to it. However, unlike an array, a linked list does not allow random access of data.
  • Elements in a linked list can be accessed only in a sequential manner. But like an array, insertions and deletions can be done at any point in the list in a constant time.
  • Linked list are special list of some data elements linked to one another. The logical ordering is represented by having each element pointing to the next element. Each element is called a node, which has two parts. INFO part which stores the information and POINTER which points to the next element.

Advantages of Linked List

  • Linked lists are dynamic data structures: That is,they cangroworshrink during execution ofa program.
  • Efficient memory utilization: Here memory is not pre-allocated. Memory is allocated whenever it is required. And it is deallocated (free) when it is no longer needed.
  • Insertion and deletions are easier and efficient: Linked list provide flexibility in inserting a data item at a specified position and deletion of a data item from the given position.
  • Elements of linked list are flexible: It can be primary data type or user defined data types.

Disadvantages of Linked List

  • Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
  • It cannot be easily sorted.
  • We must traverse 1/2 the list on average to access any element.
  • More complex to create than an array.
  • Extra memory space for a pointer is required with each element of the list.

Operations on Linked list

The basic operations to be performed on the linked list as follows :

  • Creation
  • Insertion
  • Deletion
  • Traversing
  • Searching
  • Concatenation
  • Display

Types of Linked list

Basically, we can put linked list into the following four type :

  • Singly linked list
  • Doubly linked list
  • Circular linked list
  • Circular doubly linked list

Program

Here is a program for building and printing the elements of the linked list :

#include<stdio.h>
#include<stdlib.h>
struct node
{
    int data;
    struct node *link;
    };
    struct node *insert(struct node *p, int n)
    {
    struct node *temp;
    /* if the existing list is empty then insert a new node as the starting node */
    if(p==NULL)
    {
        p=(struct node *)malloc(sizeof(struct node)); /* creates new node
        data value passes
        as parameter */
        if(p==NULL)
        {
            printf("Error\n");
            exit(0);
        }
    p-> data = n;
    p-> link = p; /* makes the pointer pointing to itself because it is a circular list*/
    }
    else
    {
    temp = p;
    /* traverses the existing list to get the pointer to the last node of it */
    while (temp-> link != p)
    temp = temp-> link;
    temp-> link = (struct node *)malloc(sizeof(struct node)); /*creates new node using data value passes as parameter and puts its address in the link field of last node of the existing list*/
    if(temp -> link == NULL)
    {
    printf("Error\n");
    exit(0);
    }
    temp = temp-> link;
    temp-> data = n;
    temp-> link = p;
    }
    return (p);
    }
    void printlist ( struct node *p )
    {
    struct node *temp;
    temp = p;
        printf("The data values in the list are\n");
    if(p!= NULL)
    {
    do
    }
    else
    {
    printf("%d\t",temp->data);
    temp=temp->link;
    } while (temp!= p);
     printf("The list is empty\n");
    }
    void main()
    {
    int n;
    int x;
    struct node *start = NULL ;
    printf("Enter the nodes to be created \n");
    scanf("%d",&n);
    while ( n -- > 0 )
    {
        printf( "Enter the data values to be placed in a node\n");
        scanf("%d",&x);
        start = insert ( start, x );
    }
    printf("The created list is\n");
    printlist ( start );
}

Explanation

  • This program uses a strategy of inserting a node in an existing list to get the list created. An insert function is used for this.
  • The insert function takes a pointer to an existing list as the first parameter, and a data value with which the new node is to be created as a second parameter, creates a new node by using the data value, appends it to the end of the list, and returns a pointer to the first node of the list.
  • Initially the list is empty, so the pointer to the starting node is NULL. Therefore, when insert is called first time, the new node created by the insert becomes the start node.
  • Subsequently, the insert traverses the list to get the pointer to the last node of the existing list, and puts the address of the newly created node in the link field of the last node, thereby appending the new node to the existing list.
  • The main function reads the value of the number of nodes in the list. Calls iterate that many times by going in a whileloop to create the links with the specified number of nodes.

Points to Remember

  • Linked lists are used when the quantity of data is not known prior to execution.
  • In linked lists, data is stored in the form of nodes and at runtime, memory is allocated for creating nodes.
  • Due to overhead in memory allocation and deallocation, the speed of the program is lower.
  • The data is accessed using the starting pointer of the list.