C Program for Singly Linked List

What is a Linked List?

A Linked List is a linear data structure whose list elements are linked using pointers unlike array elements which are stored in continuous memory locations.

Illustration of Singly Linear Linked List



Here 12,99,37 is data corresponding to every node (Every box). Here Each (box) Node has two parts i.e the data part and the pointer part. It means this structure is storing some data and a pointer which is pointing to next node of linked list. That is in the second part, the address of next node in linked list is stored.

NOTE: In singly linear linked list we can traverse the list in only forward direction until the list terminates.

Why to use a Linked List?

To overcome the limitations of array linked list is used.

Limitations of Array

  1. Size of arrays is fixed. So if we want to declare an array we must know the upper limit, maximum elements to store in an array. Also if we declared an array of size 100 but we used only 10 then 90 locations are wasted.
  2. Insertion is expensive. If we want to insert an element 22 in this arr[]=[10,20,30,40,50] array then to maintain the order we have to move all elements after 20 by 1 position.
  3. Deletion is also expensive. If we want to delete 20 from arr[] we have to move all elements after 20 1 position towards 10.

Advantages Over Arrays

  1. Dynamic Size - So we can increase size of LL at run time
  2. Easier insertion and deletion of elements

Drawbacks of Linked List

  1. We cannot access elements randomly. i.e binary search is not allowed. We have to traverse the linked list sequentially starting from the first node.
  2. Extra memory is required to store pointer.
  3. Not cache friendly. In arrays there is locality of reference since it is continues memory but it is not the case in linked lists.
Problem: Write a program to create and display singly linear linked list.

Solution:
  1. Create a new data type that is define a structure with two elements i.e. data element and pointer.
  2. Take input from user to create desired number of nodes.
  3. Allocate memory for new node.
  4. Set pointer of new node to NULL.
  5. Accept data element.
  6. If it is first node then call it as head. Also assign temp=head.
  7. If it is not first element then store the address of new node in pointer part of previous node i.e temp->next . Move the temporary pointer ahead i.e assign temp=new_node.
  8. Finally return the address of newly created node.
  9. Now to display the linked list means displaying the data. For this we need to traverse the linked list starting from head.
  10. Initialize a temporary pointer with head in for loop. move the pointer 1 position ahead after every iteration as temp=temp->next until temp!=NULL.
  11. In every iteration print the data part.

C Program:

Get This Program:  

Problem: Write a menu driven program to create, insert, delete a node by position, delete a node by values, to search for given values in linked list.

Solution:
  1. We have discussed create and display function above.
  2. Now to delete a node by position from linked list use the for loop you used in display function. 
    for(temp=head;temp!=NULL;temp=temp->next)
printf(" %d ",temp->data);
  3. Check if node to be deleted is the first node or not. If it fist the assign head to temporary pointer variable. Set head=temp->next i.e set head to next node. Now free the temp.
  4. If it is not the first element then in else part modify the for loop as 
    for(temp=head,i=1;temp!=NULL && i<pos-1;temp=temp->next,i++)
printf(" %d ",temp->data);
    Here we have introduced another counter i to count position of node. Move the temp pointer to one position before the node to be deleted. Now assign another temporary pointer temp1=temp->next. So now temp1 is the node that we have to delete. So we have to assign temp-next=temp1->next that we are storing the address of node next to temp1 in temp->next.
  5. Now free temp1.
  6. Return head.
  7. Delete by value is similar to this. Just check the data part with given values.
  8. For Search Function: Initialize a flag variable to 0. Traverse the linked list as usual. IF data is found change value of flag to 1 and break the loop. outside of loop check flag and depending on that print appropriate message. you can also use counter to print the position.

C Program:

Get This Program:  

Singly Circular Linked List

In this linked list we just have to connect the last node with head instead of connecting it to NULL. But how we will get an idea that we have traversed the list once or twice? For that keep the first node i.e head blank. So our first data node will be the node next to head. So one iteration or traversal is completed when we meet head gain.

Problem: Write a C program to create a singly circular linked list and to perform different operations on it viz.
1] Displaying the list
2] Inserting a new node
3] Calculating the length of list
4] Deleting node by position
5] Deleting node by value of data in it
6] Searching for given data in singly linked list

C Program:

Get This Program:  
Labels:











Labels