Introduction to data structures - Explore the basics

1.C Hello World Program
2.C Program to Print an Integer Entered By the User
3.C Program to Add Two Numbers
4.C Program to Multiply two Floating-Point Numbers
5.C Program to Print the ASCII Value of a Character
6.C Program to Swap Two Numbers
7.C Program to Find the Size of int, float, double, and char
8.C Program to Make a Simple Calculator
9.C Program to Print Hollow Star Pyramid in a Diamond Shape
10.C Program to Print Full Diamond Shape Pyramid
11.C Program to Display Prime Numbers Between Two Intervals
Using Functions
12.C Program to Print a 2D Array
13.C Program to Find the Largest Element in an Array
14.C Program to Find the Maximum and Minimum in an Array

Data Structure can be defined as the group of data elements
which provides an efficient way of storing and organizing
data in the computer so that it can be used efficiently.
examples of Data Structures are arrays, Linked List, Stack,
Queue, etc.
Data Structures are widely used in almost every aspect of
Computer Science i.e. Operating System, Compiler Design,
Artificial intelligence, Graphics and many more.
Data Structures are the main part of many computer science
algorithms as they enable the programmers to handle the
data in an efficient way.
It plays a vital role in enhancing the performance of a
software or a program as the main function of the software
is to store and retrieve the user’s data as fast as possible
 Data Structure= Organized Data + Allowed Operations
What is Data
Structure

Data Structure
 A data structure is a particular way of organizing data in
a computer so that it can be used effectively.
 For example, we can store a list of items having the same
data-type using the array data structure.

The representation of particular data structure in the
main memory of a computer is called as storage
structure.
The storage structure representation in auxiliary
memory is called as file structure.
It is define as the way of storing and manipulating
data in organized form so that it can be used efficiently
Data Structure mainly specifies the following four
things:
1)organization of data 2)accessing method 3)degree
of associativity 4) processing alternative for information
Algorithm + Data Structure = Program
Data Structure study Covers the following points
1) Amount of memory require to store
2) Amount of time require to process
3) Representation of data in memory

Types Of DS
The DS are divided into two
types:
1) Primitive (built in)
2) Non primitive(user defined)
Non primitive divided into two
type
3) Linear DS
4) Non linear DS

Applications
of Arrays
 Arrays
Arrangement of leader-board of a game
can be done simply through arrays to
store the score and arrange them in
descending order to clearly make out the
rank of each player in the game.
2D arrays, commonly known as, matrix,
are used in image processing.
It is also used in speech processing, in
which each speech signal is an array.

Applications
of the linked
list
1.Images in a location are linked with each
other. So, an image viewer software uses
a linked list to view the previous and the
next images using the previous and next
buttons.
2.Web pages can be accessed using the
previous and the next URL links which are
linked using linked list.
3.The music players also use the same
technique to switch between music.
4.To keep the track of turns in a multi
player game, a circular linked list is used.

Applications
of a stack
Some Applications of a stack are:
1.Undo operation is also carried out through
stacks.
2.Forward – backward surfing in browser
3.History of visited websites
4.Message logs and all messages you get are
arranged in stack
5.Call logs, E-mails, Google photos’ any gallery ,
YouTube downloads, Notifications ( latest
appears first )
6.Syntaxes in languages are parsed using stacks.
7.Converting infix to postfix expressions.

Applications
of Queue
1.
Operating System uses queue for job scheduling.
2.
To handle congestion in networking queue can be
used.
3.
Data packets in communication are arranged in
queue format.
4.
Sending an E-mail, it will be queued
5.
server while responding request
6.
Uploading and downloading photo’s, first kept for
uploading/downloading will completed first (Not if
there is threading)
7.
Most of internet requests and processes uses queue
8.
While switching multiple applications, windows uses
circular queue.

Applications
of a Graph
1.Facebook’s Graph API uses the structure of
Graphs. (The Graph API is the primary way to get data into and
out of the Facebook platform. It's an HTTP-based API that apps can
use to programmatically query data, post new stories, manage ads,
upload photos, and perform a wide variety of other tasks.)
2.Google’s Knowledge Graph also has to do
something with Graph. ( knowledge base that represents semantic
relations between concepts in a network.)
3.GPS navigation system also uses shortest path
APIs.
4.Networking components has huge application of
graph
5.Facebook, Instagram and all social media
networking sites every user is Node
6.Data organization

