DATA STRUCTURE AND ALGORITHMS LABORATORY ITU324

Practical No-2 Date:-

AIM: - After getting her job in multinational company, Shobhana has become a celebrity at
her college, and her facebook profile is full of friend requests. Being the nice girl she is,
Shobhana has accepted all the requests. Now Shobhana decides to remove some friends from her
friend list, since she knows the popularity of each of the friend she has, write and implement an
algorithm to delete a friend.
Theory:-
A linked list is a linear data structure, in which the elements are not stored at contiguous memory
locations. The elements in a linked list are linked using pointers as shown in the image

Basic Operations on Linked List

● Traversal: To traverse all the nodes one after another.

● Insertion: To add a node at the given position.

● Deletion: To delete a node.

● Searching: To search an element(s) by value.

● Updating: To update a node.

● Sorting: To arrange nodes in a linked list in a specific order.

● Merging: To merge two linked lists into one.

Arrays can be used to store linear data of similar types, but arrays have the following
limitations.
1) The size of the arrays is fixed: So we must know the upper limit on the number of elements in
advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the
usage.

Department of Information Technology, GCoE, Amravati Winter 2022

DATA STRUCTURE AND ALGORITHMS LABORATORY ITU324

2) Inserting a new element in an array of elements is expensive because the room has to be
created for the new elements and to create room existing elements have to be shifted.
For example, in a system, if we maintain a sorted list of IDs in an array id[].
id[] = [1000, 1010, 1050, 2000, 2040].
And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all
the elements after 1000 (excluding 1000).
3) Deletion is also expensive with arrays until unless some special techniques are used. For
example, to delete 1010 in id[], everything after 1010 has to be moved.
Advantages over arrays
1) Dynamic size
2) Ease of insertion/deletion
Drawbacks:
1) Random access is not allowed. We have to access elements sequentially starting from the first
node. So we cannot do binary search with linked lists efficiently with its default implementation.
Read about it here.
2) Extra memory space for a pointer is required with each element of the list.
3) Not cache friendly. Since array elements are contiguous locations, there is locality of
reference which is not there in case of linked lists.
Representation:
A linked list is represented by a pointer to the first node of the linked list. The first node is called
the head. If the linked list is empty, then the value of the head is NULL.
Each node in a list consists of at least two parts:
1) data
2) Pointer (Or Reference) to the next node

struct Node {
int data;
struct Node* next;
};

// Program to create a simple linked list with 2 nodes

int main()
{
struct Node* head = NULL;
struct Node* second = NULL;

Department of Information Technology, GCoE, Amravati Winter 2022

DATA STRUCTURE AND ALGORITHMS LABORATORY ITU324
head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));

/* Two blocks have been allocated dynamically. We have pointers

to these two blocks as head, second

head second
| |
| |
+---+-----+ +----+----+
| # | # | | # | # |
+---+-----+ +----+----+

# represents any random value. Data is random because we haven’t assigned

anything yet */

head->data = 5; // assign data in first node

head->next = second; // Link first node with the second node

/* data has been assigned to the data part of the first block (block pointed
by the head). And next pointer of first block points to second.So they both
are linked. */

head second
| |
| |
+---+---+ +----+----+
| 5 | o----->| # | # |
+---+---+ +----+----+

// assign data to second node

second->data = 2;
second->next = NULL;
return 0;
}

Operations on Singly Linked List

TRAVERSING A LINKED LIST
Algorithm:-Let LIST be a linked list in a memory. This algorithm traverses LIST, applying
an operation PROCESS to each element of LIST. The variable PTR points to the currently
being processed.
Step 1 : [Initializes pointer PTR]
Set PTR :=START.
Step 2 : Repeat Step 3 and 4 while PTR ≠ NULL.
Step 3 : Apply PROCESS to INFO[PTR].

Department of Information Technology, GCoE, Amravati Winter 2022

DATA STRUCTURE AND ALGORITHMS LABORATORY ITU324
Step 4 : Set PTR := LINK[PTR].
[PTR now points to the next node.]
[End of Step 2 loop.]
Step 5 : Exit.
SEARCHING A LINKED LIST--LIST Is Unsorted
Algorithm-SEARCH (INFO, LINK, START, ITEM, LOC)
LIST is a linked list in memory. This algorithm finds the location LOC of the node where
ITEM first appears in LIST, or sets LOC = NULL.
Step 1 : Set PTR := START.
Step 2 : Repeat Step 3 while PTR ≠ NULL:
Step 3 : If ITEM = INFO[PTR], then:
Set LOC := PTR, and Exit.
Else:
Set PTR := LINK[PTR].
[PTR now points to the next node.]
[End of If structure.]
[End of Step 2 loop.]
Step 4 : [Search is unsuccessful.]
Set LOC := NULL.
Step 5 : Exit.

