01 Linked list implementation using C

Linked List Implementation using C:

• Linked List is dynamic data structure used to overcome disadvantage of static data structure (Array) i.e. waste of unused memory.

• linked list Data Structure allows to allocate memory at the time of program execution.

Note: Use RED line code in main function with some modification.

Define A node:-

typedef struct node

{

    int data;

    struct node* next;

}

Figure 1. A typical Node.

Typical Linked List Operations:

1. Create a node 
2. Prepend 
3. Traverse A linked list
4. Display
5. Append
6. Count
7. Search
8. Insert a node After a node
9. Insert A node before a node
10. Delete Front node
11. Delete back Node
12. Delete Middle Node
13. Reverse linked list 
14. Delete Whole Linked List

1. Adding a Node at the Beginning of Linked List(Create a node):-

Logic

• Declare a head pointer that always points to the first node of the list. 

                                                        node* head;

• To add a node at the beginning of list :- 

First, we need to create a new node. We will need to create a new node each time we want to insert a new node into the list so we can develop a function that creates a new node and return it.


Main Function Code:

printf("\n Enter data for create a node:");
scanf("%d",&data);
head=create(data,NULL);

Function For Creating a node:-

node* create(int data, node* next)

{

    node* new_node = (node*)malloc(sizeof(node)); // #Include<stdlib.h>   

    if(new_node == NULL)

    {

        printf("Error creating a new node.\n");

        exit(0);

    }

    new_node->data = data;

    new_node->next = next;

    return new_node;

}

2. Insert a node at the beginning of a non-empty linked list(Prepend):-

Figure 2. Prepend a  Node.

logic:

Create a node with data and head as a next pointer then update head to new_node. 

Main function code

printf("\n Enter data for prepend a node:");

scanf("%d",&data);

head=prepend(data,head);

C Function For Prepend:-

node* prepend(node* head,int data)

{

    node* new_node = create(data,head);

    head = new_node;

    return head;

}

3.Traverse the linked list:-

Logic:

Define cursor with head .Move cursor till it becomes NULL i.e. end node of linked list.

traverse function is useful for searching,counting nodes in linked list

C code for Traverse a Linked List:-

  

    node* cursor = head;

    while(cursor != NULL)

    {

                cursor = cursor->next;

    }

4. Display Linked List:-

Logic:
while Traversing the linked list till end node print cursor->data

display(head);

C  Function  for display linked list:-

int display(node *head)

{

    node *cursor = head;

    

    while(cursor != NULL)

    {

        printf("%d->",cursor->data);

        cursor = cursor->next;

    }

    return 0;

}

 5. Insert a node at the ending of a non-empty linked list(Append):-

Figure 3. Append a  Node.

Logic:

Travese the linked list till null then create a new_node with data and null points to next location. Finally Assign cursor->next to new_node

Main Function code:

printf("\n Enter data for append a node:");

scanf("%d",&data);

head=append(head,data);

display(head);

C function for Append:-

node* append(node* head, int data)

{

    // Traverse linked list till last node

    node *cursor = head;

    while(cursor->next != NULL)

        cursor = cursor->next;

    //create a new node 

    node* new_node =  create(data,NULL);

    cursor->next = new_node; //Assign new_node as a cursor->next

    return head;

}

 6. Count a node in  linked list :-

Logic:
while Traversing the linked list till end node Count node using a variable.

Main Function code:
int i=0;
i=count(head);
printf("number of nodes in linked list is %d",i);

C  Function  for display linked list:-

int display(node *head)

{

    node *cursor = head;

    int c=0;

    while(cursor != NULL)

    {

       c++;

        cursor = cursor->next;

    }

    return c;

}

 7. Search a node in  linked list :-

Logic:

While Traversing the linked list till end node compare node data with desired data. If data match with cursor data then return cursor to main function.
Search function used for finding desired node containing data. Also can be used for insert after and insert before function to find out cursor position.

Main Function code:

printf("\n Enter data for searching  a node:");
scanf("%d",&data);

previous=search(head,data);

C  Function  for search linked list:-

node* search(node* head,int data)

{

    node *cursor = head;

    while(cursor!=NULL)

    {

        if(cursor->data == data)

            return cursor;

        cursor = cursor->next;

    }

    return NULL;

}