Datastructures

1.1)definition and importance of linear datastructures:

Alinear datastructure isaway tostore datain asequential order,with each
element connected tothe next and previouselements
Linear datastructuresare easy tounderstand and implement
Importance:
Linear datastructuresare the building blocksfor more complexalgorithms
and structures
They are used in many applicationsfromsimple datastorage tocomplex
problemsolving
Typesof Linear DataStructure
There are four typesof linear datastructure:
1. Array.
2. Linked list.
3. Stack.
4. Queue.

1.2)Abstract DataTypes

In thisarticle, we will learn about Abstract DataTypes(ADTs). But before

understanding what an ADT is, let usconsider different built-in datatypes
provided by programming languages. Datatypessuch asint, float, double, and
 long are built-in typesthat allowustoperformbasic operationslike addition,
subtraction, division, and multiplication. However, there are scenarioswhere we
need customoperationsfor different datatypes. These operationsare defined
based on specific requirementsand are tailored asneeded. Toaddresssuch
needs, we can create datastructuresalong with their operations, which are
known asAbstract DataTypes(ADTs).
Abstract DataType (ADT)
Datatypessuch asint,float,double,and long are built in typestoperformbasic operations
like addition,substraction,multiplication and division
An Abstract DataType (ADT)isaconceptual model that definesaset of operationsand
behavioursfor adatatype, without specifying howthese operationsare implemented or
howdataisorganized in memory.

For example, we use primitive valueslike int, float, and char with the understanding that
these datatypescan operate and be performed on without any knowledge of their
implementation details. ADTsoperate similarly by defining what operationsare possible
without detailing their implementation.
Defining ADTs: Examples
Now, let’sunderstand three common ADT’s: List ADT, StackADT, and Queue ADT.
1. List ADT
 Viesof list
The List ADT need tostore the required datain the sequence and should have the
following operations:
get(): Return an element fromthe list at any given position.
insert(): Insert an element at any position in the list.
remove(): Remove the first occurrence of any element fromanon-empty list.
removeAt(): Remove the element at aspecified location fromanon-empty list.
replace(): Replace an element at any position with another element.
size(): Return the number of elementsin the list.
isEmpty(): Return true if the list isempty; otherwise, return false.
isFull(): Return true if the list isfull; otherwise, return false.
2. StackADT

Viewof stack
In StackADT, the order of insertion and deletion should be according tothe FILO or LIFO
Principle. Elementsare inserted and removed fromthe same end, called the top of the
stack. It should alsosupport the following operations:
push(): Insert an element at one end of the stackcalled the top.
pop(): Remove and return the element at the top of the stack, if it isnot empty.
peek(): Return the element at the top of the stackwithout removing it, if the stack
isnot empty.
size(): Return the number of elementsin the stack.
isEmpty(): Return true if the stackisempty; otherwise, return false.
isFull(): Return true if the stackisfull; otherwise, return false.
3. Queue ADT

Viewof Queue
The Queue ADT followsadesign similar tothe StackADT, but the order of insertion and
deletion changestoFIFO. Elementsare inserted at one end (called the rear)and removed
fromthe other end (called the front). It should support the following operations:
enqueue(): Insert an element at the end of the queue.
dequeue(): Remove and return the first element of the queue, if the queue isnot
empty.
peek(): Return the element of the queue without removing it, if the queue isnot
empty.
size(): Return the number of elementsin the queue.
isEmpty(): Return true if the queue isempty; otherwise, return false.
1.3)overviewof time and space complexity analysisfor linear datastructures
Time and space complexity analysisfor linear datastructuresmeasureshowmuch
time and memory an algorithmtakestorun.itsimportant for designing software,
building web-sitesand analyzing large datasets
Time complexity
The amount of time it takesan algorithmtorun
The number of operationslike comparisions,required tocomplete the algorithm
The worst-case time complexity isthe maximumtime it takesfor any input
 The average-case time complexity isthe average time it takesfor an input