INSERTION ALGORITHM
A node can be added in three ways
1) At the front of the linked list
2) After a given node.
3) At the end of the linked list.

Department of Information Technology, GCoE, Amravati Winter 2022

DATA STRUCTURE AND ALGORITHMS LABORATORY ITU324

Algorithm :-INSFIRST(INFO, LINK, START, AVAIL, ITEM)

This algorithm inserts ITEM as the first node in the list.
Step 1 : [OVERFLOW?]
If AVAIL = NULL, then :
Write : OVERFLOW, and Exit.
Step 2 : [Remove first node from AVAIL list.]
Set NEW := AVAIL and
AVAIL := LINK[AVAIL].
Step 3 :Set INFO[NEW] := ITEM.
[Copies new data into new node].
Step 4 : Set LINK[NEW] := START.
[New node now points to original first node.]
Step 5 : Set START := NEW.
[Changes START so it points to new node.]
Step 6 : Exit.

Algorithm:-INSLOC(INFO, LINK, START, AVAIL, LOC, ITEM)

This algorithm inserts ITEM so that ITEM follows the node with location LOC or inserts
ITEM as the first node when LOC = NULL.
Step 1 : [OVERFLOW?]
If AVAIL = NULL, then :
Write : OVERFLOW, and Exit.

Department of Information Technology, GCoE, Amravati Winter 2022

DATA STRUCTURE AND ALGORITHMS LABORATORY ITU324
Step 2 : [Remove first node from AVAIL list.]
Set NEW := AVAIL and AVAIL :=
LINK[AVAIL].
Step 3 : Set INFO[NEW] := ITEM.
[Copies new data into new node].
Step 4 : If LOC = NULL, then :
[Insert as first node.]
Set LINK[NEW] := START and
START := NEW.
Else : [Insert after node with location LOC.]
Set LINK[NEW] := LINK[LOC]
and LINK[LOC] := NEW.
[End of If structure.]
Step 5 : Exit.

Algorithm:- INSERT(INFO,LINK,START,AVAIL,ITEM)
This algorithm inserts ITEM into a sorted linked list.
1. [Use Procedure to find the location of the node preceding ITEM.]
Call FINDA(INFO,LINK,START,ITEM,LOC)
2. [Use Algorithm to insert ITEM after the node with location LOC].
Call INSLOC(INFO,LINK,START,AVAIL,LOC,ITEM).
3. Exit.
Procedure:-FINDA(INFO,LINK,START,ITEM,LOC)

Department of Information Technology, GCoE, Amravati Winter 2022

DATA STRUCTURE AND ALGORITHMS LABORATORY ITU324
This procedure finds the location LOC of the last node in a sorted list such that
INFO[LOC ]<ITEM or sets LOC=NULL.
1.[List empty?] If START=NULL, then:
Set LOC:=NULL, and return.
2.[Special case ?] If ITEM< INFO[START], then: Set
LOC:=NULL, and return.
3.Set SAVE:=START and PTR:= LINK[START].
[Initializes pointers].
4.Repeat steps 5 and 6 while PTR!=NULL.
5. If ITEM< INFO[PTR]. then:
Set LOC:= SAVE, and return.
[End of if structure]
6.Set SAVE:=PTR and PTR:=LINK[PTR]
[End of Step 4 loop]
7.Set LOC:=SAVE.
8.Return.

Algorithm:- DEL(INFO,LINK,START,AVAIL,LOC,LOCP)
Let LIST be a linked list in memory. Suppose we are given the location LOC of node N in
LIST. And ,suppose we are given the location LOCP of the node preceding N or, when N is
the first node ,we are given LOCP=NULL. The following algorithm deletes N from the list.
1.If LOCP=NULL, then:
Set START:=LINK [START]. [ Deletes first node].
else:
Department of Information Technology, GCoE, Amravati Winter 2022
DATA STRUCTURE AND ALGORITHMS LABORATORY ITU324
Set LINK[LOCP]:= LINK[LOC]. [ Deletes N node.]
[End of if structure]
2.[Return deleted node to the AVAIL list.]
set LINK[LOC]:=AVAIL and AVAIL:=LOC.
3.Exit.

Student Source code:-

#include <stdio.h>
#include <stdlib.h>

struct node
{
int data;
struct node *next;
};

struct node *del (struct node *head)

{
struct node *ptr = head;
head = head->next;
free (ptr);
return head;
}

