Singly Linked List Implementation

Linked List is an another Abstract Data type
  1. A linked list is a data structure which contain the list of the elements
  2. The elements are stored anywhere in the memory and linked with the address.
  3. Linked list is used when the quantity of the data is unknown
  4. Data is stored in the form of node and at the run-time memory is allocate for creating a node
  5. Data is accessed using the starting pointer of the list

Array versus Linked List

Array suitable for 
  1.        Randomly access the elements
  2.        Searching the list of particular elements
  3.        Inserting or Deleting the particular elements
Linked List suitable for
  1.        Inserting/Deleting the elements
  2.        Application where sequential access is required
  3.        In situation where number of elements are unknown

Types of Linked List

  1. Singly linked List
  2. Doubly Linked List
  3. Circular Linked List

Application of Linked List

  1. Linked list is used for implementation of other ADT (Stack,Queue,etc)
  2. Linked list is used for Implementation of graph
  3. Linked list allows dynamic allocation
  4. Linked list efficiently manages the memory utilization
  5. Linked list (circular) help in multi programming 
  6. Undo operation of MS word and Photoshop is manage by Linked list.

Implementation of Singly Linked List

  1. Singly linked list is collection of the node with connected links
  2. Data field hold the data and address field store the address of next node
  3. Address field of the last node hold the NULL.
  4. Head pointer always point to the first node of the list
First step of implementation
  1. Design the model of the node with data and address field using structure in C
  2. For each node implementation dynamically allocate the memory 
  3. Assign a Head Pointer to point to the first node of the list
  4. Decide the function for different types of operations (inserting,deleting, etc.)
#include
#include

struct node
{
int data;
struct node *next;
}*head=NULL,*temp=NULL;

void insertNode()
{
int n;
struct node *newNode;
newNode=(struct node*)malloc(sizeof(struct node));
printf("insert the data\n");
scanf("%d",&n);
newNode->data=n;
if(head==NULL)
{
head=newNode;
newNode->next=NULL;
}
else
{
newNode->next=head;
head=newNode;
}
}

void display()
{
if(head==NULL)
printf("linked list is empty");
else
{
temp=head;
while(temp->next!=NULL)
{
printf("%d->",temp->data);
temp=temp->next;
}
printf("%d\n",temp->data);
}
}

void insertAtend()
{
int n;
struct node *newNode;
newNode=(struct node*)malloc(sizeof(struct node));
printf("insert the data\n");
scanf("%d",&n);
newNode->data=n;
temp=head;
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newNode;
newNode->next=NULL;
}

void delAtf()
{
if(head==NULL)
printf("linked list is empty\n");
else
{
if(head->next==NULL)
{
temp=head;
head=NULL;
free(temp);
}
else
{
temp=head;
head=temp->next;
free(temp);
}
}
}

void main()
{
int choice;
while(1)
{
printf("1:insert the node\n");
printf("2:display the data\n");
printf("3:insert at the end\n");
printf("4:delete from front\n");
printf("5: exit");
printf("------------------------\n");
printf("enter your choice\n");
scanf("%d",&choice);
switch(choice)
{
case 1:
    insertNode();
    break;
case 2:
    display();
    break;
case 3:
    insertAtend();
    break;
case 4:
    delAtf();
    break;
case 5:
    exit(0);
    break;
default :
    printf("invalid choice");
}
}
}

Time complexity Analysis for the Operations

  1. Print a list will take O(n)
  2. Find the K th element within the list will take O(n)
  3. Inserting and deleting will take O(1)
  4. Inserting/deletion of node is easier than finding the k the element in the list

Problem with Single Linked List

  1. Singly linked list allow the traversal of the list in single direction only
  2. Deleting a node need to keep the address of the previous node
  3. If link is lost between the node, then rest of the elements gets corrupted or untraceable
****************************************************************
This code you can get it through below link

https://drive.google.com/open?id=0B2O8tJ9QXc-3MHNFTzBDMjFvTVE

Comments

Post a Comment

Popular posts from this blog

Types of Algorithm and Its Complexity Analysis

Image
In this post, we will learn types of Algorithm and its time complexity analysis with examples  An algorithm is divided into two forms called iterative and recursive, as shown above. Firstly, we analyze the time complexity of the iterative algorithm and then recursive. Example 1:                           A()                           {                            int i;                            for(i=1 to n)   % loop run n times                            pf("deepa");                           } First, the above function is fall into the independent category. Hence, the running time of the loop will be n and it print the particular name n times. Therefore, the worst case time complexity of this algorithm will be O(n). Example 2:                          A()                         {                         int i;                         for(i=1, i^2<=n, i++)                         printf("deepa");                         } Similarly
Read more

First Step of Problem Solving Using Data Structure and Algorithm

Image
What is problem ? A state of difficulty that need to be resolve A problem exist and its solution needs to be  attain either correct or incorrect A problem gives an opportunity to improve the current state A problem is a difference between the  current state and goal state Problem Faced in daily life        Like making the decisions what should i wear today to look good? what career? what job? what shoes? what course? What happens when bad decisions are made ? Wastage of time and resource   Six steps to ensure  a Best decision in PROBLEM SOLVING Identify the problem first understand the problem Identify the different way to solve the problem (efficient) Select the best one solution among the various alternative solutions Identify the list of steps to solve a problem (instructions) Evaluate the solution of given problem (different set of inputs) Take the problem of and apply the six step of problem solving     A   Water Jug Pro
Read more

Asymptotic Notations

Image
 In computer science, any problem can be solved using the programming language. And a particular problem can have multiple solutions in terms of Algorithm. To find out which one is the best algorithm for a problem, we analyse it in terms of time and space.  To define the time and space complexity of an algorithm, we use the Asymptotic notation. Mostly three types of Asymptotic notation is widely preferred to represent the complexity of the algorithm. Big-O mathematically represented as O The X-axis of the above graph showing the size of the input (n) and Y axis showing the increase in  time (t) . In the graph,   f(n) function showing the increase of time as input   size   n is increasing for a particular algorithm. Beside, the another function called cg(n) showing the worst case of f(n) . Hence, in the above graph cg(n)  is above the f(n). If we bound the time complexity or f(n) of a given algorithm in terms of input n with another function called cg(n) for all
Read more