Linked List data structure and its types

Simple Linked List

In computer science, a linked list is a linear collection of data elements, called nodes, each pointing to the next node by means of a pointer. It is a data structure consisting of a group of nodes which together represent a sequence. Under the simplest form, each node is composed of data and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing efficient insertion or removal from arbitrary element references.

A linked list whose nodes contain two fields: an integer value and a link to the next node. The last node is linked to a terminator used to signify the end of the list.

Linked lists are among the simplest and most common data structures. They can be used to implement several other common abstract data types, including lists (the abstract data type), stacks, queues, associative arrays, and S-expressions, though it is not uncommon to implement the other data structures directly without using a list as the basis of implementation.

The principal benefit of a linked list over a conventional array is that the list elements can easily be inserted or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk, while an array has to be declared in the source code, before compiling and running the program. Linked lists allow insertion and removal of nodes at any point in the list, and can do so with a constant number of operations if the link previous to the link being added or removed is maintained during list traversal.

On the other hand, simple linked lists by themselves do not allow random access to the data, or any form of efficient indexing. Thus, many basic operations — such as obtaining the last node of the list (assuming that the last node is not maintained as separate node reference in the list structure), or finding a node that contains a given datum, or locating the place where a new node should be inserted — may require sequential scanning of most or all of the list elements. The advantages and disadvantages of using linked lists are given below.

Linked List Representation

Linked list can be visualized as a chain of nodes, where every node points to the next node.

As per the above illustration, following are the important points to be considered.

·      HEAD pointer points to first node in the List.

·      Each link carries a data field(s) and a link field called info part.

·      Each link point to next node called link part.

·      Last link carries a link as null to mark the end of the list.

Types of Linked List

Following are the various types of linked list.

·      Simple Linked List − Item navigation is forward only.

·      Doubly Linked List − Items can be navigated forward and backward.

·      Circular Linked List − Last item contains link of the first element as next and the first element has a link to the last element as previous.

Basic Operations

Following are the basic operations supported by a list.

·      Insertion − Adds an element at the beginning of the list.

·      Deletion − Deletes an element at the beginning of the list.

·      Display − Displays the complete list.

·      Search − Searches an element using the given key.

·      Delete − Deletes an element using the given key.

Insertion Operation

Adding a new node in linked list is a more than one step activity. We shall learn this with diagrams here. First, create a node using the same structure and find the location where it has to be inserted.

Imagine that we are inserting a node B (NewNode), between A (LeftNode) and C (RightNode). Then point B.next to C −

It should look like this −

Now, the next node at the left should point to the new node.

This will put the new node in the middle of the two. The new list should look like this −

Similar steps should be taken if the node is being inserted at the beginning of the list. While inserting it at the end, the second last node of the list should point to the new node and the new node will point to NULL.

Deletion Operation

Deletion is also a more than one step process. We shall learn with pictorial representation. First, locate the target node to be removed, by using searching algorithms.

The left (previous) node of the target node now should point to the next node of the target no

This will remove the link that was pointing to the target node. Now, using the following code, we will remove what the target node is pointing at.

We need to use the deleted node. We can keep that in memory otherwise we can simply deallocate memory and wipe off the target node completely.

Reverse Operation

This operation is a thorough one. We need to make the last node to be pointed by the head node and reverse the whole linked list.

First, we traverse to the end of the list. It should be pointing to NULL. Now, we shall make it point to its previous node −

We have to make sure that the last node is not the lost node. So we'll have some temp node, which looks like the head node pointing to the last node. Now, we shall make all left side nodes point to their previous nodes one by one.

Except the node (first node) pointed by the head node, all nodes should point to their predecessor, making them their new successor. The first node will point to NULL.

We'll make the head node point to the new first node by using the temp node.

The linked list is now reversed.

Advantages

·        Linked lists are a dynamic data structure, which can grow and be pruned, allocating and deallocating memory while the program is running.

·        Insertion and deletion node operations are easily implemented in a linked list.

·        Dynamic data structures such as stacks and queues can be implemented using a linked list.

·        There is no need to define an initial size for a Linked list.

·        Items can be added or removed from the middle of list.

Disadvantages

• ·     They use more memory than arrays because of the storage used by their pointers.
• ·     Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
• ·  Nodes are stored incontiguously, greatly increasing the time required toaccess individual elements within the list, especially with a CPU cache.
• ·    Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards[1] and while doubly linked lists are somewhat easier to read, memory is consumed in allocating space for a back-pointer.A linked list is a sequence of data structures, which are connected together via links.
• ·        Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array. Following are the important terms to understand the concept of Linked List.