The best-case time complexity isthe minimumtime it takesfor an input
Space complexity
The amount of memory an algorithmuses
The fixed amount of space required by the algorithm
The variable amount of space required by the algorithmwhich dependson the
input size
Calculating time and space complexity
Identify the basic operation in the algorithm
Count howmany timesthe basic operation isperformed
Expressthe count asafunction of the input size
Simplify the expression and identify the dominant term
Expressthe time complexity using big onotation
Example: Linear search algorithm
The time complexity iso(n).where n isthe number of elementsin the array
The space complexity iso(1).which meansit usesaconstant amount of extraspace
1.4)Searching techniques:Linear and binary search
Linear Search Algorithm

Given an array, arr of n integers, and an integer element x, find whether element x is
present in the array. Return the indexof the first occurrence of x in the array, or -1if it
doesn’t exist.
Input: arr[] =[1, 2, 3, 4], x=3
Output: 2
Input: arr[] =[10, 8, 30], x=6
Output: -1
Explanation: The element tobe searched is6 and itsnot present, sowe return -1.

In Linear Search, we iterate over all the elementsof the array and checkif it the current
element isequal tothe target element. If we find any element tobe equal tothe target
element, then return the indexof the current element. Otherwise, if noelement isequal to
the target element, then return -1asthe element isnot found. Linear search isalsoknown
as sequential search.
For example: Consider the array arr[] ={10, 50, 30, 70, 80, 20, 90, 40} and key =30

Binary Search Algorithm– Iterative and Recursive Implementation

Binary Search isahighly efficient algorithmused tofind an element in asorted array or
list. Unlike linear search, which checkseach element sequentially, binary search worksby
repeatedly dividing the search interval in half, which makesit much faster than linear
search, especially for large datasets.
HowBinary Search Works:
1. Initial Setup: Binary search beginsby looking at the middle element of the sorted
array.
2. Comparison:
oIf the middle element matchesthe target value, the search iscomplete.
oIf the middle element isgreater than the target, the target must be in the left
half of the array (since the array issorted). So, the search continuesin the
left half.
oIf the middle element islessthan the target, the target must be in the right
half of the array, and the search continuesthere.
3. Repeat: Thisprocessrepeats, halving the search range each time, until the
element isfound or the search range isempty (indicating the element isnot in the
array).
Binary Search Algorithm
1. Start with the whole array.
2. Calculate the middle index: mid =(low+high)//2
3. Compare the middle element with the target:
oIf arr[mid] ==target, return the index.
oIf arr[mid] >target, repeat the search in the left half (high =mid - 1).
oIf arr[mid] <target, repeat the search in the right half (low=mid +1).
4. Repeat the processuntil the element isfound or the search range becomesinvalid
(low>high).
Example:
Given asorted array: [2, 5, 8, 12, 15, 19, 25, 32, 37, 40] and the target element 15.
1. Initial Range: low=0, high =9 (the indicesof the array).
omid =(0 +9)//2=4, soarr[mid] =15.
 oarr[mid] ==15, sowe return mid =4.
Time and Space Complexity:
1. Time Complexity:
oBest case: O(1)O(1)O(1)— The target isfound in the first comparison (if it'sthe
middle element).
oAverage case: O(logn)O(\log n)O(logn)— With each iteration, the search space
ishalved, sothe time complexity growslogarithmically with the size of the
array.
oWorst case: O(logn)O(\log n)O(logn)— The algorithmmay need tomake
logn\log nlogn comparisonstoexhaust the search space.
2. Space Complexity:
oSpace Complexity: O(1)O(1)O(1)— Binary search operatesin constant space, as
it only requiresafewvariablestotrackthe low, high, and mid indices.
Requirementsfor Binary Search:
Sorted Array/List: The array must be sorted before applying binary search. If the
array isnot sorted, youwould need tosort it first, which would take O(nlogn)O(n \log
n)O(nlogn)time.
Efficient Search Space Reduction: Binary search reducesthe search space by half
each time, which iswhy it ismuch more efficient than linear search for large
datasets.
Advantages:
Efficient for Large Datasets: With atime complexity of O(logn)O(\log n)O(logn),
binary search isvery efficient compared tolinear search, especially for large
datasets.
Constant Space: It usesO(1)O(1)O(1)space, making it very memory-efficient.
Disadvantages:
Sorted DataRequirement: The array or list must be sorted beforehand.
Not Efficient for Small Datasets: For small datasets, binary search may not be worth
the overhead compared tosimpler algorithmslike linear search.

