Unit - III Linked List

3.1 Difference between Static and Dynamic Memory Allocation.

Memory Allocation: Memory allocation is a process by which computer programs and
services are assigned with physical or virtual memory space. The memory allocation is
done either before or at the time of program execution. There are two types of memory
allocations:

1. Compile-time or Static Memory Allocation

Static Memory is allocated for declared variables by the compiler. The
address can be found using the address of operator and can be assigned to a pointer. The
memory is allocated during compile time.
2. Run-time or Dynamic Memory Allocation
Memory allocation done at the time of execution (run time) is known
as dynamic memory allocation. Functions calloc() and malloc() support allocating dynamic
memory. In the Dynamic allocation of memory space is allocated by using these functions
when the value is returned by functions and assigned to pointer variables.

Sr Static Memory Allocation Dynamic Memory Allocation

No
1 In the static memory allocation, variables In the Dynamic memory allocation,
get allocated permanently, till the program variables get allocated only if your
executes or function call finishes. program unit gets active.

2 Static Memory Allocation is done before Dynamic Memory Allocation is done

program execution during program execution.
3 In this memory is allocated at compile time In this memory is allocated at run time.

4 In static memory allocation, once the In dynamic memory allocation, when

memory is allocated, the memory size memory is allocated the memory size can
cannot change. be changed.
5 In this allocated memory remains from start In this allocated memory can be released
to end of the program. at any time during the program.

6 It uses stack for managing the static It uses heap for managing the dynamic
allocation of memory allocation of memory
7 In Static Memory Allocation, there is no In Dynamic Memory Allocation, there is
memory re-usability memory re-usability and memory can be
freed when not required
8 In this memory allocation scheme, execution In this memory allocation scheme,
is faster than dynamic memory allocation. execution is slower than static memory
allocation.
9 It is less efficient It is more efficient
10 Example: array. Example: linked list
3.2 Introduction to Linked List, Terminologies: Node, Address, Pointer, Information
field / Data field, Next pointer, Null Pointer, Empty List.

o Linked List can be defined as collection of objects called nodes that are randomly
stored in the memory.
o A node contains two fields i.e. data stored at that particular address and the pointer
which contains the address of the next node in the memory.
o The last node of the list contains pointer to the null.

Uses of Linked List

o The list is not required to be contiguously present in the memory. The node can reside
anywhere in the memory and linked together to make a list. This achieves optimized
utilization of space.
o List size is limited to the memory size and doesn't need to be declared in advance.
o Empty node cannot be present in the linked list.
o We can store values of primitive types or objects in the singly linked list.

Why use linked list over array?

Till now, we were using array data structure to organize the group of elements that are to be
stored individually in the memory. However, Array has several advantages and disadvantages
which must be known in order to decide the data structure which will be used throughout the
program.

Array contains following limitations:

1. The size of array must be known in advance before using it in the program.
2. Increasing size of the array is a time taking process. It is almost impossible to expand
the size of the array at run time.
3. All the elements in the array need to be contiguously stored in the memory.
4. Inserting or Deleting any element in the array needs shifting of all its predecessors.
Linked list is the data structure which can overcome all the limitations of an array.
Using linked list is useful because,

1. It allocates the memory dynamically. All the nodes of linked list are non-contiguously
stored in the memory and linked together with the help of pointers.
2. Sizing is no longer a problem since we do not need to define its size at the time of
declaration. List grows as per the program's demand and limited to the available
memory space.

Terminologies
Node: Each data element in a linked list is represented as a node. Node contains two parts
one is info (data) and other is next pointer (address). Info part stores data and next pointer
stores address of next node.

Info Next
Poniter

Next pointer: It is a pointer that holds address of next node in the list i.e. next pointer points
to next node in the list

Start 10 Next 20 NULL

Poniter

Null pointer: It is a pointer that does not hold any memory address i.e. it is pointing to
nothing. It is used to specify end of the list. The last element of list contains NULL pointer to
specify end of list.

10 Next 20 NULL
Start
Poniter