Applications
of the trees
1.XML Parser uses tree algorithms.
2.Decision-based algorithm is used in machine
learning which works upon the algorithm of tree.
3.Databases also uses tree data structures for
indexing.
4.Domain Name Server(DNS) also uses tree
structures.
5.File explorer/my computer of mobile/any
computer
6.BST used in computer Graphics
7.Posting questions on websites like Quora, the
comments are child of questions

DATA TYPES
A particular kind of data
item, as defined by the
values it can take, the
Programming language
used, or the operations
that can be performed
on it.
Primitive Data Structure
 Primitive Data Structure are basic structure and
directly operated upon by machine instructions.
 Primitive data structures have different
representations on different computers.
 Integers, floats, character and pointers are example
of primitive data structures.
 These data types are available in most
programming languages as built in type.
Integer: It is a data type which allows all values
without fraction part. We can used it for whole
numbers.
Float: It is a data type which is use for storing
fraction numbers.
Character: It is a data type which is used for
character values.
Pointer: A variable that hold memory address of

Non Primitive Data Type
 These are more sophisticated data structures.
 These are derived from primitive data structure.
 The non – primitive data structures emphasize structuring
of a group of homogeneous or heterogeneous data items.
 Example of non – primitive data types are Array, List, and
File etc.
 A non – primitive data type is further divided into Linear
and non – Linear data structure.
Array: An array is a fixed size sequenced collection of
elements of the same data type.
List: An ordered set containing variable number of
elements is called as List.
File: A file is a collection of logically related information. It
can be viewed as a large list of records consisting of
various fields.

Linear Data Structures
A linear data structure simply means that it is a
storage format of the data in the memory in
which the data are arranged in contiguous blocks
of memory.
Example is the array of characters it represented
by one character after another.
In the linear data structure, member elements
form a sequence in the storage.
There are two ways to represent a linear data
structure in memory.
 static memory allocation
 dynamic memory allocation

Operations on Data structures
1. Traversing
2. Searching
3. Insertion
4. Deletion
5. Selection
6. Update
7. Sort
8. Merge
9. Split

Program 1 – Menu driven program to implement linear
search and binary search and find the location of an
element on its first occurrence
Main Function
Step 1 : List the choices
Step 2: Enter the choice
Step 3: Validate the choice
Step 4: if option is 1 then call linear() function; 2 calls
binary() function; 3 exits

Introduction to data structures - Explore the basics

Quicksort
 Quick sort is a fast sorting algorithm used to sort a list of
elements.
The quick sort algorithm attempts to separate the list of
elements into two parts and then sort each part
recursively. That means it use divide and
conquer strategy.
 In quick sort, the partition of the list is performed based
on the element called pivot. Here pivot element is one of
the elements in the list.
 The list is divided into two partitions such that "all
elements to the left of pivot are smaller than the pivot
and all elements to the right of pivot are greater than
or equal to the pivot".

Steps of
quick sort
Step by Step Process
In Quick sort algorithm, partitioning of the list is
performed using following steps...
Step 1 - Consider the first element of the list as
pivot (i.e., Element at first position in the list).
Step 2 - Define two variables i and j. Set i and j to
first and last elements of the list respectively.
Step 3 - Increment i until list[i] > pivot then stop.
Step 4 - Decrement j until list[j] < pivot then stop.
Step 5 - If i < j then exchange list[i] and list[j].
Step 6 - Repeat steps 3,4 & 5 until i >= j.
Step 7 - Exchange the pivot element with list[j]
element.

 Merge sort is a sorting algorithm that follows the
divide-and-conquer approach. It works by recursively
dividing the input array into smaller subarrays and
sorting those subarrays then merging them back
together to obtain the sorted array.
 Here’s a step-by-step explanation of how merge sort
works:
1.Divide: Divide the list or array recursively into two halves
until it can no more be divided.
2.Conquer: Each subarray is sorted individually using the
merge sort algorithm.
3.Merge: The sorted subarrays are merged back together
in sorted order. The process continues until all elements
from both subarrays have been merged.

def mergeSort(arr):
 if len(arr) <= 1:
 return arr
 mid = len(arr) / 2
 leftHalf = arr[0:mid]
 rightHalf = arr[mid:len(arr)]
 sortedLeft = mergeSort(leftHalf)
 sortedRight = mergeSort(rightHalf)
 return merge(sortedLeft, sortedRight)

