Linear Data Structure

Lecture 2
Types of Data Structure
Types of Data Structure

The types of data structures or their kind can be broken into two:
1. Linear Data Structure
Linear data structures are organized in a particular order, and it is done so
because the elements are ordered in a particular pattern; they are simple to
implement. Nevertheless, linear data structures might not be the best choice
for sophisticated systems because of their operational complexity.
2. Nonlinear Data Structure
Nonlinear elements of data structures aren't ordered in a particular way, as
opposed to linear structures. They are arranged in a hierarchical manner in
which each element may be linked to one element. The graph and tree-based
structures divide those that are nonlinear.
What Is Linear Data Structure?

 A linear data structure is known as a data structure that allows data elements to be
arranged in a sequential or linear fashion.
 Each element is attached with its next and previous adjacent. A linear data
structure only has one level and performs linear searching in the data structure.
 We can therefore traverse all elements in a single run. Because computer memory
is linearly arranged, linear data structures are simple to implement.
 Linear data structure examples are array, linked list, stack, queue, etc.
 Types in Linear Data Structure

 The Array, Linked List, Stack, and Queue are all kinds of linear data
structure types. Let's look at each in greater detail.
 Real Life Example
 Lets suppose a person name John has 4 sisters and we need to store her eldest
sister’s age in a variable. We can write it as
int age= 20;
 But what happens if we have to store the ages of all her sisters in a list?
 For that purpose we use Array.
Array is a List of variables of similar type.
Example:
{ 1,2,3,4,5}
{‘c’, ‘f’, ‘h’ ,‘i’ }
{ ‘d’, 3, ‘f’, 4.3}
Array
 1. Array( 数组数据结构 )
 An array is a collection of items of same data type stored at contiguous memory locations.

 An Array is a type of framework that stores homogeneous parts in connected memory

locations.
 It is precisely the same kinds of objects that are saved sequentially inside an array.
 The fundamental concept behind linear arrays in the data structure is that multiple pieces
of data similar can be stored together.
 Before saving the data in an array, it is essential that the size of an array need to be
established.
 Continue…

 Every aspect of the array can be accessed or modified, and the data is stored in an
index to identify their places of their own.
 The concept of an array can be explained through an easy example of saving the
marks for all the students in a class if you assume that there are twenty
pupils.
 The size of your array needs to be identified as 20. The marks of all pupils could
also be saved in the array created without the need to create separate variables for
markings for every pupil.
 A simple traversal of the array will allow access to the parts.
 Why Do You Need an Array in Data Structures?
( 为什么数据结构中需要数组？ )

 Let's suppose a class consists of ten students, and the class has to
publish their results. If you had declared all ten variables
individually, it would be challenging to manipulate and maintain the
data.
 If more students were to join, it would become more difficult to
declare all the variables and keep track of it. To overcome this
problem, arrays came into the picture.
Basic terminologies of array

 Array Index: In an array, elements are identified by their indexes. Array index
starts from 0.
 Array element: Elements are items stored in an array and can be accessed by
their index.
 Array Length: The length of an array is determined by the number of elements it
can contain.
Characteristics of Array Data Structure:

 Homogeneous Elements: All elements within an array must be of the same data type.
 Contiguous Memory Allocation: In most programming languages, elements in an array
are stored in contiguous (adjacent) memory locations.
 Zero-Based Indexing: In many programming languages, arrays use zero-based indexing,
which means that the first element is accessed with an index of 0, the second with an index
of 1, and so on.
 Random Access: Arrays provide constant-time (O(1)) access to elements. This means that
regardless of the size of the array, it takes the same amount of time to access any element
based on its index.
Types of arrays( 数组类型 )

 One-Dimensional Array: This is the simplest form of an array,

which consists of a single row of elements, all of the same data type.
Elements in a 1D array are accessed using a single index.
 Continue…
 Two-Dimensional Array: A two-dimensional array, often referred
to as a matrix or 2D array, is an array of arrays. It consists of rows
and columns, forming a grid-like structure. Elements in a 2D array
are accessed using two indices, one for the row and one for the
column.
 Continue…
 Multi-Dimensional Array: Arrays can have more than two
dimensions, leading to multi-dimensional arrays. These are used
when data needs to be organized in a multi-dimensional grid.
Advantages of using Arrays
( 使用数组的优点 )
 Arrays allow random access to elements. This makes