/*program to implement simple linked list using c language*/

#include <stdio.h>

#include<conio.h>
#include<malloc.h>
//#define NULL 0
typedef struct nodetype
{
    int info;
    struct nodetype *link;
}node;

int main()
{

    node *head=NULL;
    int total,loc,pos,value;
    node* create();//function to create list
    void traverse(node*);//function to traverse list
    int count(node*);//program to count no of nodes in list
    int search(node*,int);//search the value and return its location
    total=0,value=0,loc=0;pos=0;
    printf("\n enter the elements in list-->\n");
    head=create();
    printf("\n elements in the list are--->");
    traverse(head);
    printf("\n no of nodes in the list are--->");
    total=count(head);
    printf("%d",total);
    printf("\n Enter the value you want to search in the list--->");
    scanf("%d",&value);
    loc=search(head,value);
    if(loc==0)
     printf("\n value not found");
else
    printf("\n %d is present at %d location  in the list",value,loc);
    printf("\n thank you");
    return 0;
}


node* create()
{
    node *ptr,*head=NULL;
    int data;
    char ch='y';
    while(ch=='y'||ch=='Y')
    {
    if(head==NULL)
    {
        head=(node*)malloc(sizeof(node));
        ptr=head;
    }
    else
    {
        ptr->link=(node*)malloc(sizeof(node));
        ptr=ptr->link;
    }
    printf("\n enter the value you want to input in list:");
    scanf("%d" ,&data);
    ptr->info=data;
    fflush(stdin);
    printf("\n do you want to create more nodes______if yes then press y-->");
    scanf( "%c" ,&ch);
    }
    ptr->link=NULL;
    return head;
}

void traverse(node *head)
{
    node *ptr=head;
    while(ptr!=NULL)
    {
        printf("\n value in link list:  %d",ptr->info);
        ptr=ptr->link;
    }

}

int count(node *head)
{
node *ptr=head;
int count=0;
    while(ptr!=NULL)
    {
        count++;
        ptr=ptr->link;
    }
    return count;
}

int search(node *head,int item)
{
node *ptr=head;
int loc=0;
    while(ptr!=NULL )
    {
        loc++;
       
        if(item==ptr->info)
{
loc++;
   return loc;
   }
        if(ptr->link!=NULL) 
        ptr=ptr->link;        
        else
break; 

}return 0;


}

Program for singly linked list with multiple info part using c:-

#include<conio.h>
#include<malloc.h>
#include<string.h>

typedef struct nodetype
{
char stu_name[20];
    int stu_rollno;
    char stu_semester[10];
    long long int stu_phone;
    struct nodetype *link;
}node;

int main()
{
    node *head=NULL;
    node* create();
    void traverse(node*);
    printf("\n enter the student record in list-->\n");
    head=create();
    printf("\n Recordsin the list are--->");
    traverse(head);
    return 0;
}

//function to create new nodes
node* create()
{
    node *ptr,*head=0;
    char name[20],sem[20];
    int rollno;
long long phone;
    char ch='y';
    while(ch=='y'||ch=='Y')
    {
    if(head=NULL)//list empty
    {
        head=(node*)malloc(sizeof(node));//creating new node as a first node
        ptr=head;
    }
    else
    {
        ptr->link=(node*)malloc(sizeof(node));//creating new node next to current node
        ptr=ptr->link;
    }
    printf("\n enter the name of student:");
    scanf("%s" ,&name);
    strcpy(ptr->stu_name,name);//we have to copy string values we cant no directly assign them
    printf("\n enter the roll no of student:");
    scanf("%d" ,&rollno);
    ptr->stu_rollno=rollno;
    printf("\n enter the semester of student:");
    scanf("%s" ,&sem);
    strcpy(ptr->stu_semester,sem);
    printf("\n enter the mobile no of student:");
    scanf("%llu" ,&phone);
    ptr->stu_phone=phone;
    fflush(stdin);
    printf("\n do you want to enter more records*********if yes then press y*******");
    scanf( "%c" ,&ch);
    }
    ptr->link=NULL;
    return head;
}
/*printing records*/
void traverse(node *head)
{
    node *ptr=head;
    while(ptr!=NULL)
    {
        printf("\n Student's Name':  %s",ptr->stu_name);
        printf("\n Student's Roll No':  %d",ptr->stu_rollno);
        printf("\n Student's Semester':  %s",ptr->stu_semester);
        printf("\n Student's Phone No':  %llu",ptr->stu_phone);
        ptr=ptr->link;
    }

}

Output