Linked List in C

Linked Lists in C Programming Language

Linked List in C is a linear type of data structure, which has some major advantages over arrays and other linear data structures. Eventhough Linked List are linear Data Strucutres, the nodes of a Linked Lists need not be stored in a contiguous manner and can be scatter in memory. Linked is constructed of two parts-:

  • Node – It contains the data
  • Pointer – It contains the address of the next node
Linked List in C

Why do we prefer Linked Lists ?

Linked Lists are a more preferable data structure to use than any other data structure if we are willing to store large amount of data, as insertion and deletion process in linked lists are fairly easy and less complicated in comparison with other data structures.

According to Wikipedia

Linked List in C Node

How to Create Linked List in C?

For constructing a Linked List in C. We use a user-defined data type.

  • We make a structure in C for using Linked List. We design a user-defined struct data type.
  • That contains the following –
    • Data: A data type, for storing the desired data
    • Next Pointer: Pointer variable for storing the address of the next node in the Linked List.

Syntax for creating a node in Linked List in C

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

The above code will create a new node in a Linked List which will store an integer datatype.

Advantages of using Linked List in C

  1. No restriction of size:  Unlike arrays, we do not have to declare the size of the linked list before creating it.
  2. No memory wastage: Unlike arrays, in Linked List, we can add or delete nodes and their memory dynamically, however in arrays, the whole initialized memory is consumed even if we are using the first few indexes to store values.
  3. Linked List does not need contiguous memory: If one node has an address of 1000 then the next node may have the address 2000, we can simply connect these non-contiguous memories using pointers.
  4. Insertion and Deletion Operation in Linked Lists are pretty easy and less complicated.

Disadvantages of using Linked List in C

  1. Although insertion and deletion are not difficult tasks in Linked List, searching in Linked List is very difficult.
  2. We cannot use efficient searches like Binary Search.
  3. It takes more space, as it stores the address also.
  4. Linked lists are not cached friendly as arrays are stored in the contiguous format they can be cached easily
  5. Loss of data threat is there, if we lose one pointer location the rest of the linked list can’t be accessed.

Types of Linked Lists

There are three type of linked lists in C
  1. Singly Linked Lists
  2. Double Linked Lists
  3. Circular Linked Lists

Code for Implementing Singly Linked List in C

Run
// Linked List in C Implementation code
#include <stdio.h>
#include <stdlib.h>
//stdlib is included because we will be using  ‘malloc’

// creating a node in linked list
struct Node { 
    int data; 
    struct Node* next; 
    // Pointer pointing towards next node
};

//function to print the linked list
void display(struct Node* node) 
{ 
    while (node != NULL) { 
        printf(" %d ", node->data); 
        node = node->next; 
    } 
}

// main function
int main() 
{ 
    //creating 4 pointers of type struct Node
    //So these can point to address of struct type variable
    struct Node* head = NULL; 
    struct Node* node2 = NULL; 
    struct Node* node3 = NULL; 
    struct Node* node4 = NULL; 

    // allocate 3 nodes in the heap 
    head =  (struct Node*)malloc(sizeof(struct Node)); 
    node2 = (struct Node*)malloc(sizeof(struct Node)); 
    node3 = (struct Node*)malloc(sizeof(struct Node)); 
    node4 = (struct Node*)malloc(sizeof(struct Node)); 

   
    head->data = 10; // data set for head node 
    head->next = node2; // next pointer assigned to address of node2 

    node2->data = 20; 
    node2->next = node3; 

    node3->data = 30;
    node3->next = node4; 

    node4->data = 40;
    node4->next = NULL; 
   

    display(head);

    return 0; 
}
Output

10   20   30   40

Basic Operations on Linked Lists

  • Insertion
  • Deletion
  • Searching
  • Printing

The below program shows all the following –

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

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


void insertFirst(struct Node** head, int data){
    
    // dynamically create memory for this newNode
    struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
    
    // assign data value
    newNode->data = data;
    // change the next node of this newNode 
    // to current head of Linked List
    newNode->next = *head;

    //re-assign head to this newNode
    *head = newNode;
}

void deleteFirst(struct Node** head){
    struct Node* temp = *head;
  
    // if there are no nodes in Linked List can't delete
    if(*head == NULL){
        printf("Linked List Empty, nothing to delete");
        return;
    }
    
    // move head to next node
    *head = (*head)->next;
    
    printf("\n%d deleted\n\n", temp->data);
    free(temp);
}

void display(struct Node* node){
    printf("Linked List : \n");
    
    // as linked list will end when Node is Null
    while(node!=NULL){
        printf("%d ",node->data);
        node = node->next;
    }
    printf("\n\n");
}

void search(struct Node* node, int key){

    int pos = 1;
    int flag = 0;
    while(node!=NULL)
    {
        if(node->data == key){
            flag = 1;
            break;
        }
        node = node->next;
        pos++;
    }
    if(flag)
        printf("%d present at %d position\n", key, pos);
    else
        printf("%d not present\n");
}

// Note by default insertion/deletion happens at starting node
// of Linked List
int main()
{
    struct Node* head = NULL;

    // Need '&' i.e. address as we need to change head
    insertFirst(&head,50);
    insertFirst(&head,40);
    insertFirst(&head,30);
    insertFirst(&head,20);
    insertFirst(&head,10);

    // no need of '&' as we are not changing head just displaying Linked List
    display(head); 

    search(head, 30);
    search(head, 100);
    
    deleteFirst(&head);

    display(head); 

    return 0; 
}

Output

Linked List : 
10 20 30 40 50 

30 present at 3 position
100 not present

10 deleted

Linked List : 
20 30 40 50