Introduction to Data Structures

Introduction to Data Structure

• A data structure is a representation of the logical relationship existing between individual elements of data.
• Data structures organize data items, considering both the elements stored and their relationships.
• Data structure affects the design of structural and functional program aspects.
• Program = Algorithm + Data Structure
• An algorithm is a step-by-step procedure to solve a particular function.
• Algorithm refers to a set of instructions written to carry out certain tasks, where the data structure organizes the data with logical relationships retained.
• A suitable data structure must be selected to develop a program from an algorithm

Classification of Data Structures

• Data structures are divided into two categories:
  • Primitive Data Structures
  • Non-Primitive Data Structures

Primitive Data Structure

• These are basic structures directly operated upon by machine instructions.
• Representation varies on different computers
• Includes Integer, Floating-point number, Character constants, string constants, pointers, etc.

Non-Primitive Data Structure

• These are sophisticated data structures derived from primitive structures.
• Emphasis is on structuring a group of homogeneous or heterogeneous data items.
• Examples: Lists, Stacks, Queues, Trees, and Graphs.
• An efficient data structure design must allow for operations to be performed

Common operations on data structures include the following:

• Create
• Selection
• Updating
• Searching
• Sorting
• Merging
• Destroy or Delete

Differences Between Data Structures

• Primitive data structures are basic and usually built into the language (e.g., integer, float).
• Non-primitive data structures are built from primitive structures linked in meaningful ways (e.g., linked lists, binary search trees, graphs).

Arrays

• An array is a finite set of homogeneous or same-type data items (e.g., all integers, all float-point numbers, or all characters).
• Declaration example: int arr[10]
  • int specifies the data type of the elements the array stores.
  • arr is the array name
  • The number inside the square brackets represents the number of elements the array can store; also called the array's size or length.
• Individual array elements are accessed by specifying the array name, followed by the index or subscript inside square brackets.
• The first array element has an index of zero [0]
• The last array element will be specified as arr[9].
• Array elements are stored in consecutive memory locations.
• The number of elements that can be stored in an array, is given by (Upperbound-lowerbound)+1
• The example array contains: (9-0) + 1 = 10 elements, where 0 is the lower bound and 9 isthe upper bound.
• One-dimensional arrays are read or written using one loop
• Two-dimensional arrays are read or written using two loops
• Arrays of N dimensions require N loops for reading or writing.

Common array operations:

• Creation of an array
• Traversing an array
• Inserting a new element
• Deleting a required element
• Modifying an element
• Merging arrays

Lists

• A List (Linear linked list) is a collection of a variable number of data items
• Lists are used as flexible storage containers whose size may differ on creation
• Lists are examples of non-primitive data structures.
• A list element must contain at least two fields: one for storing data/information, and another for storing the address of the next element.
• Pointers can be used to store the address
• An element is referred to as a node
• A list is basically a collection of node

Types of linked lists:

• Single linked list
• Doubly linked list
• Single circular linked list
• Doubly circular linked list

Stack

• A stack is an ordered collection of elements like arrays.
• Insertion and deletion of elements are done only from one end, called the top of the stack (TOP).
• Stacks are referred to as last-in, first-out (LIFO) data structures.
• Stacks are non-primitive data structures.
• When insertion or removal happens, the base remains fixed while TOP changes.
• Element insertion into a stack is called PUSH
• Element deletion from a stack is called POP.
• Stacks can be implemented using arrays (static implementation) or pointers (dynamic implementation).

Queue

• Queues are "first in, first out" (FIFO) data structures.
• New elements are added to the queue from the REAR end, and elements are always removed from the FRONT end.
• People standing in a railway reservation row are an example of a queue.
• Queues can be implemented using arrays (static implementation) or pointers (dynamic implementation).

Trees

• A tree is a finite set of data items (nodes)
• It is a non-linear data structure with items arranged/stored in a sorted sequence.
• Trees represent the hierarchical relationships between elements.
• There is a special data item at the top of the hierarchy called the Root of the tree.
• Remaining data items are partitioned into mutually exclusive subsets, each of which is itself a tree (subtree).
• Trees grow downwards in data structures
• Tree structures organize data into related branches.

Graph

• A graph is a mathematical non-linear data structure representing physical structures.
• Graphs have found applications in Geography, Chemistry, and Engineering
• A graph G(V,E) is a set of vertices V and a set of edges E.
• An edge connects a pair of vertices and may have a weight (e.g., length, cost, etc.).
• Vertices are shown as points or circles
• Edges shown as arcs or line segments.

Types of Graphs

Graph types include:

• Directed graph
• Undirected graph
• Simple graph
• Weighted graph
• Connected graph
• Non-connected graph

Algorithm

• An algorithm is an effective method or step-by-step procedure for solving a problem.
• Step-by-step procedure to solve a computational problem
• An algorithm step-by-step plan for a computational procedure that begins with an input and yields an output value in a finite number of steps in order to solve a particular problem.
• Set of steps of operations to solve a problem performing calculation, data processing, and automated reasoning tasks.
• Algorithms can be expressed within specified time and space
• Algorithm design includes creating an efficient algorithm to solve a problem efficiently using minimum time and space.
• To solve a problem, different approaches can be followed some may be time efficient and another memory efficient

