Data Structures Using C

UNIT 2
GEETHA N
ASSISTANT PROFESSOR
B.M.S. COLLEGE OF ENGINEERING
Linked List
Linked List is a very commonly used linear data structure which consists of group of
nodes in a sequence.
• Each node holds its own data and the address of the next node hence forming a
chain like structure.
• Linked Lists are used to create trees and graphs.
Applications of Linked Lists
• Linked lists are used to implement stacks, queues, graphs, etc.
• Linked lists let you insert elements at the beginning and end of the list.
• In Linked Lists we don't need to know the size in advance.
Browser History Management : Each visited web page is stored as a node.
Operating System Task Scheduling A list of processes (or tasks) waiting to be executed can be stored in a linked
list, allowing efficient addition and removal of processes from the queue.
File System Directory Structure Directories contain lists of files, which can be managed dynamically using linked
lists, especially when files are constantly added, deleted, or modified.
Multimedia Applications Linked lists allow dynamic adjustment of the buffer size, enabling smoother playback as
data is streamed and added in real-time.
Peer-to-Peer Networks In peer-to-peer (P2P) networks, linked lists can be used to keep track of the network
topology (how nodes are connected).
Types of Linked Lists

• Singly Linked List

• Doubly Linked List

• Circular Linked List
Singly Linked List
Singly linked lists contain nodes which have a data part as well as an address part i.e. next,
which points to the next node in the sequence of nodes.

• The operations we can perform on singly linked lists are insertion, deletion and traversal.
Doubly Linked List

In a doubly linked list, each node contains a data part and two addresses, one for the
previous node and one for the next node.
Circular Linked List
In circular linked list the last node of the list holds the address of the first node hence
forming a circular chain.
Disadvantages of Linked Lists
• The memory is wasted as pointers require extra memory for storage.
• No element can be accessed randomly; it has to access each node sequentially.
Difference between Array and Linkedlist
[Link] ArrayList LinkedList

1 This is known as static memory allocation. This is known as dynamic memory allocation.

2 Less memory is used. More memory is used.

3 It is used to store only similar types of data. It is used to store any types of data.

4 Inefficient memory utilization. Good memory utilization.

5 It can be one, two or multi-dimensional. It can either be single, double or circular LinkedList.

6 Data access and storage is very efficient as it stores the Data access and storage is slow in LinkedList.
elements according to the indexes.

7 Deletion operation is not very efficient. Deletion operation is very efficient.

Dynamic Memory Allocation Functions
Example
Syntax for malloc(): ptr=(datatype *)malloc(specified-size);
• Example 1:
int ptr;
ptr=(int *)malloc(10*sizeof(int));

• Example 2:
struct node *str;
str=(struct node *)malloc(sizeof(struct node));
Singly Linked List
What is a Node?
• A Node in a linked list holds the data value and the pointer which points to the location
of the next node in the linked list.
Node Implementation
// A linked list node
struct Node
{
int data;
struct Node *next;
};

struct Books {
char title[50];
char author[50];
char subject[100];
int book_id;
struct Books *add;
};
Creating a Node in C
// A linked list node
struct Node
{
NULL
int data;
struct Node *next;
head
};
int main( )
{
struct Node *head = NULL; 45 NULL
head = (struct Node *) malloc (sizeof (struct Node ) );

head -> data = 45;

head -> next = NULL;
1000
printf(“%d”, head->data); head
return 0;
}
Inserting a node
• 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.
 Add a node at the front
/* Given a reference (pointer to pointer) to the head of a list
and an int, inserts a new node on the front of the list. */
void push(struct Node** head_ref, int new_data)
{
/* 1. allocate node */
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
/* 2. put in the data */
new_node->data = new_data;
/* 3. Make next of new node as head */
new_node->next = (*head_ref);
/* 4. move the head to point to the new node */
(*head_ref) = new_node;
}
Add a node at the end
Add a node at specified position
Display the content of Linked List
Singly Linked List: Deleting a node
A node can be deleted in three ways
1) At the front of the linked list
2) After a given node/specified position
3) At the end of the linked list.
Delete a node at the front
void Pop()
{
struct node *ptr;
if(head == NULL)
{
printf("\nList is empty");
}
else
{
ptr = head;
head = ptr->next;
free(ptr);
printf("\n Node deleted from the begining ...");
}
}
 Delete a node at the end