1. def merge(left, right):
2. result = []
3. i = j = 0
4. while i < len(left) and j
< len(right):
5. if left[i] < right[j]:
6.
result.append(left[i])
7. i += 1
8. else:
9.
result.append(right[j])
10. j += 1
11.result.extend(left[i:])
12. result.extend(right[j:])
13. return result
14.unsortedArr = [3, 7, 6, -
10, 15, 23.5, 55, -13]
15.sortedArr =
mergeSort(unsortedArr)
16.print("Sorted array:",
sortedArr)

 List Operations:
  Traversal: Traversal of a data structure
means processing all the data elements of it,
sequentlly.
  Insertion: Insertion means addition of a new
data element in a data structure.
  Deletion: Deletion means removal of a data
element from a data structure. The data
element is searched for before its removal.
  Searching: Searching involves searching for
the specified data element in a data structure.
  Sorting: Arranging data elements of a data
structure in a specified order is called sorting.
  Merging: Combining elements of two similar
data structures to form a new data structure of
same type, is called merging.

Insert an
element
Algorithm InsertLA (DATA, N, ITEM, LOC)
Desc: This algorithm inserts new element ITEM in linear array DATA
with N elements
If LOC=1 it means the element has to insert in beginning
If LOC =N+1 it means the element have to be inserted at the end
If LOC = J it means the elements have to be inserted at Jth Location
Begin
Step 1: [Initialize counter I with index of last element] I=N
Step 2: While I >=LOC repeat steps 3 and 4
Step 3: [Move the current element one position backwards]
DATA[I+1]=DATA[I]
Step 4: [Decrement counter I]
I=I-1
Step 5:[Insert new element at the Location]
DATA[LOC]=ITEM
Step 6:[ Update total under of array elements]
N=N+1
Exit

 It is a process of deleting a particular
element from an array. If an element to be
deleted ith location then all elements from
the (i+1)th location we have to be shifted
one step towards left.
So (i+1)th element is copied to ith location
and (i+2)th to (i+1)th location and so on.
Algorithm: In this algorithm a value is being
deleted from ith location of an array Reg[N]. Let us
assume that last element in the array is at Mth
position.
Steps
1. Back=i
2. While (Back<M) repeat 3 and 4
3. Reg[Back]= Reg[Back+1]
4. Back= Back+1
5. M=M-1
6. End

There are 4 library functions provided by C defined
under <stdlib.h> header file to facilitate dynamic memory
allocation in C programming. They are:
1.malloc()
2.calloc()
3.free()
4.realloc()

malloc()
method
The “malloc” or “memory allocation” method
in C is used to dynamically allocate a single
large block of memory with the specified size.
It returns a pointer of type void which can be
cast into a pointer of any form. It doesn’t
Iniatialize memory at execution time so that it
has initializes each block with the default
garbage value initially.
ptr = (cast-type*) malloc(byte-size)
For Example:
ptr = (int*) malloc(100 * sizeof(int));

C calloc()
method
“calloc” or “contiguous allocation” method in C
is used to dynamically allocate the specified
number of blocks of memory of the specified
type. it is very much similar to malloc() but has
two different points and these are:
1.It initializes each block with a default value
‘0’.
2.It has two parameters or arguments as
compare to malloc().
ptr = (cast-type*)calloc(n, element-
size);
n= no. of elements and
element-size is the size of each
element.
ptr = (float*) calloc(25,
sizeof(float));

free()
method
free() method in C is used to
dynamically de-allocate the memory.
The memory allocated using functions
malloc() and calloc() is not de-allocated
on their own. Hence the free() method
is used, whenever the dynamic memory
allocation takes place. It helps to
reduce wastage of memory by freeing
it.
Syntax:
free(ptr);

realloc()
method
“realloc” or “re-allocation” method in C is used
to dynamically change the memory allocation
of a previously allocated memory. In other
words, if the memory previously allocated with
the help of malloc or calloc is insufficient,
realloc can be used to dynamically re-allocate
memory. re-allocation of memory maintains the
already present value and new blocks will be
initialized with the default garbage value.
ptr = realloc(ptr, newSize);
where ptr is reallocated with new size 'newSize'.

Linked List
A linked list is a non-sequential collection of data items.
It is a dynamic data structure. For every data item in a
linked list, there is an associated pointer that would
give the memory location of the next data item in the
linked list.
 The data items in the linked list are not in consecutive
