DATA STRUCTURES

II YEAR
A data structure is a storage that is used to store and organize data.
It is a way of arranging data on a computer so that it can be accessed
and updated efficiently.
A data structure is not only used for organizing the data. It is also
used for processing, retrieving, and storing data
Types of Data Structure

Basically, data structures are divided into two categories:

Linear data structure

Non-linear data structure
Linear Data Structure:

A Linear Data Structure is a data structure in which elements are

arranged sequentially or in a linear order, where each element is
connected to the previous and the next element.

Non-Linear Data Structure:

A Non-Linear Data Structure is a data structure in which elements

are not arranged in sequential order. Instead, elements are connected
in a hierarchical or complex relationship.
Static Data Structure:

A Static Data Structure is a data structure whose size and

structure are fixed at compile time. Once the memory is allocated,
it cannot be changed during program execution..

Dynamic Data Structure:

A Dynamic Data Structure (also called non-static) is a data

structure that can grow or shrink in size during runtime as needed.
Array:
An array is a collection of similar types of elements stored together
in one place, where each element can be accessed using a
number called an index.

The individual element of an array can be accessed by specifying

name of the array, following by index or subscript inside square
brackets

(Collection of items in same data type in Continuous Memory

block)
Example of array:

CHOCOLATE
Elements Index
Array name
 0

The elements of array will always be stored in 2

the consecutive (continues) memory location.

3

It only starts from 0's & 1's

4
If the chocolate is[50] it will create an
5
50 Memory allocation
.

49
 Sample code:
1 0

int boxer[50]; 13 1

23 2

Data types Array Values

3

boxer[0] = 1; 4

boxer[1]=13; 5

boxer[2]=23; .

49
Abstract Data Type (ADT):
An Abstract Data Type (ADT) is a theoretical concept in data structures that defines
a data type by its behavior (operations) from the point of view of a user, without
specifying the implementation details.

It focuses on:
What operations can be performed on the data.
What outcomes to expect from those operations.
It does NOT describe how the operations are implemented.
Think of a TV remote:
You know what the buttons do (volume up, change channel, etc.)
But you don’t know (or need to know) how the circuit inside works.
Similarly, an ADT defines what operations are allowed, but hides how they are
done
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.
 LINKED LIST

NODE 1 NODE 2 NODE 3

Nodes are connected(Linked) with next node and to the next node.
LINKED LIST
NODE
INT NEXT
STRING DATA ADDRESS NODE IN
CLASS LIST
(It will show the next node
memory location)
 LINKED LIST
HEAD
NODE

DATA ADDRESS HEAD

NODE
The first node will always the head node
DATA ADDRESS
VALUE a
If it be an null the linked has been end NULL
LINKED LIST
HEAD TAIL
NODE NODE
DATA ADDRESS DATA ADDRESS

a b
The last node will be called as an Tail node
NULL
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
SINGLY LINKED LIST

struct Node {
int data;
struct Node* next;
};
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.
DOUBLY LINKED LIST

struct Node {
int data;
struct Node* next;
struct Node* prev;
};
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.
 DIFFERENCE BETWEEN ARRAY AND LINKED LIST
Array Linked list

Arrays is static data structure means its size can't be increased Linked list is dynamic data structure means its size can be
or decreased on runtime modified on runtime

If we are confirm to use n fixed block then linked list use

If we are confirm to use n fixed block and it is not going to
extra space for pointer to next node and it waste 2*n bytes
change in a program, so arrays is better
of memory space

Linked list is a complex data structure and it is used

Arrays is simpler to use
basically for complex programming

In arrays, insertion and deletion consequences as large In linked list, insertion and deletion doesn't need so much
amount of data movements data movements
Polynomial manipulation:
Polynomial manipulation is a fundamental application of data structures,
commonly used in symbolic computation systems. It involves performing
operations like addition, subtraction, multiplication, and evaluation of
polynomials.

A polynomial is a mathematical expression of the form:

4 3 2
5x + 4x + 3x + 2x + 1
 Stack
A stack is a linear data structure that follows the LIFO
(Last In, First Out) principle.
•void push (stack *s, int element);
/* Insert an element in the stack */
•int pop (stack *s);
/* Remove and return the top element */
•void create (stack *s);
/* Create a new stack */
•int isempty (stack *s);
/* Check if stack is empty */
•int isfull (stack *s);
/* Check if stack is full */
Application of Stacks
It is used to reverse a word. You push a given word to stack
– letter by letter and then pop letter from the stack.
“Undo” mechanism in text editor.
Backtracking: This is a process when you need to accessthe most
recent data element in a series of elements. Once you reach a dead
end, you must backtrack.
Language Processing: Compiler’ syntax check for matchingbraces in
implemented by usingstack.
Conversion of decimal number to binary.
To solve tower of Hanoi.
Conversion of infix expression into prefix and postfix.
Quick sort
Runtime memory management.
DECLARATION
#define MAXSIZE 100 struct lifo
struct lifo {
{ int value;
int st[MAXSIZE]; struct lifo *next;
inttop; };
}; typedef struct lifo
typedef struct lifo stack; stack;
stack s;
stack *top;

ARRAY LINKED LIST

EVALUATING ARITHMETIC
EXPRESSIONS
What is an Arithmetic Expression?
An arithmetic expression is a combination of:
Operands (e.g., 2, x)
Operators (e.g., +, -, *, /)
Types of Arithmetic Expressions
[Link] Expression
Operators are between operands
Example: A + B * C
[Link] Expression (Reverse Polish Notation)
Operators follow the operands
Example: A B C * +
[Link] Expression (Polish Notation)
Operators precede the operands
Example: + *A B C
A/B+C → INFIX INFIX TO POSTFX
A+B/C
INFIX TO POSTFIX
AB/C+

/
INFIX TO PREFIX AB/C+
+/ABC

+
OUTPUT

STACK
A/B+C → INFIX INFIX TO POSTFX
A * B + ( C- D / E ) #
INFIX TO POSTFIX
AB/C+

INFIX TO PREFIX
+/ABC