👋 October 2023 Community Survey - How can we make RemNote better for you?

DS unit 1 Share

DS unit 1 50 / 50

data ↔ collection of numbers, alphabets and symbols combined to represent

information.
types of data ↕
Atomic data ↕
non decomposable entity
For example, integer value 2305 or character value ‘A’ cannot be further
divided. if we further divide the value 2305 in four different digits ‘2’,’3’,’0’ and
‘5’ then its meaning will be lost.
Composit data ↕
decomposable entity
It is a composition of several atomic data and hence can be further divided
into atomic data.
data type ↕
it refers to the kind of data a variable might hold in a programming language
a value cannot be interpreted if the type is not mentioned
data can be of various types such as: int, float, char, bool, etc
data types are the building blocks of data structures.
types of data type ↕
boolean ‒ logical values ‒ true or false
integer ‒ numbers ‒ signed: can contain negative nos ‒ unsigned: from 0
floating point ‒ decimal nos
charachter ‒ symbols, letters,etc
pointer ‒ used to point other values
string ‒ aplphabets, words, etc ‒ in between ' '
abstract data type ↕
it is also known as adt
it a type or class for objects, whose behaviour is defined by a set of values or
operations
ADT only mentions the operations that are to be performed but not how the
operations should be implemented
it also does not specify how the data will be strored in the memory or the
algorithm that should be used for performing those operations
it is called abstract because it give application independent view
The abstract datatype is special kind of datatype, whose behavior is defined by
a set of values and set of operations.
The keyword “Abstract” is used as we can use these datatypes, we can perform
different operations. But how those operations are working that is totally hidden
from the user.
The ADT is made of with primitive datatypes, but operation logics are hidden.
Some examples of ADT are Stack, Queue, List etc.

data structure ↕
data structure is used to organize, process, retrieve and store data
DS make it easy for users to access and work with the data they need in
appropriate ways.
 most importantly, data structures organize the information in such a way that it
is easy to understand for machines and as well as humans
The idea is to reduce the space and time complexities of different tasks.
it is important to choose a data structure that is suitable for your situation
because choosing an ill-suited data structure could result in slow runtimes or
unresponsive code.
5 factors to consider before choosing a data structure ↕
What kind of information will be stored?
How will that information be used?
Where should data persist, or be kept, after it is created?
What is the best way to organize the data?
What aspects of memory and storage reservation management
should be considered?
Use of data structures ↕
it is used to implement physical form of ADT
it is a crucial part of designing efficient software
They also play a critical role in algorithm design and how those algorithms are
used within computer programs.
some examples of how DS is used:
storing data: specifies the collection of attributes and corresponding
structures used to store records in a database management system.
managing resources and services: Core operating system (OS) resources and
services areenabled through the use of data structures
data exchange: define the organization of information shared
betweenapplications, such as TCP/IP packets.
ordering and sorting: using priority queues, programmers can manage items
organized according to a specific priority.
indexing: sophisticated data structures such as B-trees are used to index
objects, such as those stored in a database.
searching: binary search trees, B-trees or hash tables speed the ability to find
a specific sought-after item.
scalbility: used for allocating and managing data storageacross distributed
storage locations, ensuring scalability and performance.
charachteristica of ds ↕
Linear or non-linear: This characteristic describes whether the data items are
arranged in sequential order, such as with an array, or in an unordered
sequence, such as with a graph.
linear: has a pattern
non linear: does not have a pattern
Homogeneous or heterogeneous: This characteristic describes whether all data
items in a given repository are of the same type. One example is a collection of
elements in an array, or of various types, such as an abstract data type defined
as a structure in C or a class specification in Java.
homogeneous: of same type
heterogeneous: of different type
Static or dynamic: This characteristic describes how the data structures are
compiled. Static data structures have fixed sizes, structures and memory
locations at compile time. Dynamic data structures have sizes, structures and
memory locations that can shrink or expand, depending on the use.
static: size is already fixed
dynamic: we can freely add or delete items
types of linear data structures
array ↕
An array stores a collection of items at adjoining memory locations.
Items that are the same type are stored together so the position of each
element can be calculated or retrieved easily by an index.
Arrays can be fixed or flexible in length.

stack ↕
A stack stores a collection of items in the linear order that operations are
applied.
This order could be last in, first out (LIFO) or first in, last out (FILO).
queue ↕
A queue stores a collection of items like a stack;
however, the operation order can only be first in, first out.

linked list ↕
A linked list stores a collection of items in a linear order.
Each element, or node, in a linked list contains a data item, as well as a
reference, or link, to the next item in the list.
Types of non linear data structure ↔
tree ↕
A tree stores a collection of items in an abstract, hierarchical way.
Each node is associated with a key value, with parent nodes linked to child
nodes -- or subnodes.
There is one root node that is the ancestor of all the nodes in the tree.

Heap ↕
A heap is a tree-based structure in which each parent node's associated key
value is greater than or equal to the key values of any of its children's key
values.
two types of heap
Max-Heap: In a Max-Heap the key present at the root node must be greatest
among the keys present at all of its children.
Min-heap: Min-Heap the key present at the root node must be minimum among
the keys present at all of it’s children.

Graph ↕
A graph stores a collection of items in a nonlinear fashion.
Graphs are made up of a finite set of nodes, also known as vertices, and lines
that connect them, also known as edges.
These are useful for representing real-world systems such as computer
networks.
trie ↕
A trie, also known as a keyword tree, is a data structure that stores strings as
data items that can be organized in a visual graph.

Hash table ↕
A hash table -- also known as a hash map -- stores a collection of items in an
associative array that plots keys to values.
A hash table uses a hash function to convert an index into an array of buckets
that contain the desired data item.

Operations that can be performed on linear data structures ↔

for stack ↕
isFull(): used to check whether the stack is full or not
isEmpty(): used to check whether the stack is empty or not
push(z): used to push z in stack
 pop(): used to delete one element from top of the stack
peek(): used to get the top most element of the stack
size(): used to get number of elements present into the stack
for queue ↕
isFull(): used to check whether the queue is full or not
isEmpty(): used to check whether the queue is empty or not
insert(z): used to insert z in queue
delete(): used to delete one element form the front end of tehe queue
size(): gets the size of the queue
enqueue(): putting items in the queue
dequeue(): remove items form the queue
for linked list ↕
size(): gets the size of the list
insert(z): used to insert z into the list
remove(z): used to remove z from the list
get(i): used to get the elemet at position i
replace(z,x): used to replace z with x
basic Operations performed on data structures in general ↕
searching: search for an element in the datastructure
sorting: sort elements in ascending or descending order
insertion: insert an element in the datastructure
deletion: delete an element from the datastructure
updation: we can update or replace elements of a datastructure
Advantages of data structure ↕
Data structures allow storing the information on hard disks.
An appropriate choice of ADT (Abstract Data Type) makes the program more
efficient.
Data Structures are necessary for designing efficient algorithms.
It provides reusability and abstraction.
Using appropriate data structures can help programmers save a good amount of
time while performing operations such as storage, retrieval, or processing of
data.
Manipulation of large amounts of data is easier.