memory locations. They may be anywhere, but the
accessing of these data items is easier as each data
item contains the address of the next data item.

Advantages
of linked lists
1. Linked lists are dynamic data structures. i.e.,
they can grow or shrink during the execution of a
program.
2. Linked lists have 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.
3. Insertion and Deletions are easier and efficient.
Linked lists provide flexibility in inserting a data
item at a specified position and deletion of the
data item from the given position.
4. Many complex applications can be easily
carried out with linked lists.

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

Why use
linked list
over array?
 Array has the 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.
Inserting any element in the array needs
shifting of all its predecessors.

Disadvantag
es of linked
lists
1. It consumes more space
because every node requires a
additional pointer to store
address of the next node.
2. Searching a particular element
in list is difficult and also time
consuming.

Comparison
between
array and
linked list

Types of
Linked Lists
1. Single Linked List.
2. Double Linked List.
3. Circular Linked List.
4. Circular Double Linked List.

 A single linked list is one in which all nodes are linked together
in some sequential manner. Hence, it is also called as linear
linked list.
 A double linked list is one in which all nodes are linked together
by multiple links which helps in accessing both the successor
node (next node) and predecessor node (previous node) from any
arbitrary node within the list. Therefore each node in a double
linked list has two link fields (pointers) to point to the left node
(previous) and the right node (next). This helps to traverse in
forward direction and backward direction.
 A circular linked list is one, which has no beginning and no end.
A single linked list can be made a circular linked list by simply
storing address of the very first node in the link field of the last
node.
 A circular double linked list is one, which has both the successor
pointer and predecessor pointer in the circular manner.

Implementat
ion of Single
Linked List
Before writing the code to build the above
list, we need to create a start node, used
to create and access other nodes in the
linked list.
 Creating a structure with one data item
and a next pointer, which will be pointing
to next node of the list. This is called as
self-referential structure.
 Initialize the start pointer to be NULL.

Creating a
node for
Single Linked
List

void createlist(int n)
{
int i;
node * newnode;
node *temp;
for(i = 0; i < n ; i+ +)
{
newnode = getnode();
if(start = = NULL)
{
start = new node;
}
else
{
temp = start;
while(temp - > next != NULL)
temp = temp - > next;
temp - > next = new node;
}
}
}

Insertion of
a Node
 Inserting a node at the beginning.
 Inserting a node at the end.
 Inserting a node at intermediate
position.
Inserting a node at the beginning:
The following steps are to be followed to
insert a new node at the beginning of the list:
Get the new node using getnode().
If the list is empty then start = newnode.
If the list is not empty, follow the steps given
below:
newnode -> next = start;
start = newnode;

void insert_at_beg()
{
node *newnode;
if(start == NULL)
{
start = newnode;
}
else
{
newnode -> next = start;
start = newnode;
}
}

Inserting a
node at the
end
The following steps are
followed to insert a new
node at the end of the list:
• Get the new node using
getnode()
• newnode = getnode();
• If the list is empty then
start = newnode.
• If the list is not empty
follow the steps given
below:
• temp = start;
• while(temp -> next !=
NULL)
• temp = temp ->
next;
void insert_at_end()
{
node *newnode, *temp;
if(start == NULL)
{
start = newnode;
}
else
{
temp = start;
while(temp -> next != NULL)
temp = temp -> next;
temp -> next = newnode;
}
}

Inserting a
node at
intermediat
e position
Get the new node using getnode().
Ensure that the specified position is in between first node
and last node. If not, specified position is invalid. This is
done by countnode() function.
Store the starting address (which is in start pointer) in
temp and prev
pointers. Then traverse the temp pointer upto the specified
position followed by prev pointer.
After reaching the specified position, follow the steps given
below:
prev -> next = newnode;
newnode -> next = temp;

Counting the Number of Nodes:
The following code will count the number of nodes
exist in the list using recursion.
int countnode(node *st)
{
if(st = = NULL)
return 0;
else
return(1 + countnode(st - > next));
}

