WHAT'S IS DATA STRUCTURE?
Is a named group of data of different data types which is stored in a specific way and can be
processed as a single unit. A data structure has well-defined operations, behaviour and
properties.
DATA TYPE VS. DATA STRUCTURE
DATA TYPE defines the type of values we can store and operations we can perform. For example in int
data type we cannot store decimal values, we cannot multiply two string type values. It also specifies
amount of memory it will take. DATA STRUCTURE is physical implementation that
clearly defines a way of storing, accessing and manipulation of data stored in data structure. Every
data structure has a specific way of insertion and deletion like STACK work on LIFO i.e. all operation
will take from one end i.e. TOP where as QUEUE works on FIFO i.e. item inserted first will be removed
first and new item will always added to the end of QUEUE.
In python we will use LIST as a data structure.
TYPES OF DATA STRUCTURE
Data structure can be classified into following two types:
Simple Data structure : these are built from primitive data types like integer, float, string or Boolean.
Example: Linear List or Array
Complex Data structure : simple data structure can be combined in various way to form more complex
data structure. It is of two types:
Linear : are single level data structure i.e. in linear fashion to form a sequence. Example : STACK, QUEUE, LINKED
LIST
Non-Linear: are multilevel data structure. Example: TREE and GRAPH.
LINEAR LIST ARRAYS
Refers to named list of finite number of n similar data elements. Each of the data elements can be
accessed by its unique index/subscript position usually 0,1,2,3,…For example if the list mylist contains 10
elements then first element will be mylist[0], second will be mylist[1] and so on. Array can be Single Dimensional or
Multidimensional. In Python arrays are implemented through List data types as Linear List or through NumPy arrays.
STACK
Allow to insert and delete items from one end only called TOP.
Stack works on LIFO principle. It means items added in list will be removed first.
Real life Example: Stack of Plates, Books, Bangles
Computer based examples: Undo Operation, Function Call etc.
QUEUE
Allows insertion and deletion from different end i.e. insertion from REAR and deletion from
FRONT Queue works on FIFO principle i.e. item added first will be removed first. Real life example: Queue of People
for ticket Computer based example: Keyboard typing, Printer etc.
LINKED LIST
It is dynamic data structure i.e. size of Linked List is not pre-known before the execution of
program. It takes memory as per requirement during runtime and every item allocated
dynamically will be known as NODE. NODE contains 2 parts: (1) INFO part stores the
actual data to store like roll no. name, marks etc. and (2) LINK holds the address of next allocated
node in memory creating chain of linked items Singly Linked List hold the address of next node
and last Node will point to NULL whereas Doubly Linked List holds the address of next as
well as previous node allows both forward andbackward movement
TREES
Are multilevel data structure having hierarchical relationship among its elements called nodes.
Topmost node is called the root of tree and bottommost nodes are called leaves of tree.
Each of the node holds the address of nodes below it. It will never contains a closed loop
OPERATIONS ON DATA STRUCTURE
INSERTION - Addition of new data to data structure
DELETION- Removal of data element from data structure
SEARCHING - Finding specific data element in data structure
TRAVERSAL - Processing all data elements one by one
SORTING - Arranging data elements in ascending or descending order
MERGING - Combining elements of two similar data structure to form a new data structure.
STACK
A stack is a collection of data items that can be accessed at only one end, called top.
Items can be inserted and deleted in a stack only at the top. The last item inserted in a stack is the first one
to be deleted.
Therefore, a stack is called a Last-In-First-Out (LIFO) data structure. 2 mains operations on Stack is PUSH & POP
PUSH means inserting new item at top and POP means deleting item from top.
OTHER STACK TERM
Peek : getting the most recent value of stack i.e value at TOP
OverFlow : a situation when we are Pushing item in Stack that is full.
Underflow : a situation when we are Popping item from empty stack