C Tutorial

C Linked List

Linked List

Linked list is very common data structure and often used to store similar data in memory.

Linked list are not stored in adjacent locations and array occupy continuous locations.

Linked list is a collection of elements called nodes, each of which stores two items of information - an element of the list and a link.

Link is a pointer or an address that indicates explicitly the location of the node containing the successor of the list element.

C Program To Implement Linked List and Operations

#include<stdio.h>  


//structure contains data and link
struct node
{
    int data;
    struct node *link;
};

// Adds the node at the linked list end
void append(struct node **head, int data)
{
    struct node *temp, *tail;
    temp = *head;

    // if linked list is empty, adding as first node.
    if(*head == NULL)
    {
        temp = malloc( sizeof (struct node));
        temp->data = data;
        temp->link = NULL;
        *head = temp;
    }
    // adding in the last if linked list is not empty
    else
    {
        //Move to last node
        while(temp->link != NULL)
        {
            temp = temp->link;
        }
        tail = malloc( sizeof (struct node));
        tail->data = data;
        tail->link = NULL;
        temp->link = tail;
    }
    
}

// Displays the linked list
void display(struct node *head)
{
    printf("\n");
    // traversing entire linked list
    printf("\nhead==>");
    while(head != NULL)
    {
        printf("%d-->", head->data);
        head = head->link;
    }
    printf("tail");
}

// returns the number of elements in the linked list.
int count(struct node *head)
{
    int c = 0;
    while(head != NULL)                                                         
    {                                                                           
        head = head->link;          
        c++;
    } 
    return c;
}

// delete the element in the linked list.
int delete(struct node **head, int data)
{
    struct node *old, *temp;
    temp = *head;

    while(temp != NULL)
    {
        if(temp->data == data)
        {
            // deleting first node if data matches
            if(temp == *head)
            {
                *head = temp->link;
                free(temp);
                return 1;
            }
            // deleting other nodes except first node
            else
            {
                old->link = temp->link;
                free(temp);
                return 1;
            }
        }
        // old points to the previous node
        old = temp;
        temp = temp->link;
    }
    return 0;
}

// Add element as the linked list first elements
void addfirst(struct node **head, int data)
{
    struct node *temp;

    // adding new node
    temp = malloc(sizeof(struct node));

    temp->data = data;
    temp->link = *head;
    *head = temp;
}

// Add the element at specified location.
int addafter(struct node *head, int location, int data)
{
    struct node *temp, *tail;
    int i=1;

    //temp = *head;
    //printf("%d", location);
    temp = head;
    // skip till desired location
    while(i<location-1)
    {
        temp = temp->link;
        i++;
        if(temp == NULL)
        {
            printf("There are less than %d elements in the linked list", location);
            return 0;
        }
    }
    // insert new node at desired location
    tail = malloc(sizeof(struct node));
    tail->data = data;
    tail->link = temp->link;
    temp->link = tail;
    return 1;
}




void main()                                                                     
{       
    int op, data, loc;                                                                        
    struct node *ptr;                                                           
    // Empty linked list                                                        
    ptr = NULL;                                                                 
                                                                                
    printf("\nNumber of elements in the linked list: %d", count(ptr));          
    append(&ptr, 1);                                                            
    append(&ptr, 2);                                                            
    append(&ptr, 3);                                                            
                                                                                
    display(ptr);       
    printf("\nNumber of elements in the linked list: %d", count(ptr));

    do
    {
        printf("\nLinked List\n---------------\n1.Add element in begining \n2.Add element in end\n3.Add element in specific location\n4.delete\n5.display\n6.count\n0.exit");
        printf("\nEnter choice: ");
        scanf("%d", &op);
        switch(op)
        {
            case 3:
                printf("\nEnter element: ");
                scanf("%d", &data);
                printf("\nEnter location: ");
                scanf("%d", &loc);
                addafter(ptr, loc, data);
                break;
            case 1:
                printf("\nEnter element: ");                                    
                scanf("%d", &data);                                             
                addfirst(&ptr, data);
                break;
            case 2:
                printf("\nEnter element: ");                                    
                scanf("%d", &data);                                             
                append(&ptr, data);  
                break;
            case 4:
                printf("\nEnter element: ");                                    
                scanf("%d", &data);                                             
                delete(&ptr, data);  
                break;
            case 5:
                display(ptr);
                break;
            case 6:
                printf("\nNumber of elements in the linked list: %d", count(ptr));
                break;
        }
    }while(op>=1 && op<=6);
}