void insert_at_mid()
{
node *newnode, *temp, *prev;
int pos, nodectr, ctr = 1;
printf("n Enter the position: ");
scanf("%d", &pos);
nodectr = countnode(start);
if(pos > 1 && pos < nodectr)
{
temp = prev = start;
while(ctr < pos)
{
prev = temp;
ctr++;
}
prev -> next = newnode;
newnode -> next = temp;
}
else
{
printf("position %d is not a midd
position", pos);
}
}

Deletion of a
node
Another primitive operation that can be done
in a singly linked list is the deletion of a node.
Memory is to be released for the node to be
deleted. A node can be deleted from the list
from three different places namely.
Deleting a node at the beginning.
Deleting a node at the end.
Deleting a node at intermediate position

Deleting a
node at the
beginning
The following steps are
followed, to delete a node
at the beginning of the list:
If the list is not empty,
follow the steps given
below:
temp = start;
start = start -> next;
free(temp);
void delete_at_beg()
{
node *temp;
if(start == NULL)
{
printf("n No nodes are
exist..");
return ;
}
else
{
temp = start;
start = temp -> next;
free(temp);
printf("n Node deleted ");
}
}

Deleting a
node at the
end
The following steps are followed to
delete a node at the end of the list:
If the list is empty, display error
message
If the list is not empty, follow the steps
given below:
while(temp -> next != NULL)
{
prev = temp;
}
prev -> next = NULL;
free(temp);
void delete_at_last()
{
node *temp, *prev;
if(start == NULL)
{
printf("n Empty List.."
return ;
}
else
{
temp = start;
prev = start;
while(temp -> next !=
NULL)
{
prev = temp;
}
prev -> next = NULL;
free(temp);
printf("n Node delete
");
}
}

Deleting a
node at
Intermediate
position
If the list is empty, then display ‘empty list
message’
If the list is not empty, follow the steps given
below.
{
ctr = 1;
while(ctr < pos)
{
prev = temp;
ctr++;
}
prev -> next = temp -> next;
free(temp);
printf("n node deleted..");

void delete_at_mid()
{
int ctr = 1, pos, nodectr;
node *temp, *prev;
if(start == NULL)
{
printf("n Empty List..");
return ;
}
else
{
printf("n Enter position of node to
delete: ");
scanf("%d", &pos);
nodectr = countnode(start);
if(pos > nodectr)
{
printf("nThis node doesnot exist");
}
{
while(ctr < pos)
{
prev = temp;
ctr ++;
}
prev -> next = temp -> next;
free(temp);
printf("n Node deleted..");
}
else
{
printf("n Invalid position..");
getch();
}
}
}

Traversal
and
displaying a
list (Left to
Right)
void traverse()
{
node *temp;
temp = start;
printf("n The contents of List (Left to Right):
n");
if(start == NULL )
printf("n Empty List");
else
{
while (temp != NULL)
{
printf("%d ->", temp -> data);
}
}
printf("X");
}

Infix to
Postfix
 Algorithm
1. Scan the infix expression from left to right.
2. If the scanned character is an operand, output it.
3. Else,
1 If the precedence of the scanned operator is greater
than the precedence of the operator in the stack(or the stack
is empty or the stack contains a ‘(‘ ), push it.
2 Else, Pop all the operators from the stack which are
greater than or equal to in precedence than that of the
scanned operator. After doing that Push the scanned
operator to the stack. (If you encounter parenthesis while
popping then stop there and push the scanned operator in
the stack.)
4. If the scanned character is an ‘(‘, push it to the stack.
5. If the scanned character is an ‘)’, pop the stack and output
it until a ‘(‘ is encountered, and discard both the parenthesis.
6. Repeat steps 2-6 until infix expression is scanned.
7. Print the output
8. Pop and output from the stack until it is not empty.

A * ( B + C )  ABC + * D /
(A + ( B * C))  ABC*+
((A + B) * (C + E))  AB + CE+*
((A + (B * C))/(D - E))  ABC * + DE - /

Algorithm to evaluate the postfix expression
1. Create a stack to store operands.
2. Scan the given expression from left to right.
3. a) If the scanned character is an operand, push it
into the stack.
b) If the scanned character is an operator, POP two
operands from stack and perform operation and PUSH
the result back to the stack.
4. Repeat step 3 till all the characters are scanned.
5. When the expression is ended, the number in the
stack is the final result.

Doubly Linke
d List
A Doubly Linked List (DLL) contains
an extra pointer, typically
called previous pointer, together with
next pointer and data which are
there in singly linked list.

Advantages over singly linked list
1) A DLL can be traversed in both forward
and backward direction.
2) The delete operation in DLL is more
efficient if pointer to the node to be
deleted is given.
3) We can quickly insert a new node
before a given node.
In singly linked list, to delete a node,
pointer to the previous node is needed. To
get this previous node, sometimes the list
is traversed. In DLL, we can get the
previous node using previous pointer.

Disadvantages over singly linked
list
1) Every node of DLL Require extra
space for an previous pointer. It is
possible to implement DLL with
single pointer though
2) All operations require an extra
pointer previous to be maintained.
For example, in insertion, we need to
modify previous pointers together
with next pointers.

Creating a
Node in
Doubly
Linked List
Each node in a doubly linked list has data as well pointers.
Therefore, we use a structure to create the node.
The structure template for the node looks as follows:
struct Node
{
int data; //The data point
struct Node *Prev; //Pointer to the previous
node
struct Node *Next; //Pointer to the next
node
};

Traversal in a
Doubly
Linked List
List_traversal(struct Node *Head)
{
Prev = (struct Node *)malloc(sizeof(struct
Node));
Next = (struct Node *)malloc(sizeof(struct
Node));
if(Head == NULL) //If the list is empty
return;
while(Next->Data != NULL)
{
Print(Next->data); //The display operation
}
}

Insertion
A node can be added in four
ways
1) At the front of the DLL
2) After a given node.
3) At the end of the DLL
4) Before a given node.