accessing elements by position faster.
 Arrays have better cache locality which makes a pretty big
difference in performance.
 Arrays represent multiple data items of the same type using a
single name.
 Arrays store multiple data of similar types with the same
name.
 Array data structures are used to implement the other data
structures like linked lists, stacks, queues, trees, graphs, etc.
 Disadvantages of Array( 数组的缺点 )
 As arrays have a fixed size, once the memory is allocated to them, it cannot be
increased or decreased, making it impossible to store extra data if required. An array
of fixed size is referred to as a static array.
 Allocating less memory than required to an array leads to loss of data.
An array is homogeneous in nature so, a single array cannot store values of different
data types.
 Arrays store data in contiguous memory locations, which makes deletion and
insertion very difficult to implement. This problem is overcome by implementing
linked lists, which allow elements to be accessed sequentially.
 C++ Array Declaration

 Arrays are typically defined with square brackets with the size of the arrays as its
argument.

 Here is the syntax for arrays:

1D Arrays: int arr[n];
Access Elements in C++ Array

 In C++, each element in an array is associated with a number. The number is

known as an array index. We can access elements of an array by using those
indices.

 Consider the array x, int x[6]

Few Things to Remember:

 The array indices start with 0. Meaning x[0] is the first element stored at index 0.
 If the size of an array is n, the last element is stored at index n-1. In the above example,
x[5] is the last element.
 Elements of an array have consecutive addresses. For example, suppose the starting
address of x[0] is 2120.
 Then, the address of the next element x[1] will be 2124, the address of x[2] will be
2128 and so on…
 Here, the size of each element is increased by 4. This is because the size of int is 4
bytes.
 C++ Array Initialization
 In C++, it's possible to initialize an array during declaration. For example,

 Another method to initialize array during declaration:

 Here, we have not mentioned the size of the array. In such cases, the compiler automatically
computes the size.
C++ Array With Empty Members
 In C++, if an array has a size n, we can store upto n number of elements in the
array. However, what will happen if we store less than n number of elements.
 For example,

 Here, the array x has the size of 6 . However, we have initialized it with only 3
elements. In such cases, the compiler assigns random values to the remaining
places. Oftentimes, this random value is simply 0.
How many ways to declare an Array?

 The above declaration is static or compile-time memory allocation, which means that the
array element’s memory is allocated when a program is compiled.
 Here only a fixed size (i.e. the size that is mentioned in square brackets []) of memory
will be allocated for storage, but don’t you think it will not be the same situation as we
know the size of the array every time, there might be a case where we don’t know the size
of the array.
 If we declare a larger size and store a lesser number of elements will result in a wastage of
memory or either be a case where we declare a lesser size then we won’t get enough
memory to store the rest of the elements.
 In such cases, static memory allocation is not preferred.
Solution is dynamic array?

 The answer is Yes.

 It is possible to allocate memory dynamically.
 So, dynamic memory allocation is the process of assigning the memory space
during the execution time or the run time.

int *array = new int[5];

Types of Array operations( 数组运算的类型 ):

 Traversal: Traverse through the elements of an array.

 Insertion: Inserting a new element in an array.
 Deletion: Deleting element from the array.
 Searching: Search for an element in the array.
 Sorting: Maintaining the order of elements in the array.
1. Traversal in Array( 数组数据结构中的遍历 )

 Traversal operation in array or simply traversing an array means,

Accessing or printing each element of an array exactly once
so that the data items (values) of the array can be checked or used as
part of some other operation or process (This accessing and
processing is sometimes called “visiting” the array).

 Note: Accessing or printing of elements always takes place one by one.

Algorithm for Traversing an
Array:

Variables used:
Traversal in Array(Continue…)

We will learn about the two ways to traverse the elements of an array in C++:
 Using for loop.
 Using While loop
Using for loop.
Using While loop
 2. Insertion in Array( 数组数据结构中的插入 )
 How to Insert an element at a specific position in an Array in C++
Given an array arr of size n, we will learn how to insert an element x in this array arr at a
specific position pos.
Approach: Here’s how to do it.

 First get the element to be inserted, say x

 Then get the position at which this element is to be inserted, say pos
 Then shift the array elements from this position to one position forward, and do
this for all the other elements next to pos.
 Insert the element x now at the position pos, as this is now empty.
 3.Deletion in Array( 数组数据结构中的删除 )

 We will learn how to delete an element from an array in C++ and