Algorithm Properties

• Input: The algorithm should be given zero or more inputs.
• Output: At least one quantity is produced. For each input, the algorithm produces a value from a specific task.
• Definiteness: The instruction given is clear and unambiguous.
• Finiteness: The algorithm terminates after a finite number of steps.
• Effectiveness: The algorithm is very basic so that it can be carried out, in principle, by a person using only pencil & paper.

Algorithm vs Pseudocode vs Program

• Algorithm: A systematic logical approach that is a well-defined, step-by-step procedure that allows a computer to solve a problem.
• Pseudocode: A simpler version of programming code in plain English using short phrases to write code before implementation in a specific language.
• Program: Exact code written for a problem, following all the rules of the programming
• Algorithms are at the design phase.
• Programs are written in implementation phase.
• Pseudocode is a written form of natural language.
• Programs written as programming language.

Algorithm Specification

• Algorithm is described (Represented) in four ways.
  • Natural language like English
  • Graphic representation called flowchart
  • Pseudo-code Method
  • Programming Language, such as C, C++, JAVA etc.

Pseudo-Code Conventions:

• Comments begin with //
• Blocks are indicated inside matching braces { and }
• Identifiers begin with a letter
• Data types of variables are not explicitly declared.

Data Operators

• The Relational Operators consist of: <=, >, >=, =, !=
• Assignment of values to variables is done using the assignment statement <Variable> := <expression>;
• Compound data types can be formed with records
• The following looping statements are used
  • For
  • While
  • Repeat-until

Conditional statements include the following forms.

• If <condition> then <statement>
• If <condition> then <statement-1> Else <statement-1>
• Input and output are done using the instructions read & write.
• There is one procedure Algorithm; the heading takes the form, Algorithm Name (Parameter lists)

Algorithm creation and validation

• To create an algorithm the following design techniques can be used include:
  • Divide & Conquer
  • Greedy method
  • Dynamic Programming
  • Branch & Bound
  • Backtracking
• Once an algorithm is created, it must be validated.

Analyzing algorithms

• Analysis or performance analysis determines how much computing Time & storage algorithms require.
  • Computing time-Time complexity: Frequency or Step count method
  • Storage space - To calculate space complexity we have to use a number of inputs used in algorithms. Programs are tested for:
    • Debugging: Executing programs on sample data to determine faulty results & correct them.
    • Profiling or performance measurement is the process of executing a correct program on a data set and measuring the time & space it takes to compute the result.

Algorithm Importance

• Is used to understanding the basic idea of the problem
• Is used to find an approach to solve the problem
• Is used to improve the efficiency of existing techniques
• Is used to understand the basic principles of designing the algorithms
• Is used to compare the performance of the algorithm with respect to other techniques
• Is a precise description without implementation details
• Gives a goal & requirements to the designer
• Facilitates a good solution design
• Aids understanding of the problem flow

Array Basics

• Arrays are fundamental in computer science.
• They store collections of similar elements in contiguous memory locations.
• Arrays allow for efficient access and manipulation of data.
• A linear data structure where each element is identified by an index.
• Elements are stored in consecutive memory slots, which makes random access fast.

Array types include:

• Static Arrays: size determined at declaration
• Dynamic Arrays: Resizable during execution Arrays can store a sequence of elements of the same type with each element being identified by the order of placement
• Memory is also allocated sequentially in Arrays

Operations

• Elements can be accessed, where any element can be retrieved at constant time
• Loops are used to process each element using loops.
• Used for searching, printing values, or applying operations on each element.
• Complexity is O(n)
• Can insert elements involving shifting subsequent elements to make space. Involves
  • Determining the position for insertion
  • Shift all elements from that position one index to the right
  • Insert the new element.
• Complexity is O(n) in the worst case.
• Removing an element is similar to insertion and requires shifting elements, where
  • Identify the index of the element to remove
  • Shift all subsequent elements one index to the left
  • Update the size of the array if necessary.
• The Complexity is O(n) in the worst case.
• Elements can be modified, where indexes are used to update an element.
  • For example arr[1] = 25 replaces the second element with 25, with O(1) 9 Complexity

Searching Algorithms

Linear

• Requires each element to be checked sequentially until the target is found and has an O(n) Time Complexity

Binary

• An efficient option for sorted arrays where search interval is halved repeatedly with an O(log n) Time Complexity

Common sorting algorithms include

• Bubble Sort, Insertion Sort, Merge Sort and Quick Sort
• Simple sorts (Bubble, Insertion): O(n²) on average
• Efficient sorts (Merge, Quick): O(n log n) on average
• Contiguous Memory Allocation improves cache performance, but can lead to challenges like memory fragmentation
• Insertions and deletions (in static arrays) require shifting, which can be expensive for large arrays.
• Resizing Dynamic Arrays often involves allocating a new, larger array and copying over elements, which is an expensive operation if it happens frequently

Tuples

• A tuple is similar to a list, but with one major difference—tuples are immutable, such that it cannot be changed once created