Compilation:

$ cc linked-list.c 
linked-list.c: In function ‘append’:
linked-list.c:18:16: warning: implicit declaration of function ‘malloc’ [-Wimplicit-function-declaration]
         temp = malloc( sizeof (struct node));
                ^~~~~~
linked-list.c:18:16: warning: incompatible implicit declaration of built-in function ‘malloc’
linked-list.c:18:16: note: include ‘’ or provide a declaration of ‘malloc’
linked-list.c:31:16: warning: incompatible implicit declaration of built-in function ‘malloc’
         tail = malloc( sizeof (struct node));
                ^~~~~~
linked-list.c:31:16: note: include ‘’ or provide a declaration of ‘malloc’
linked-list.c: In function ‘delete’:
linked-list.c:76:17: warning: implicit declaration of function ‘free’ [-Wimplicit-function-declaration]
                 free(temp);
                 ^~~~
linked-list.c:76:17: warning: incompatible implicit declaration of built-in function ‘free’
linked-list.c:76:17: note: include ‘’ or provide a declaration of ‘free’
linked-list.c:83:17: warning: incompatible implicit declaration of built-in function ‘free’
                 free(temp);
                 ^~~~
linked-list.c:83:17: note: include ‘’ or provide a declaration of ‘free’
linked-list.c: In function ‘addfirst’:
linked-list.c:100:12: warning: incompatible implicit declaration of built-in function ‘malloc’
     temp = malloc(sizeof(struct node));
            ^~~~~~
linked-list.c:100:12: note: include ‘’ or provide a declaration of ‘malloc’
linked-list.c: In function ‘addafter’:
linked-list.c:125:12: warning: incompatible implicit declaration of built-in function ‘malloc’
     tail = malloc(sizeof(struct node));
            ^~~~~~
linked-list.c:125:12: note: include ‘’ or provide a declaration of ‘malloc’

Output:

$ ./a.out 

Number of elements in the linked list: 0

head==>1-->2-->3-->tail
Number of elements in the linked list: 3
Linked List
---------------
1.Add element in begining 
2.Add element in end
3.Add element in specific location
4.delete
5.display
6.count
0.exit
Enter choice: 1

Enter element: 23

Linked List
---------------
1.Add element in begining 
2.Add element in end
3.Add element in specific location
4.delete
5.display
6.count
0.exit
Enter choice: 5


head==>23-->1-->2-->3-->tail
Linked List
---------------
1.Add element in begining 
2.Add element in end
3.Add element in specific location
4.delete
5.display
6.count
0.exit
Enter choice: 6

Number of elements in the linked list: 4
Linked List
---------------
1.Add element in begining 
2.Add element in end
3.Add element in specific location
4.delete
5.display
6.count
0.exit
Enter choice: 2

Enter element: 45

Linked List
---------------
1.Add element in begining 
2.Add element in end
3.Add element in specific location
4.delete
5.display
6.count
0.exit
Enter choice: 5


head==>23-->1-->2-->3-->45-->tail
Linked List
---------------
1.Add element in begining 
2.Add element in end
3.Add element in specific location
4.delete
5.display
6.count
0.exit
Enter choice: 6

Number of elements in the linked list: 5
Linked List
---------------
1.Add element in begining 
2.Add element in end
3.Add element in specific location
4.delete
5.display
6.count
0.exit
Enter choice: 4

Enter element: 2

Linked List
---------------
1.Add element in begining 
2.Add element in end
3.Add element in specific location
4.delete
5.display
6.count
0.exit
Enter choice: 5


head==>23-->1-->3-->45-->tail
Linked List
---------------
1.Add element in begining 
2.Add element in end
3.Add element in specific location
4.delete
5.display
6.count
0.exit
Enter choice: 6

Number of elements in the linked list: 4
Linked List
---------------
1.Add element in begining 
2.Add element in end
3.Add element in specific location
4.delete
5.display
6.count
0.exit
Enter choice: 0

$ ./a.out 

Number of elements in the linked list: 0

head==>1-->2-->3-->tail
Number of elements in the linked list: 3
Linked List
---------------
1.Add element in begining 
2.Add element in end
3.Add element in specific location
4.delete
5.display
6.count
0.exit
Enter choice: 3

Enter element: 45

Enter location: 2

Linked List
---------------
1.Add element in begining 
2.Add element in end
3.Add element in specific location
4.delete
5.display
6.count
0.exit
Enter choice: 5


head==>1-->45-->2-->3-->tail

« Previous Next »