get the code for doing so. The program is created in the following
ways:
 To delete an element from an array in C++ programming,
 You have to ask the user to enter the array's 10 elements first.
 Then ask for the element that has to be deleted.
 Now search for that number or element and delete it if found.
 Otherwise, print a message such as "Element not found."
Program
 Continue…
 Now supply any 10 numbers, say 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10, as 10 array
elements. Enter the number or element, say 3, that must be deleted from the list
after entering 10 elements for the array arr[]. Here is the final snapshot of the
sample run:
Using a function, delete an element from an array
 We will use user-defined function delElem().
 The function delElem() takes three arguments.
 The first argument is array, the second is size, and the third is the element that
has to be deleted.

4. Searching in Array( 在数组数据结构中搜索 )
We’ll be using an algorithm called Linear Search for this purpose.
 A linear search, also known as a sequential search, is a method of finding an element within an
array.
 It checks each element of the array sequentially until a match is found for a particular element
or the whole array has been searched.
Algorithm:
 Take the size of the array, the element that needs to be searched, and elements of the array as
input from the user.
 Before searching store the index as -1 in variable names “ans”.
 Loop through the elements of the array.
 If a match is found, then we break the loop and update the value of the “ans” variable with the
index of the element.
 If no match is found, then display output accordingly.
Program:
 5. Sorting in Arrays( 数组排序数据结构 )
 Sorting an array in C++ programming means that arranging its elements in a particular
sequence, such as numerical or alphabetical order.
 This process is a crucial task in programming that finds its use in various applications,
including data analysis, searching, and data processing.
 Essentially, sorting an array permits programmers to manage large quantities of information
more accurately.
 This makes it easier to search for particular data, perform calculations, and access data.
 In C++, sorting may be classified into two categories, i.e., internal sorting and external
sorting.
Types of Sorting
Example
Find sum of integers in the array {2, 4, 6, 8}

 In the following example, we take an integer array initialized with some elements,
and find the sum of the elements of this array using a For Loop.
Assignment for Class Activity( 课堂活动作业 )

Write a C++ Program to find the average of integers in

the array {2, 4, 6, 8}
Continue…
C++ Find Largest Number in Integer Array
 Continue…
 In the following example, we take an integer array initialized with some elements,
and find the largest number of the elements of this array.
Example : Displaying Array
Elements
Output of the program:
 Example 2: Take Inputs from User and Store Them in an
Array

 Once again, we have

used a for loop to iterate from
i=0 to i=4. . In each iteration, we
took an input from the user and
stored it in numbers[i].
 Then, we used another for loop
to print all the array elements.
Output of the program:
 Assignment # 2:

 Example 3: Display Sum and Average of Array Elements Using

for Loop with explanation.

 Deadline: 6th November 2023

C++ Array Out of Bounds

 If we declare an array of size 10, then the array will contain

elements from index 0 to 9.
 However, if we try to access the element at index 10 or more
than 10, it will result in Undefined Behavior.
What is Time Complexity And Why Is It
Essential?

 Time complexity is defined as the amount of time taken by an algorithm to run, as

a function of the length of the input.
 It measures the time taken to execute each statement of code in an algorithm.
 It is not going to examine the total execution time of an algorithm. Rather, it is
going to give information about the variation (increase or decrease) in execution
time when the number of operations (increase or decrease) in an algorithm.
 Yes, as the definition says, the amount of time taken is a function of the length of
input only.
 Continue…
 Space and Time define any physical object in the Universe. Similarly, Space and Time
complexity can define the effectiveness of an algorithm.
 While we know there is more than one way to solve the problem in programming,
knowing how the algorithm works efficiently can add value to the way we do
programming.
 To find the effectiveness of the program/algorithm, knowing how to evaluate them using
Space and Time complexity can make the program behave in required optimal
conditions, and by doing so, it makes us efficient programmers.
 While we reserve the space to understand Space complexity for the future, let us focus on
Time complexity now.
 Time is Money! we will discover a gentle introduction to the Time complexity of an
algorithm, and how to evaluate a program based on Time complexity.
56
Algorithm Definition

A finite set of statements that guarantees an optimal

solution in finite interval of time
57 Good Algorithms?

 Run in less time

 Consume less memory

But computational resources (time complexity) is usually more

