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:

1. How will the data be stored?
2. 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.

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 true or false
• 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:

• push to add an item
• pop to remove the most recently added item
• peek to view the top item
• isEmpty to 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:

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

---

Write an algorithm, pseudocode, and Java condition that identifies whether a number is positive or negative.

Algorithm

1. Read a number from the user.
2. Check if the number is greater than zero.
3. Display Positive if the condition is true.
4. Otherwise, display Negative.

Pseudocode

INPUT number
IF number > 0 THEN
    DISPLAY "Positive"
ELSE
    DISPLAY "Negative"
END IF

Java Example

if (number > 0) {
    System.out.println("Positive");
} else {
    System.out.println("Negative");
}

Practice Task

Create a program that accepts three grades: prelim, midterm, and final. Compute the average. If the average is at least 75, display Passed; otherwise, display Failed. Then write the algorithm and pseudocode for your solution.

---