Empty list: Each linked list has a header node. When header node contains NULL value,
then that list is said to be empty list.

NULL
3.3 Type of Lists: Linear List, Circular List, Representation of Doubly Linked List.

Types of Linked List

Following are the various types of linked list.

Singly Linked Lists

Singly linked lists contain two "buckets" in one node; one bucket holds the data and the other
bucket holds the address of the next node of the list. Traversals can be done in one direction
only as there is only a single link between two nodes of the same list.

Doubly Linked Lists

Doubly Linked Lists contain three "buckets" in one node; one bucket holds the data and the
other buckets hold the addresses of the previous and next nodes in the list. The list is
traversed twice as the nodes in the list are connected to each other from both sides.

Circular Linked Lists

Circular linked lists can exist in both singly linked list and doubly linked
list.

Since the last node and the first node of the circular linked list are connected, the traversal in
this linked list will go on forever until it is broken.
 3.4 Operations on a Singly Linked List:
 Creating a Linked List

Node Creation
struct node
{
int data;
struct node *next;
};
struct node *head, *newnode;
newnode = (struct node *)malloc(sizeof(struct node ));

Program for Creating Linked List

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
void createlist(int n);
void display();
struct node
{
int data;
struct node * next;
};
struct node *head =0;
void main()
{
int n;
printf(“Enter the size of Linked List”);
sacnf(“%d”,&n);
createlist(n);
display();
getch();
}

void createlist( int n)

{
struct node * temp,*newnode;
 for ( int i=0; i<n ;i++)
newnode= (struct node *)malloc(sizeof(struct node));
printf(“Enter Data”);
scanf(“%d”,&newnode->data)
newnode->next=0;
if (head==0)
{
head=temp=newnode;
}
else
{
temp->next=newnode;
temp=newnode;
}
}

 Inserting Operation in a Linked List

Adding a new node in linked list is a more than one step activity. We shall learn this with
diagrams here. First, create a node using the same structure and find the location where it has to be
inserted.

Imagine that we are inserting a node B (NewNode), between A (LeftNode) and C

(RightNode). Then point B.next to C −

NewNode.next -> RightNode;

It should look like this −

Now, the next node at the left should point to the new node.

LeftNode.next -> NewNode;

This will put the new node in the middle of the two. The new list should look like this −

Insertion in linked list can be done in three different ways. They are explained as follows −

 Insertion at Beginning

In this operation, we are adding an element at the beginning of the list.

Algorithm
1. START
2. Create the node pointer *newnode
struct node * newnode ;
3. Allocate address to newnode using malloc
newnode =(struct node *) malloc(sizeof(struct node));
4. Check whether head is null, if null then Display “Underflow” else
newnode-> next=head ;
5. head=newnode
6. STOP

Program for Insertion at begining

void InsertatBeg( )
{
struct node *newnode;
newnode=(struct node *)malloc(sizeof(struct node));
printf(“Enter Your Data”);
scanf(“%d”,&newnode-> data);
newnode->next=0;
if (head== null)
{
head=newnode;
}
else
{
newnode->next=head;
head=newnode;
}
}

 Insertion at Ending

In this operation, we are adding an element at the ending of the list.

Algorithm
1. START
2. Create two node pointer *newnode ,*temp
Struct node * newnode,*temp;
3. temp=head;
4. Allocate address to newnode using malloc
newnode =(struct node *) malloc(sizeof(struct node));
5. Check whether head is null, if null then Display “Underflow” else
newnode-> next=temp
5. while(temp->next!= null)
temp=temp->next;
temp->next = newnode;
6. STOP

Program for Insertion at ending