void end_delete() else
{ {
struct node *ptr,*ptr1; ptr = head;
if(head == NULL) while(ptr->next != NULL)
{ {
printf("\nlist is empty"); ptr1 = ptr;
} ptr = ptr ->next;
else if(head -> next == NULL) }
{ ptr1->next = NULL;
free(ptr);
free(head);
printf("\n Deleted Node from the last ...");
head = NULL; }
printf("\nOnly node of the list deleted ..."); }
}
Delete a node at specified position
void delete_specified()
{
struct node *ptr, *ptr1;
int loc,i;
scanf("%d",&loc);
ptr=head;
if(loc == 1)
{
head = ptr-> next;
free(ptr);
}
for(i=1;i<loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;
if(ptr == NULL)
ptr1 ->next = ptr ->next;
{
free(ptr);
printf("\nThere are less than %d elements
printf("\nDeleted %d node ",loc);
in the list..\n",loc);
}
return;
}
}
Singly Linked List Operations
Search
Count number of nodes
Concatenation
Sorting
Merging
Reversing
Search
void search( )
{
struct node *ptr;
int item, i=0;
ptr = head;
if(ptr == NULL)
{
printf(“ \n Empty list”);
}
else
{
printf(“ \n enter the element you want to search \n”);
scanf( “%d”, item);
while(ptr!=NULL)
{
if(ptr->data == item )
{
printf(“ item found at location %d”, i+1);
}
i++;
ptr = ptr->next;

else
printf(“\n item not found”);
}
}
}
Count number of nodes
void Count_nodes( )
{
struct node* temp = head; /* temp pointer points to head */
int count=0; /* Initialize count variable */
/* Traverse the linked list and maintain the count */
while(temp != NULL)
{
temp = temp->next;
count++;
}
/* Print the total count. */
printf("\n Total no. of nodes is %d",count);
}
Concatenation
void concat(struct node *head1, struct node *head2)
{
struct node *temp1, *temp2;
temp1 = head1;
temp2 = head2;
while(temp1->next ! = NULL)
{
temp1 = temp1->next;
}
temp1 -> next = temp2;
printf(“\n the concatenated list is \n”);
temp1 = head1;
while(temp1 != NULL)
{
printf(“%d”, temp1->data);
temp1 = temp1->next;
}
}
Sorting
void sort( )
{
struct node *i, *j;
int temp;
for( i=head; i->next != NULL; i = i->next)
{
for( j = i->next; j != NULL; j=j->next)
{
if( i->data > j->data )
{
temp = i->data;
i->data = j->data;
j->data = temp;
}
}
}
}
Merging
Input: a: 5->10->15

b: 2->3->20

Output: 2->3->5->10->15->20

Input: a: 1->1

b: 2->4

Output: 1->1->2->4
Merging if(L1->data < L2->data)
{
struct node * merge(struct node *L1, struct node j->next = L1;
*L2) L1 = L1->next;
{ j = j->next;
struct node *i, *j; }
if(L1 == NULL) else
return L2; {
if(L2 == NULL)
j->next = L2;
return L1;
L2 = L2->next;
if(L1->data < L2->data)
{ j = j->next;
i = j = L1; }
L1 -> L1->next; }
} if(L1 == NULL)
else j->next = L2;
{ else
i = j = L2; j->next = L1;
L2 -> L2->next;
return i;
}
while(L1 != NULL && L2 != NULL) }
{
Reversing a Linked List
Input —- 5 -> 10 -> 15 -> 2 -> 3

Output: 3 -> 2 -> 15 -> 10 -> 5

Input —- 45 -> 1 -> 5 -> 27

Output: 27 -> 5 -> 1 -> 45

Reversing a LinkedList

void reverse( )
{
struct node *prev, *curr, *nextn;
prev = NULL;
curr = nextn = head;
while(nextn! = NULL)
{
nextn = nextn->next;
curr->next = prev;
prev = curr;
curr = nextn;
}
head = prev;
}