Module 1: Introduction to Data Structures
Computers work with large amounts of information. To process that information efficiently, data must be arranged in a way that makes storage, retrieval, updating, and computation practical. A data structure is a method of organizing data in memory or storage so that a program can use the data effectively.
A good data structure answers two important questions:
- How will the data be stored?
- What operations will be performed on the data?
For example, a program that frequently searches for records may need a different structure from a program that mostly adds new records at the end of a list.
Data, Structure, and Data Structure
Data means raw facts or values that can be processed, such as numbers, names, grades, or symbols.
Structure refers to the arrangement or organization of parts.
A data structure is therefore an organized collection of data that supports specific operations. Common examples include arrays, linked lists, stacks, queues, trees, graphs, and hash tables.
Linear and Nonlinear Data Structures
Data structures can be grouped based on how their elements are connected.
| Category | Description | Examples |
|---|---|---|
| Linear | Elements are arranged in a sequence. Each item has a clear previous and next relationship, except at the ends. | Array, linked list, stack, queue |
| Nonlinear / hierarchical | Elements are not arranged in one straight sequence. Items may branch or connect in multiple directions. | Tree, graph, heap |
Data Types
A data type describes the kind of value a variable can store. Examples include:
- integers for whole numbers
- floating-point or real numbers for decimal values
- characters for single symbols
- Boolean values for
trueorfalse - strings for sequences of characters
Choosing the correct data type helps a program store values properly and perform valid operations on them.
Abstract Data Types
An Abstract Data Type (ADT) describes data and the operations allowed on that data without focusing on how the data is implemented internally.
For example, a stack ADT may define these operations:
pushto add an itempopto remove the most recently added itempeekto view the top itemisEmptyto check whether the stack has no items
The ADT describes what the structure can do. The implementation decides how it is built, such as by using an array or a linked list.
Algorithms
An algorithm is a finite set of clear instructions used to solve a problem or perform a task. A program is usually based on one or more algorithms.
A valid algorithm should have:
| Criterion | Meaning |
|---|---|
| Input | It may receive zero or more values. |
| Output | It should produce at least one result. |
| Definiteness | Each instruction must be clear and unambiguous. |
| Finiteness | It must stop after a limited number of steps. |
| Effectiveness | Each step must be possible to perform. |
Pseudocode
Pseudocode is a plain-language description of an algorithm. It looks more structured than regular writing but is not tied to a specific programming language. It is useful for planning logic before writing code.
Stepwise Refinement
Stepwise refinement means starting with a broad solution and gradually breaking it into smaller, more detailed steps until the algorithm is ready to be coded.
Algorithm Analysis
Algorithm analysis studies how many resources an algorithm needs. The most common resources are:
- time, often measured by the number of operations
- memory, or the amount of storage needed
Common cases include:
- best case: the most favorable input condition
- worst case: the least favorable input condition
- average case: expected behavior over typical inputs