1.5)Sorting techniques: Bubble Sort, Selection Sort, Insertion Sort:

Bubble Sort Algorithm
Bubble Sort isasimple comparison-based sorting algorithmin computer science. It is
named "bubble sort" because the smaller elements"bubble" tothe top (beginning of the
array)with each passthrough the list.
HowBubble Sort Works:
1. Iterate through the list: Starting at the first element, compare the current element
with the next element.
2. Swap if necessary: If the current element isgreater than the next one (for
ascending order), swap the twoelements.
3. Repeat: Continue thisprocessfor the entire list. After each pass, the largest
element "bubbles" tothe correct position at the end of the list.
4. Optimization: If during apass, noswapsare made, the list isalready sorted, and
the algorithmcan terminate early.
Example:
Let'ssort an array: [5, 3, 8, 4, 2] in ascending order.
1. First Pass:
oCompare 5and 3, swap [3, 5, 8, 4, 2]
oCompare 5and 8, noswap [3, 5, 8, 4, 2]
oCompare 8 and 4, swap [3, 5, 4, 8, 2]
oCompare 8 and 2, swap [3, 5, 4, 2, 8]
oAfter the first pass, the largest element (8)isin itscorrect position at the end
of the list.
2. Second Pass:
oCompare 3and 5, noswap [3, 5, 4, 2, 8]
oCompare 5and 4, swap [3, 4, 5, 2, 8]
oCompare 5and 2, swap [3, 4, 2, 5, 8]
oAfter the second pass, the second-largest element (5)isin itscorrect position.
3. Third Pass:
oCompare 3and 4, noswap [3, 4, 2, 5, 8]
oCompare 4 and 2, swap [3, 2, 4, 5, 8]
oAfter the third pass, the third-largest element (4)isin itscorrect position.
4. Fourth Pass:
oCompare 3and 2, swap [2, 3, 4, 5, 8]
 oThe list isnowsorted.
Time Complexity:
Best case (already sorted array): O(n)O(n)O(n)— when the algorithmterminates
early due tonoswaps.
Average case: O(n2)O(n^2)O(n2)— when the array isunsorted.
Worst case: O(n2)O(n^2)O(n2)— when the array issorted in reverse order.
Space Complexity:
Space Complexity: O(1)O(1)O(1)— Bubble Sort isan in-place sorting algorithm,
meaning it doesn’t require additional storage proportional tothe input size.
Advantages:
Simple tounderstand and implement.
In-place sorting with O(1)O(1)O(1)extraspace.
Disadvantages:
Inefficient for large datasetsdue toitsO(n2)O(n^2)O(n2)time complexity.
Not suitable for large-scale sorting when compared toalgorithmslike Merge Sort
or QuickSort.
Selection Sort isasimple and intuitive sorting algorithm. It repeatedly selectsthe smallest
(or largest)element fromthe unsorted portion of the array and swapsit with the element
at the beginning of the unsorted portion. Thisprocessisrepeated until the entire array is
sorted.
HowSelection Sort Works:
1. Start with the first element of the list.
2. Find the smallest element in the unsorted part of the list (fromthe current
element tothe last element).
3. Swap the smallest element with the first unsorted element.
4. Move the boundary of the unsorted portion by one position forward (i.e., move the
left pointer tothe next element).
5. Repeat thisprocessuntil the entire array issorted.
Example:
Let'swalkthrough Selection Sort on the following array:
[64, 25, 12, 22, 11]
Step-by-step Process:
First Pass:
The initial array is[64, 25, 12, 22, 11].
We need tofind the smallest element fromthe entire array.
oCompare 64 with 25, 25issmaller.
oCompare 25with 12, 12 issmaller.
 oCompare 12 with 22, 12 isstill smaller.
