Data Structures (18CS202) Lecture Notes

Data Structures and Algorithms

• Data Structures course objectives:
  • Demonstrate familiarity with major algorithms and data structures
  • Choose the appropriate data structure and algorithm design method for a specified application
  • Determine which algorithm or data structure to use in different scenarios
  • Improve logical ability

Algorithms

• An algorithm is a step-by-step process to solve a problem
• Properties of an algorithm:
  • Input-Output: Algorithm takes input and produces output
  • Finiteness: An algorithm must terminate in a countable number of steps
  • Definiteness: Each step of an algorithm must be stated clearly and unambiguously
  • Effectiveness: Each step in an algorithm can be converted into a programming language statement
  • Generality: Algorithm is generalized and works on all set of inputs
• Categories of algorithms:
  • Sequence: Steps are performed successively one by one
  • Selection: Involves decision-making and conditional branching
  • Iteration: Used for solving problems that involve repetition of statements

Performance Analysis of Algorithms

• Time Complexity: The amount of time required for an algorithm to complete its execution
• Space Complexity: The amount of space occupied by an algorithm
• Asymptotic Notations:
  • Big Oh Notation (Ο): Measures the upper bound of an algorithm's running time
  • Omega Notation (Ω): Measures the lower bound of an algorithm's running time
  • Theta Notation (θ): Measures both the upper and lower bound of an algorithm's running time

Data Structures

• Data Structure: An organized collection of data with allowed operations
• Types of Data Structures:
  • Linear Data Structures: Organize data elements in a linear fashion (e.g., arrays, linked lists, stacks, and queues)
  • Non-Linear Data Structures: Organize data elements in a non-sequential fashion (e.g., multidimensional arrays, trees, graphs, tables, and sets)
• Operations on Data Structures:
  • Traversing
  • Searching
  • Inserting
  • Deleting
  • Sorting
  • Merging

Stacks and Queues

• Stack: A linear data structure that follows the LIFO (Last In, First Out) principle
• Operations on Stacks:
  • Push: Add a new element to the stack
  • Pop: Remove an element from the stack
• Representation of Stacks:
  • Using arrays
  • Using linked lists

Stack Operations

• Push Operation:
  • Add a new element to the stack
  • Check if the stack is full before adding a new element
• Pop Operation:
  • Remove an element from the stack
  • Check if the stack is empty before removing an element
• Display Operation:
  • Display the elements in the stack
  • Check if the stack is empty before displaying the elements### Stack Operations
• A stack is used to check for balancing of parentheses, brackets, and braces in compilers.
• It is used to evaluate postfix expressions and convert infix expressions into postfix or prefix form.
• In recursion, all intermediate arguments and return values are stored on the processor's stack.
• During a function call, the return address and arguments are pushed onto a stack and popped off when the function returns.

Algebraic Expressions

• An algebraic expression is a legal combination of operators and operands.
• Operands are quantities on which mathematical operations are performed, and can be variables or constants.
• Operators are symbols that signify mathematical or logical operations between operands.
• There are three types of algebraic expressions: infix, postfix, and prefix.

Infix, Postfix, and Prefix Notations

• Infix notation places the arithmetic operator between two operands (e.g. A + B).
• Prefix notation places the arithmetic operator before its two operands (e.g. + A B).
• Postfix notation places the arithmetic operator after its two operands (e.g. A B +).

Conversion from Infix to Postfix

• Scan the infix expression from left to right.
• If the scanned symbol is a left parenthesis, push it onto the stack.
• If the scanned symbol is an operand, place it directly in the postfix expression.
• If the scanned symbol is a right parenthesis, pop all items from the stack and place them in the postfix expression until the matching left parenthesis is found.
• If the scanned symbol is an operator, remove all operators from the stack and place them in the postfix expression if their precedence is greater than or equal to the precedence of the scanned operator.

Evaluation of Postfix Expressions

• Use a stack to evaluate the postfix expression.
• When a number is seen, push it onto the stack.
• When an operator is seen, apply it to the two numbers popped from the stack and push the result onto the stack.
• There is no need to know precedence rules when evaluating postfix expressions.

Queues

• A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle.
• Items are inserted at the rear and deleted from the front of the queue.
• Queue operations are analogous to those of a stack, but with insertions at the end and deletions at the beginning.
• Queue operations include enqueue (insertion), dequeue (deletion), and display.

Representation of Queues

• Queues can be represented using arrays or linked lists.
• Array representation uses a fixed-size array to store queue elements.
• Linked list representation uses a dynamic list of nodes, each pointing to the next node.

Linear Lists

• A linear list is a collection of elements that can be stored in a specific order.
• Operations on linear lists include create, destroy, determine whether the list is empty, determine the size of the list, find an element with a given index, and insert or delete an element at a given index.

Array Representation of Linear Lists

• Array representation uses a mathematical formula to map list elements to array positions.
• The formula is Location(i) = i-1, which means the ith element of the list is in position i-1 of the array.
• The length of the list is stored separately and is used to keep track of the current size of the list.

Insertion and Deletion of Linear Lists

• To remove an element from the list, move all elements to the right of it down by one position.
• To insert an element, move all elements to the right of it up by one position and then insert the new element.

Linked Representation of Linear Lists

• Linked representation uses a separate node for each element of the list.
• Each node has a link field that points to the next node in the list.
• The link field is used to locate the next element in the list.### Queue Using Arrays
• A program is written to implement a queue using arrays.
• The program includes functions for insertion, deletion, and display.
• The user is prompted to enter the size of the queue and then perform operations on the queue.
• The program uses a switch statement to handle different cases for insertion, deletion, and display.

Types of Queues

• There are two types of queues: priority queue and circular queue.
• A program is written to implement a priority queue using a linked list.
• The program includes functions for insertion, deletion, and display.
• The priority queue is implemented using a linked list, where each node has a priority and info field.

Stack Implementation

• A program is written to implement a stack using an array.
• The program includes functions for push and pop operations.
• The program uses a switch statement to handle different cases for push and pop operations.

Infix to Postfix Conversion

• A program is written to convert an infix expression to a postfix expression.
• The program uses a stack to convert the infix expression to postfix.
• The program includes functions for push and pop operations.

Circular Queue

• A program is written to implement a circular queue using an array.
• The program includes functions for insertion, deletion, and display.
• The program uses a circular array to implement the queue.

Doubly Linked List

• A program is written to implement a doubly linked list.
• The program includes functions for insertion, deletion, and display.
• The program uses a doubly linked list, where each node has a prev and nxt field.

Searching Algorithms

• There are three types of searching algorithms: linear search, binary search, and Fibonacci search.
• A program is written to implement linear search and binary search.
• The program includes functions for searching and displaying the result.

Tree Traversal

• A program is written to implement tree traversal using a binary tree.
• The program includes functions for insertion, inorder, preorder, and postorder traversal.
• The program uses a binary tree, where each node has a left and right child.

Balancing a Tree

• A program is written to balance a tree using a binary search tree.
• The program includes functions for creating a binary search tree and displaying the preorder traversal.
• The program uses a binary search tree, where each node has a value and left and right child.