Single linked list program

Introduction
• If the memory is allocated before the
execution of program, it is fixed cannot be
changed.
• We have to adopt an alternative strategy
to allocated memory only when it is
required.
• There is special data structure called
linked list that provides a more flexible
storage system and it does not require the
use of arrays.
07/04/25 2
 Linked List
• Linked lists are special list of some data
elements linked to one together.
• The logical ordering is representing by
having each element pointing to the next
element.
• Each element is called a node, which has
two parts.
– INFO parts which stores the information
– POINTER which points to next element.

07/04/25 3
 Singly Linked List

start

info link info link info link info null

07/04/25 4
 Advantage of Linked List
• Linked list are dynamic data structures:
– i.e., they can grow or shrink during the execution of a
program.
• Efficient memory utilization:
– Here, memory is not pre-allocated. Memory is
allocated whenever it is required. And it is de-
Allocated (removed) when it is no longer needed.
• Insertion and deletions are easier and efficient:
– Linked list provide flexibility in inserting a data item at
a specified position and deletion of a data item from
the given position.

07/04/25 5
 Key terms
• A linked list is a non-sequential collection
of data items called nodes.
• These nodes in principle are structures
containing fields. Each node in a linked list
basically two fields.
– Data fields:
• it contains an actual value to be stored and
processed.
– Link fields
• The link field contains the address of the next data
item in the linked list.
07/04/25 6
 Key terms contd…
• Null Pointer
– The link field of the last node contains NULL
rather than the valid address. It is a null
pointer and indicates the end of list.
• External pointer
– It is a pointer to the very first node in the
linked list, it enables us to access the entire
linked list.
• Empty List
– If the nodes are not present in a linked list,
then it is called an empty linked list. It is also
called null list.
07/04/25 7
 Representation of Linked List
• Suppose we want to store list of integers, then the linked
list can be represented in memory with the following
declaration:

typedef struct node

•It is a self referential structure. One member of this structure is a pointer

07/04/25 8
 Node
• #include<stdio.h>
• #include<conio.h>
• typedef struct node
• {
• int data;
• struct node *next;
• }node;
 Prototype
• node *create(int);
• node *addbeg(node*);
• node *insertend(node*);
• node *insertmid(node*);
• node *del(node*);
• void Print(node*);
 Main
• void main()
• {
• node *start; int n, x;
• clrscr();
• start = NULL;
• printf("Enter the no. of node\n");
• scanf("%d", &n);
• start = create(n);
• Print(start);
• printf("Enter your Choice\n");
• scanf("%d", &x);
• while(x<6)
• { switch(x)
• {
• case 1:
• start=addbeg(start); break;
• case 2:
• start=insertmid(start); break;
• case 3:
• start=insertend(start); break;
• case 4:
• Print(start); break;
• case 5:
• start=del(start); break;
• defalut:
• printf("enter 6 for quit"); break;
• }
• printf("Enter for rechoice\n");
scanf("%d",&x);
• }
• getch();
• }
• node *create(int n)
• {
• node *head, *p, *temp;
• int i;
• head=(node*)malloc(sizeof(node));
• head->next=NULL;
• printf("Enter the value");
• scanf("%d", &head->data);
• p=head;
• for(i=1; i<n; i++)
• {
• temp=(node*)malloc(sizeof(node));
• p->next=temp;
• p=p->next;
• printf("enter the first onwords values\n");
• scanf("%d", &p->data);
• p->next=NULL;
• }
• return(head);
• }
 Print
• void Print(node *p)
• {
• if(p==NULL)
• printf("List is empty\n");
• while(p!=NULL)
• {
• printf("->%d", p->data);
• printf("\n");
• p=p->next;
• }
• }
 Insertion into a linked list
• Insertion in a linked list may be possible in
three ways:
– Insertion at beginning
– Insertion in between
– Insertion at last

07/04/25 15
 Insertion at beg
• node *addbeg(node *p)
• {
• node *tmp, *head; int item;
• head=p;
• tmp=(node*)malloc(sizeof(node));
• printf("Enter the FIRST value\n");
• scanf("%d",&item);
• tmp->data=item;
• tmp->next=head;
• head=tmp;
• return(head);
• }
 Insertion at end
• node *insertend(node *head)
• {
• node *p, *q; int item;
• p=(node*)malloc(sizeof(node));
• printf("Enter the LAST value\n"); scanf("%d",&item);
• p->data=item;
• p->next=NULL;
• if(head==NULL)
• return(p);
• q=head;
• while(q->next!=NULL)
• {
• q=q->next;
• }
• q->next=p; return(head);
• }
 Insertion at mid
• node *insertmid(node *head)
• {
• node *p, *q; int item, i, loc; p=(node*)malloc(sizeof(node));
• printf("Enter the LOCATION of item\n"); scanf("%d", &loc);
• if(loc==0)
• {
• printf("Loc is larger than 1\n");
• return(head);
• }
• printf("Enter the item value\n"); scanf("%d", &item);
• p->data=item; p->next=NULL; q=head;
• for(i=0; i<loc-1; i++)
• {
• q=q->next;
• if(q==NULL)
• {
• printf("there are less then element\n"); return(head);
• }
• }
• p->next=q->next; q->next=p;
• return(head);
• }
 Deletion from a linked list
• First we traverse the linked list and
compare with each element. After finding
the there may be three cases for deletion:
– Deletion at the beginning
– Deletion in between
– Deletion at last

07/04/25 19
 Deletion
• node *del(node *head)
• {
• node *p, *q;int x;
• printf("Enter the deleted element\n"); scanf("%d", &x);
• if(head->data==x)
• {
• p=head; head=head->next; free(p);
• return(head);
• }
• q=head;
• while(q->next->data!=x)//middie and last
• { q=q->next; }
• if(q->next->data==x)
• {
• p=q->next; q->next=p->next;
• printf("Deleted Element=%d\n",p->data); free(p);
• return(head);
• }
• q=q->next;
• if(q==NULL)
• { printf("Element%d not found\n",x); }
• return(head);
• }
• Thanks