oCompare 12 with 11, 11issmaller.
oThe smallest element in thispassis11.
Swap 11with 64 (the first element of the array).
The array nowbecomes:

[11, 25, 12, 22, 64]

Second Pass:
Now, we focuson the unsorted portion of the array: [25, 12, 22, 64].
Find the smallest element in thissubarray:
oCompare 25with 12, 12 issmaller.
oCompare 12 with 22, 12 issmaller.
oCompare 12 with 64, 12 isstill smaller.
oThe smallest element is12.
Swap 12 with 25(the first element in thisunsorted subarray).
The array nowbecomes:
[11, 12, 25, 22, 64]
Third Pass:
Now, focuson the subarray[25, 22, 64].
Find the smallest element in thissubarray:
oCompare 25with 22, 22issmaller.
oCompare 22with 64, 22issmaller.
oThe smallest element is22.
Swap 22with 25.
The array nowbecomes:
[11, 12, 22, 25, 64]
Fourth Pass:
Focuson the subarray [25, 64].
Find the smallest element in thissubarray:
o25issmaller than 64.
Noneed toswap since 25isalready in the correct position.
The array remains:
[11, 12, 22, 25, 64]
Fifth Pass:
 The remaining subarray isjust [64], which isalready sorted.
Final Sorted Array:
After completing all passes, the array issorted:
[11, 12, 22, 25, 64]
Time and Space Complexity:
1. Time Complexity:
oBest, Average, and Worst Case: O(n2)O(n^2)O(n2)— Selection Sort always
comparesevery element with every other element in the unsorted portion,
resulting in aquadratic number of comparisons.
Best Case: Even if the array isalready sorted, Selection Sort still
performsO(n2)O(n^2)O(n2)comparisons.
Worst Case: The worst case happenswhen the array issorted in
reverse order, which still requiresO(n2)O(n^2)O(n2)comparisons.
2. Space Complexity:
oSpace Complexity: O(1)O(1)O(1)— Selection Sort isan in-place sorting
algorithm, meaning it requiresonly aconstant amount of additional space
for the temporary variable used in swapping.
Advantagesof Selection Sort:
Simplicity: Very easy tounderstand and implement.
In-place sorting: It sortsthe array without using additional memory (i.e., no
auxiliary array).
Not affected by the initial order of elements: Unlike algorithmslike Bubble Sort or
Insertion Sort, which can performbetter if the array ispartially sorted, Selection
Sort alwaysperformsthe same number of comparisons.
Disadvantagesof Selection Sort:
Inefficient for large datasets: Because of itsO(n2)O(n^2)O(n2)time complexity, it is
very slowfor large arrays, especially when compared tomore advanced algorithms
like Merge Sort or QuickSort, which have O(nlogn)O(n \log n)O(nlogn)time
complexity.
Not adaptive: It doesn't improve even when the array ispartially sorted. Thismakes
it inefficient in many practical scenarios.
Insertion Sort in DataStructureswith Example
Insertion Sort isasimple comparison-based sorting algorithmthat buildsthe final sorted
array one element at atime. It ismuch like sorting playing cardsin your hands, where you
take one card at atime and place it in the correct position relative tothe cardsalready
sorted.
HowInsertion Sort Works:
1. Start with the second element (since asingle element istrivially sorted).
2. Compare the current element with the elementsin the sorted portion of the array
(toitsleft).
 3. Shift all elementsthat are greater than the current element one position tothe