important
58
Measuring Efficiency

 The efficiency of an algorithm is a measure of the amount of resources consumed

in solving a problem of size n.
 The resource we are most interested in is time
 We can use the same techniques to analyze the consumption of other
resources, such as memory space.

 It would seem that the most obvious way to measure the efficiency of an
algorithm is to run it and measure how much processor time is needed

 Is it correct ?
59
Factors
 Hardware

 Operating System

 Compiler

 Size of input

 Nature of Input

 Algorithm

Which should be improved?

60 RUNNING TIME OF AN ALGORITHM

 Depends upon
 Input Size
 Nature of Input

 Generally time grows with size of input, so running time of an algorithm

is usually measured as function of input size.

 Running time is measured in terms of number of steps/primitive

operations performed

 Independent from machine, OS

61 Finding running time of an
Algorithm / Analyzing an Algorithm

 Running time is measured by number of steps/primitive operations performed

 Steps means elementary operation like

 ,+, *,<, =, A[i] etc

 We will measure number of steps taken in term of size of input

62
Simple Example (1)

// Input: int A[N], array of N integers

// Output: Sum of all numbers in array A

int Sum(int A[], int N)

{
int s=0;
for (int i=0; i< N; i++)
s = s + A[i];
return s;
}

How should we analyse this?

63 Simple Example (2)
// Input: int A[N], array of N integers
// Output: Sum of all numbers in array A

int Sum(int A[], int N){

int s=0; 1
for (int i=0; i< N; i++)
2 3 4
s = s + A[i];
5 6 7 1,2,8: Once
return s; 3,4,5,6,7: Once per each iteration
}
8 of for loop, N iteration
Total: 5N + 3
The complexity function of the
algorithm is : f(N) = 5N +3
64 Simple Example (3) Growth of 5n+3

Estimated running time for different values of N:

N = 10 => 53 steps
N = 100 => 503 steps
N = 1,000 => 5003 steps
N = 1,000,000 => 5,000,003 steps

As N grows, the number of steps grow in linear proportion to N for this

function “Sum”
 What Dominates in Previous
65
Example?
What about the +3 and 5 in 5N+3?
 As N gets large, the +3 becomes insignificant
 5 is inaccurate, as different operations require varying amounts of time and
also does not have any significant importance

What is fundamental is that the time is linear in N.

Asymptotic Complexity: As N gets large, concentrate on the

highest order term:
 Drop lower order terms such as +3
 Drop the constant coefficient of the highest order term i.e. N
66
Asymptotic Complexity

 The 5N+3 time bound is said to "grow asymptotically" like N

 This gives us an approximation of the complexity of the

algorithm

 Ignores lots of (machine dependent) details, concentrate on

the bigger picture
67 COMPARING FUNCTIONS:
ASYMPTOTIC NOTATION

 Big Oh Notation: Upper bound (Worst Case)

 Omega Notation: Lower bound ( Optimum Case)

 Theta Notation: Tighter bound ( Average Case)

68 Big Oh Notation [1]
 If f(N) and g(N) are two complexity functions, we say

f(N) = O(g(N))

(read "f(N) is order g(N)", or "f(N) is big-O of g(N)")

 if there are constants c and N0 such that for N > N0,
f(N) ≤ c * g(N)
for all sufficiently large N.
Big Oh Notation [2]

69
70 O(f(n))
 Example (2): Comparing Functions

 Which function is better? 4000

10 n2 Vs n3 3500

3000

2500

10 n^2
2000
n^3

1500

1000

500

0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

71
72 Comparing Functions

 As inputs get larger, any algorithm of a smaller order will be more

efficient than an algorithm of a larger order

0.05 N2 = O(N2)
Time (steps)

3N = O(N)

Input (size)
N = 60
73 Big Omega Notation

 If we wanted to say “running time is at least…” we use Ω

 Big Omega notation, Ω, is used to express the lower bounds on a function.

 If f(n) and g(n) are two complexity functions then we can say:

f(n) is Ω(g(n)) if there exist positive numbers c and n0 such that 0<=f(n)>=cΩ (n) for all n>=n0
74 Big Theta Notation

 If we wish to express tight bounds we use the theta notation, Θ

 f(n) = Θ(g(n)) means that f(n) = O(g(n)) and f(n) = Ω(g(n))

75 What does this all mean?

 If f(n) = Θ(g(n)) we say that f(n) and g(n) grow at the same rate,