Insert a node
at front (5
Steps)

Insert a node at front (5
Steps)
//Given a reference 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 point to earlier head and previous as NULL */
new_node->next = (*head_ref);
new_node->prev = NULL;
/* 4. change prev of earlier head node to new node */
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
/* 5. move the head to point to the new node */
(*head_ref) = new_node;
}

Add a node
after a
given node
/* Given a node as prev_node, insert a new
node after the given node */
void insertAfter(struct Node* prev_node, int
new_data)
{
/*1. check if the given prev_node is NULL
*/
if (prev_node == NULL) {
printf("the given previous node cannot
be NULL");
return;
}
/* 2. allocate new node */
struct Node* new_node = (struct
Node*)malloc(sizeof(struct Node));
/* 4. Make next of new node
as next of prev_node */
new_node->next = prev_node-
>next;
/* 5. Make the next of
prev_node as new_node */
prev_node->next = new_node;
/* 6. Make prev_node as
previous of new_node */
new_node->prev = prev_node;
/* 7. Change previous of
new_node's next node */
if (new_node->next != NULL)
new_node->next->prev =
new_node;
}

Add a node
before a
node
Let the pointer to this given node be next_node and the data of
the new node to be added as new_data.
1.Check if the next_node is NULL or not. If it’s NULL, return from
the function because any new node can not be added before a
NULL
2.Allocate memory for the new node, let it be called new_node
3.Set new_node->data = new_data
4.Check for empty list
5.Set the previous pointer of this new_node as the previous node
of the next_node, new_node->prev = next_node->prev
6.Set the previous pointer of the next_node as the new_node,
next_node->prev = new_node
7.Set the next pointer of this new_node as the next_node,
new_node->next = next_node;
8.If the previous node of the new_node is not NULL, then set the
next pointer of this previous node as new_node, new_node-
>prev->next = new_node
9.Else, if the prev of new_node is NULL, it will be the new head
node. So, make (*head_ref) = new_node.

void append(struct Node** head_ref, int
new_data)
{
/* 1. allocate node */
struct Node* new_node = (struct
Node*)malloc(sizeof(struct Node));
struct Node* last = *head_ref;
/* used in step 5*/
/* 5. Else traverse till the last
node */
while (last->next != NULL)
last = last->next;
/* 6. Change the next of last node
*/
last->next = new_node;
/* 7. Make last node as previous of
new node */
new_node->prev = last;
return;
}
/* 3. This new node is going to be the last
node, so make next of it as NULL*/
new_node->next = NULL;
/* 4. If the Linked List is empty, then
make the new node as head */
if (*head_ref == NULL) {
new_node->prev = NULL;
*head_ref = new_node;
return;
}

Deletion
from a
Doubly
Linked List
1. Deletion from beginning
2. Deletion at the end
3. Deleting a node other than the
first and the last node

Deletion from
the beginning
Algorithm to delete node from beginning
%% Input: head {Pointer to first node of the linked
list}
Begin:
If (head == NULL) then
write ('Can't delete from an empty list')
End if
Else then
toDelete head;
←
head head.next;
←
head.prev NULL;
←
unalloc (toDelete)
write ('Successfully deleted first node from the
list')
End if
End

Deletion at
the end
Algorithm to delete node from end
%% Input: last {Pointer to last node of the linked
list}
Begin:
If (last == NULL) then
write ('Can't delete from an empty list')
End if
Else then
toDelete last;
←
last last.prev;
←
last.next NULL;
←
unalloc (toDelete)
write ('Successfully deleted last node from the
list')
End if
End

Algorithm
to delete
node from
any position
of a doubly
linked list
Algorithm to delete node from any position
%% Input : head {Pointer to the first node of the list}
last {Pointer to the last node of the list}
N {Position to be deleted from list}
Begin:
current head;
←
For i 1 to N and current != NULL do
←
current current.next;
←
End for
If (N == 1) then
deleteFromBeginning()
End if
Else if (current == last) then
deleteFromEnd()
End if
Else if (current != NULL) then
current.prev.next current.next
←
If (current.next != NULL) then
current.next.prev current.prev;
←
End if
unalloc (current)
write ('Node deleted successfully from ', N, '
position')
End if
Else then
write ('Invalid position')
End if

Defining a
node
1.typedef struct node//
defining structure node
2.{
3. int data;
4. struct node *link;
5.}node;

Creation of
new node
1. //creates a new node
2. node *create()
3. {
4. node *temp=(node*)malloc(sizeof(node));
5. printf("enter datan");
6. scanf("%d",&temp->data);
7. temp->link=NULL;
8. size++;
9. return temp;
10.}

Traverse to a
node in the
list
1. node *traverse(node *start,int pos)
2. {
3. int i=1;
4. do
5. {
6. i++;
7. start=start->link;
8. }while(i<pos);
9. return start;
10.}

Insert after a
node
1. //inserts node after curr node
2. void insert(node *curr)
3. {
4. node *temp=create();
5. temp->link=curr->link;
6. curr->link=temp;
 }

Insert at the
beginning
1. node *insert_start(node *start, node *end)
2. {
3. //printf("%dn",start->data);
4. node *curr=create();
5. curr->link=start;
6. start=curr;
7. end->link=start;
8. return start;
9. }

Insert at the
end
1. node *insert_end(node *start, node *end)
2. {
3. node *curr=create();
4. end->link=curr;
5. curr->link=start;
6. end=curr;
7. return end;
8. }

Traverse
1. void display(node *start, int size)
2. {
3. node *temp=start;int i=1;
4. printf("ncircular linkedlistn");
5. if(size==0)
6. {
7. printf("List Emptyn");
8. return;
9. }
10. do
11. {
12. i++;
13. printf("%dn",start->data);
15. }while(start!=temp&&i<=size);
16. printf("n");
17.}

Delete a
node at
given
location
1. void delete(node *start,node *end,int pos)
2. {
3. node *temp,*temp2;
4. temp=traverse(start,pos);//
traverses to prev node from current pos
5. temp2=temp->link;//set to next node from pos
6. temp->link=temp2->link;//
connection of prev to next node
7. free(temp2);
8. size--;
9. display(start);
10.}

Delete from
beginning
1. node *delete_from_beg(node *start,node *end)
2. {
3. node *temp;
4. if(size==1)//
to delete remaining one element in list since both are linked to each other
5. {
6. // free(start);
7. /+/ free(end);
8. size--;
9. start=end=NULL;
10. display(start);
11. return NULL;
12. }
13. else
14. {
15. temp=start;
17. end->link=start;
18. free(temp);
19. size--;
20. display(start);
21. return start;
22. }
23. }
24.

Delete from
end
1. node *delete_from_end(node *start,node *end)
2. {
3. node *temp;
4. if(size==1)
5. {
6. start=delete_from_beg(start,end);
7. return start;
8. }
9. else
10. {
11. temp=traverse(start,size-1);
12. temp->link=start;
13. free(end);
14. end=temp;
15. size--;
16. display(start);
17. return end;
18. }
19.}

Introduction to data structures - Explore the basics

Recommended

More Related Content

Similar to Introduction to data structures - Explore the basics (20)

More from divyammo (8)

Recently uploaded (20)

Introduction to data structures - Explore the basics

Editor's Notes