void sorting (struct node *head)

{
int temp;
struct node *ptr, *cpt;

ptr = head;
while (ptr != NULL)
{
cpt = ptr->next;
while (cpt != NULL)
Department of Information Technology, GCoE, Amravati Winter 2022
DATA STRUCTURE AND ALGORITHMS LABORATORY ITU324
{
if (ptr->data > cpt->data)
{
temp = ptr->data;
ptr->data = cpt->data;
cpt->data = temp;
}
cpt = cpt->next;
}
ptr = ptr->next;
}
}

struct node *insert (struct node *head, int data)

{
struct node *cpp = (struct node *) malloc (sizeof (struct node));
cpp->next = head;
cpp->data = data;
return cpp;
}

int main ()
{
int i, n, item, sum = 0;
int r;
struct node *p, *q, *head = NULL;

printf ("Enter the number of friends: ");

scanf ("%d", &n);

for (i = 0; i < n; i++)

{
printf ("Enter the popularity of friend %d: ", i + 1);
scanf ("%d", &item);

q = (struct node *) malloc (sizeof (struct node));

q->data = item;
q->next = NULL;

if (head == NULL)
{
head = q;
p = head;
}
else
{
p->next = q;
Department of Information Technology, GCoE, Amravati Winter 2022
DATA STRUCTURE AND ALGORITHMS LABORATORY ITU324
p = p->next; // ye point kar raha hay next me jo address haay uskki help se next
node acces kr raha haay
}
sum += item;
}

sorting (head);

printf ("\nThe popularity of your friends after sorting is: ");

p = head;
while (p != NULL)
{
printf ("%d ", p->data);
p = p->next;
}

int mean = (int) sum / n;

printf ("\nThe mean of the popularities: %d\n", mean);

p = head;
while (p != NULL)
{
if (p->data < mean)
{
head = del (head);
p = head;
}
else
{
p = p->next;
}
}
int a, f;
printf ("Enter 1 if you want to insert new friend:");
scanf ("%d", &a);
if (a == 1)
{
printf ("Enter the popularity of new friend:");
scanf ("%d", &f);

head=insert (head,f);

sorting (head);
}

Department of Information Technology, GCoE, Amravati Winter 2022

DATA STRUCTURE AND ALGORITHMS LABORATORY ITU324
printf ("\nUpdated friend list:");
p = head;
while (p != NULL)
{
printf ("%d ", p->data);
p = p->next;
}

return 0;
}

Output-
Enter the number of friends: 5
Enter the popularity of friend 1: 5
Enter the popularity of friend 2: 4
Enter the popularity of friend 3: 3
Enter the popularity of friend 4: 2
Enter the popularity of friend 5: 1

The popularity of your friends after sorting is: 1 2 3 4 5

The mean of the popularities: 3
Enter 1 if you want to insert new friend:1

Enter the popularity of new friend:6

Updated friend list:3 4 5 6

Viva Question:-
1. What is Linked List?
2. What is Singly Linked List?
3. How would you sort a linked list?
4. Whether Linked List is linear or Non-linear data structure?
Department of Information Technology, GCoE, Amravati Winter 2022
DATA STRUCTURE AND ALGORITHMS LABORATORY ITU324
5. What does the following function do for a given Linked List with first node as head?

void fun1(struct node* head)

if(head == NULL)

return;

fun1(head->next);

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

A Prints all nodes of linked lists

B Prints all nodes of linked list in reverse order

C Prints alternate nodes of Linked List

D Prints alternate nodes in reverse order

6. Which of the following points is/are true about Linked List data structure when it is
compared with array

A Arrays have better cache locality that can make them better in terms of performance.

B It is easy to insert and delete elements in Linked List

C Random access is not allowed in a typical implementation of Linked Lists

D The size of array has to be pre-decided, linked lists can change their size any time.

E All of the above

7. Which of the following sorting algorithms can be used to sort a random linked list with
minimum time complexity?

Insertion Sort

Quick Sort

Heap Sort

Merge Sort

Department of Information Technology, GCoE, Amravati Winter 2022

DATA STRUCTURE AND ALGORITHMS LABORATORY ITU324
8. What is the output of following function for start pointing to first node of following linked
list? 1->2->3->4->5->6

void fun(struct node* start)

{ if(start == NULL)

return;

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

if(start->next != NULL )

fun(start->next->next);

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

A 146641 B 135135 C 1235 D 135531

9. In the worst case, the number of comparisons needed to search a singly linked list of length n
for a given element is

A log 2 n

B n/2

C log 2 n – 1

D n

Department of Information Technology, GCoE, Amravati Winter 2022