Introduction to Data Structures

Study Notes

A data structure is a specific way to store and organize data in a computer's memory for efficient access and manipulation.
It defines the logical or mathematical model for organizing data.

Linear Data Structures have elements arranged in a sequential order. Common examples include:
- Arrays: Store data in contiguous memory locations.
- Queues: Follow a First-In-First-Out (FIFO) principle.
- Stacks: Follow a Last-In-First-Out (LIFO) principle.
- Linked Lists: Store data in nodes, with each node pointing to the next.
Non-linear Data Structures represent data with hierarchical relationships between elements. Common examples include:
- Trees: Data organized in a hierarchical structure, resembling an upside-down tree.
- Graphs: Data connected by edges, representing relationships between nodes.

Arrays: A container holding a fixed number of items of the same data type. Important terms include:
- Element: Each item stored in the array.
- Index: A numerical label representing the position of an element in the array.
Sparse Matrix: A matrix where most of the elements have a value of 0.
- Triple Representation: Stores non-zero elements as triples (Row, Column, Value) to save memory, as storing all zero elements is inefficient.
- Why Sparse Matrices?:
  - Storage Efficiency: Only non-zero elements are stored, saving space.
  - Computational Efficiency: Algorithms can focus on non-zero elements, reducing computation time.

ADT: A logical description of data and the operations that can be performed on it. It defines what data represents but not how it is implemented.

Algorithm: A sequence of well-defined instructions to perform a specific task.
- Properties:
  - Finiteness: Algorithm terminates after a finite number of steps.
  - Definiteness: Each step is clearly defined.
  - Generality: Algorithm solves a general class of problems.
  - Effectiveness: Steps can be executed in a finite amount of time.
  - Input-Output: Has well-defined inputs and outputs.
Design Goals:
- Time Complexity: Minimize the execution time.
- Space Complexity: Minimize the memory usage.

Insertion Operation: Adding one or more data elements into an array.
- Locations: Elements can be inserted at the beginning, end, or a specific index.
- Linear Array (LA): An unordered array with N elements.
- K: A positive integer representing the position where the element is to be inserted.