asymptotically

 If f(n) = O(g(n)) and f(n) ≠ Ω(g(n)), then we say that f(n) is

asymptotically slower growing than g(n).

 If f(n) = Ω(g(n)) and f(n) ≠ O(g(n)), then we say that f(n) is

asymptotically faster growing than g(n).
 Which Notation do we use?
76

 To express the efficiency of our algorithms which of the three

notations should we use?

 As computer scientist we generally like to express our algorithms

as big O since we would like to know the upper bounds of our
algorithms.

Why?

 If we know the worse case then we can aim to improve it and/or

avoid it.
 Performance Classification
f(n) Classification
1 Constant: run time is fixed, and does not depend upon n. Most instructions are executed once, or
only a few times, regardless of the amount of information being processed

log n Logarithmic: when n increases, so does run time, but much slower. Common in programs which solve
large problems by transforming them into smaller problems. Exp : binary Search

n Linear: run time varies directly with n. Typically, a small amount of processing is done on each
element. Exp: Linear Search

n log n When n doubles, run time slightly more than doubles. Common in programs which break a problem
down into smaller sub-problems, solves them independently, then combines solutions. Exp: Merge

n2 Quadratic: when n doubles, runtime increases fourfold. Practical only for small problems; typically
the program processes all pairs of input (e.g. in a double nested loop). Exp: Insertion Search

n3 Cubic: when n doubles, runtime increases eightfold. Exp: Matrix

2n Exponential: when n doubles, run time squares. This is often the result of a natural, “brute force”
solution. Exp: Brute Force.
Note: logn, n, nlogn, n2>> less Input>>Polynomial
n3, 2n>>high input>> non polynomial
77
78 Complexity Classes

Time (steps)
 Size does matter[2]
79

 Suppose a program has run time O(n!) and the run time for
n = 10 is 1 second

For n = 12, the run time is 2 minutes

For n = 14, the run time is 6 hours

For n = 16, the run time is 2 months

For n = 18, the run time is 50 years

For n = 20, the run time is 200 centuries

80
Standard Analysis Techniques

1. Constant time statements

2. Analyzing Loops
3. Analyzing Sequence of Statements
4. Analyzing Conditional Statements
 1. Constant time statements
81

Simplest case: O(1) time statements

 Assignment statements of simple data types

int x = y;

 Arithmetic operations:
x = 5 * y + 4 - z;

 Array referencing:
A[j] = 5;

 Array assignment:
 j, A[j] = 5;

 Most conditional tests:

if (x < 12) ...
82 2. Analyzing Loops[1]
 Any loop has two parts:
 How many iterations are performed?
 How many steps per iteration?

int sum = 0,j;

for (j=0; j < N; j++)
sum = sum +j;

 Loop executes N times (0..N-1)

 4= O(1) steps per iteration

 Total time is N * O(1) = O(N*1) = O(N)

83
Analyzing Loops[2]

 What about this for loop?

int sum =0, j;
for (j=0; j < 100; j++)
sum = sum +j;

 Loop executes 100 times

 4 = O(1) steps per iteration

 Total time is 100 * O(1) = O(100 * 1) = O(100) = O(1)

 Analyzing Loops – Linear Loops
84
 Example (have a look at this code segment):

 Efficiency is proportional to the number of iterations.

 Asymptotically, efficiency is : O(n)
85 3. Sequence of Statements

 For a sequence of statements, compute their complexity functions

individually and add them up

 Total cost is O(n2) + O(n) +O(1) = O(n2)

86 4. Conditional Statements
 What about conditional statements such as

if (condition)
statement1;
else
statement2;

 where statement1 runs in O(n) time and statement2 runs in O(n 2) time?

 We use "worst case" complexity: among all inputs of size n, what is the
maximum running time?

 The analysis for the example above is O(n2)

87
Summary

 Algorithms can be classified according to their complexity =>

O-Notation
 only relevant for large input sizes

 "Measurements" are machine independent

 worst-, average-, best-case analysis
Quiz No 1 2nd November

 Write a C++ Program for Insertion

in Array
Or
Write a C++ Program for Deletion in
Array
Quiz No.1

 Programs
1. Insertion in Array
2. Deletion in Array

Date: 2nd November

Quiz No. 2

 From all the slides of Lecture 1 ppt.

Date: 9th November
92