right tomake space for the current element.
4. Insert the current element intoitscorrect position.
5. Repeat thisprocessfor all the elementsin the array.
Example:
Consider the array: [5, 2, 9, 1, 5, 6]
Step-by-step Process:
Initial Array:
[5, 2, 9, 1, 5, 6]
We will start with the second element (index1), because the first element istrivially
considered sorted.

First Pass(i =1):

Current element: 2
Compare 2with 5(the element toitsleft).
o2<5, soshift 5tothe right.
oThe array nowlookslike: [5, 5, 9, 1, 5, 6].
Insert 2intoitscorrect position: Place 2at the start.
The array becomes: [2, 5, 9, 1, 5, 6].

Second Pass(i =2):

Current element: 9
Compare 9 with 5(the element toitsleft).
o9 >5, noshift needed.
Insert 9: It'salready in the correct position.
The array remains: [2, 5, 9, 1, 5, 6].

Third Pass(i =3):

Current element: 1
Compare 1with 9 (shift 9 right).
oThe array becomes: [2, 5, 9, 9, 5, 6].
Compare 1with 5(shift 5right).
oThe array becomes: [2, 5, 5, 9, 5, 6].
Compare 1with 2(shift 2right).
 oThe array becomes: [2, 2, 5, 9, 5, 6].
Insert 1at the start.
The array becomes: [1, 2, 5, 9, 5, 6].

Fourth Pass(i =4):

Current element: 5
Compare 5with 9 (shift 9 right).
oThe array becomes: [1, 2, 5, 9, 9, 6].
Compare 5with 5(noshift needed).
Insert 5after the first 5.
The array becomes: [1, 2, 5, 5, 9, 6].

Fifth Pass(i =5):

Current element: 6
Compare 6 with 9 (shift 9 right).
oThe array becomes: [1, 2, 5, 5, 9, 9].
Compare 6 with 5(noshift needed).
Insert 6 after the second 5.
The array becomes: [1, 2, 5, 5, 6, 9].

Final Sorted Array:

After completing all passes, the array issorted:
[1, 2, 5, 5, 6, 9]
Insertion Sort AlgorithmCode (in Python):
Time and Space Complexity:
1. Time Complexity:
oBest case: O(n)O(n)O(n)— Thishappenswhen the array isalready sorted. In
thiscase, only one comparison ismade for each element, and noshifting
occurs.
oWorst case: O(n2)O(n^2)O(n2)— Thisoccurswhen the array issorted in
reverse order. Each element needstobe compared and shifted tothe
beginning.
oAverage case: O(n2)O(n^2)O(n2)— On average, the algorithmwill need to
performabout n2/2n^2/2n2/2comparisonsand shifts.
2. Space Complexity:
oSpace Complexity: O(1)O(1)O(1)— Insertion sort isan in-place sorting
 algorithm, meaning it doesn't require any additional space besidesthe input
array.
Advantagesof Insertion Sort:
Simple tounderstand and implement: It isone of the easiest sorting algorithmsto
understand and code.
Efficient for small datasets: For small arrays, the overhead of more advanced
algorithmsmay not be justified, and Insertion Sort can performwell.
Adaptive: It isadaptive, meaning if the array isalready partially sorted, the
algorithmwill performbetter (i.e., fewer shiftsand comparisons).
Stable: Insertion sort isstable, meaning that it maintainsthe relative order of
elementswith equal values.
Disadvantagesof Insertion Sort:
Inefficient for large datasets: Due toitsO(n2)O(n^2)O(n2)time complexity, it isnot
suitable for large arrays.
Not ideal for large-scale data: For larger datasets, more efficient algorithmslike
QuickSort, Merge Sort, or Heap Sort are typically preferred.
When toUse Insertion Sort:
Small datasets: It isefficient for small arrayswhere the overhead of more complex
algorithmsisn't necessary.
Partially sorted arrays: If the array isalready partially sorted, Insertion Sort can be
much faster than other algorithms.
Memory-constrained environments: It usesonly O(1)O(1)O(1)extraspace, soit is
useful when memory islimited.