void Insertatend( )
{
struct node *newnode,*temp;
newnode=(struct node *)malloc(sizeof(struct node));
printf(“Enter Your Data”);
scanf(“%d”,&newnode-> data);
newnode->next=0;
if (head== null)
{
head=newnode;
}
else
{
temp=head;
while(temp->next!= null)
{
temp=temp->next;
}

temp->next = newnode;
}
  Insertion at a Given Position

In this operation, we are adding an element at any position within the list.

Algorithm
1. START
2. Create two node pointer *newnode,*temp
struct node * newnode,* temp;
3. Initialize three variable len,loc and i
4. Calculate the length of Linked List
len = length( );
5. Input Location where to insert the node
6. Compare Location is greater than length. If Yes Print “Invalid Location “ and Retrun
7. If No then assign start address to pointer variable
temp=head;
8. Reach at specified location using
While (i<loc)
{
temp=temp-> next;
i++;
}
9. Allocate address to newnode using malloc
newnode = (struct node*) malloc(sizeof(struct node));
10. Accept data and address for new node
11. After reaching at specified location set first right link address and then left link address
newnode-> next=temp-> next
temp->next = newnode

Program for Insertion at given position

void Insertatgivenposition()
{
struct node * newnode,* temp;
int loc,len,i=1;
printf(“Enter Location where you want to insert the node”);
sacnf(“%d”,&loc);
len=length();
if (loc > len)
{
printf(“Invalid Location”);
printf(“Currently Linkeed List having %d nodes”,len);
}
else
{
temp=head;
while (i< loc)
{
 temp=temp-> next;
i++;
}
newnode=(struct node *)malloc(sizeof(struct node));
printf(“Enter Your Data”);
scanf(“%d”,&newnode-> data);
newnode->next=0;
newnode-> next=temp->next;
temp->next=newnode;

}
}

 Deleting Operation in Linked List,

Deletion is also a more than one step process. We shall learn with pictorial
representation. First, locate the target node to be removed, by using searching algorithms.

The left (previous) node of the target node now should point to the next node of the target
node −

LeftNode.next -> TargetNode.next;

This will remove the link that was pointing to the target node. Now, using the following code,
we will remove what the target node is pointing at.

TargetNode.next -> NULL;

We need to use the deleted node. We can keep that in memory otherwise we can simply
deallocate memory and wipe off the target node completely.

Similar steps should be taken if the node is being inserted at the beginning of the list. While
inserting it at the end, the second last node of the list should point to the new node and the
new node will point to NULL.

Deletion in linked lists is also performed in three different ways. They are as follows −

 Deletion at Beginning

In this deletion operation of the linked, we are deleting an element from the beginning of the
list. For this, we point the head to the second node.

Algorithm
1. START
2. Create temporary node temp
3. Assign address of first node to temp pointer
4. Store address of second node in header pointer
5. Free temp
6. STOP
Program for Deletion at Begining

void deleteatbeg()
{
struct node * temp;
if (head == 0)
{
printf(“List is Empty can not Delete”);
}
else
{
 temp=head;
head=temp-> next;
temp-> next =0;
free(temp);
}
}

 Deletion at Ending
In this deletion operation of the linked, we are deleting an element from the ending of the list.

Algorithm
1. START
2. Create temporary node temp ,q
3. Assign address of first node to temp pointer
4. Traverse the node upto second last node
5. Mark last node address as q
6. Store NULL value in address field of second last node
7. Free q
8. STOP
Program for Deletion at Ending

void DeleteatEnd()
{
struct node * temp,*q;
int i=1,loc;
printf(“enter the Location to delete”);
scanf(“%d”, &loc);
if (loc > length())
{
printf(“ Invalid Function”);
}
else
{
temp=head;
while ( i < loc-1)
{
temp=temp->next;
i++;
}
q=temp-> next;
temp-> next=null;
q-> next=null;
free(q);
}
}
  Deletion at a Given Position

In this deletion operation of the linked, we are deleting an element at any position of the list.

Algorithm
1. START
2. Create temporary node temp ,q
3. Assign address of first node to temp pointer
4. Traverse the node upto previous node to be deleted
5. Mark last node address as q
6. Store address from node q in address field of temp node
7. Free q
8. STOP

Program for Deletion at Given Position

void DeleteatGivenPositio()
{
struct node * temp,*q;
int i=1,loc;
printf(“enter the Location to delete”);
scanf(“%d”, &loc);
if (loc > length())
{
printf(“ Invalid Function”);
}
else
{
temp=head;
while (i < loc-1)
{
temp=temp->next;
i++;
}
q=temp-> next;
temp-> next=q->next;
q-> next=null;
free(q);
}
}
  Linked List - Traversal Operation

The traversal operation walks through all the elements of the list in an order and displays the
elements in that order.

Algorithm
1. START
2. While the list is not empty and did not reach the end of the list, print the data in each
node
3. STOP
Program for Traversing in Linked List
void Traverse()
{
struct node* temp;
temp=head;
while(temp != NULL )
{
temp= temp-> next;
}
}

 Linked List - Search Operation

Searching for an element in the list using a key element. This operation is done in the same
way as array search; comparing every element in the list with the key element given.

Algorithm
1. START
2. If the list is not empty, iteratively check if the list contains the key
3. If the key element is not present in the list, unsuccessful search
4. STOP
Program for Searching in Linked List
Void search(int x)
{
struct node *temp;
temp=head;
while (temp !=NULL)
{
if ( temp-> data == x)
{
return 1;
temp=temp-> next;
}
}
return 0;
}
  Linked List - Display Operation
The display operation walks through all the elements of the list in an order and
displays the elements in that order.
Algorithm
1. START
2. While the list is not empty and did not reach the end of the list, print the data in each
node
3. STOP
Program for Display of Linked List
void display ()
{
struct node* temp;
temp=head;
if ( temp = = NULL)
{
printf(“List is Empty”);
}
while(temp != NULL )
{
printf(“%d”,temp-> data);
temp= temp-> next;
}
}
 Linked List – Counting Operation
Algorithm
1. START
2. Initialize count variable to 0
3. Initilize node pointer temp=head
4. If the list is not empty, iteratively count the number of node in the list .
5. STOP
Program for Searching in Linked List
int length( )
{
int count=0;
struct node *temp;
temp=head;
while (temp !=NULL)
{
count++;
temp=temp-> next;

}
return count;
}
3.5 Applications of Linked List.
Applications of linked list in computer science:
1. Implementation of stacks and queues
2. Implementation of graphs: Adjacency list representation of graphs is the most popular
which uses a linked list to store adjacent vertices.
3. Dynamic memory allocation: We use a linked list of free blocks.
4. Maintaining a directory of names
5. Performing arithmetic operations on long integers
6. Manipulation of polynomials by storing constants in the node of the linked list
7. Representing sparse matrices
Applications of linked list in the real world:
1. Image viewer – Previous and next images are linked and can be accessed by the next
and previous buttons.
2. Previous and next page in a web browser – We can access the previous and next URL
searched in a web browser by pressing the back and next buttons since they are linked
as a linked list.
3. Music Player – Songs in the music player are linked to the previous and next songs. So
you can play songs either from starting or ending of the list.
4. GPS navigation systems- Linked lists can be used to store and manage a list of locations
and routes, allowing users to easily navigate to their desired destination.
5. Robotics- Linked lists can be used to implement control systems for robots, allowing
them to navigate and interact with their environment.
6. Task Scheduling- Operating systems use linked lists to manage task scheduling, where
each process waiting to be executed is represented as a node in the list.
7. Image Processing- Linked lists can be used to represent images, where each pixel is
represented as a node in the list.
8. File Systems- File systems use linked lists to represent the hierarchical structure of
directories, where each directory or file is represented as a node in the list.
9. Symbol Table- Compilers use linked lists to build a symbol table, which is a data
structure that stores information about identifiers used in a program.
10. Undo/Redo Functionality- Many software applications implement undo/redo
functionality using linked lists, where each action that can be undone is represented as a
node in a doubly linked list.
11. Speech Recognition- Speech recognition software uses linked lists to represent the
possible phonetic pronunciations of a word, where each possible pronunciation is
represented as a node in the list.
12. Polynomial Representation- Polynomials can be represented using linked lists, where
each term in the polynomial is represented as a node in the list.
13. Simulation of Physical Systems- Linked lists can be used to simulate physical systems,
where each element in the list represents a discrete point in time and the state of the
system at that time.