7 Data Structures for Problem Solving

Data structure selection

A data structure organizes values so that an algorithm can perform operations such as creating, storing, accessing, searching, updating, deleting, traversing, and measuring a collection.

Before choosing a structure, ask four questions:

1. What values must be stored?

2. How should those values be organized?

3. How will each value be identified or accessed?

4. Which changes must be efficient and safe?

The same operation can have different costs in different structures. Accessing an element by index is normally direct, while finding a record through a field that is not indexed may require examining many records. Therefore, the best choice depends on how the algorithm uses the data.

Takeaway: Choose a structure by matching it to the collection's dominant operations.

Strings and text operations

A String stores text as an ordered sequence of characters. In many programming languages, positions begin at index $0$. A string can therefore support direct character access, range selection, searching, and length measurement.

A slice selects a range whose ending position is excluded. For example, selecting positions $0$ through $3$ can be written as text[0:4]; the result contains four characters. Common text operations include:

• removing surrounding whitespace;

• changing letter case;

• splitting text into fields;

• joining pieces with a separator;

• replacing one substring with another.

Text fields remain strings after splitting. If a field such as 1843 must be used as a number, it must be converted explicitly. Strings are commonly immutable: an apparent modification creates a new string rather than changing the original object. For repeated construction of a large string, collecting pieces and joining them once is often more efficient than repeated concatenation.

Takeaway: Treat text as structured data, and remember that character positions and conversions affect how an algorithm processes it.

Ordered collections

An Array and a List both represent ordered collections whose values can be accessed by position. Typical operations include indexing, assignment, appending, inserting, deleting, searching, traversing, and measuring length.

An array usually emphasizes a sequence with a fixed or managed size and often consistent element types. A list is generally more flexible and can grow or shrink while a program runs. A program that stores daily temperatures, for example, can use an ordered collection because the position of each value corresponds to a day.

Insertion and deletion near the beginning of a contiguous sequence may require other elements to shift. If an algorithm performs these operations frequently, a queue, linked list, or specialized collection may be more suitable.

Traversal processes every element in order. A running total can be computed by starting at zero, adding each value, and then dividing by the collection length to obtain an average:

A List comprehension creates a new list by transforming or filtering elements. For example, it can retain only scores satisfying a passing condition while leaving the original list unchanged.

Takeaway: Use an ordered collection when position and sequence matter, but consider the cost of shifting elements during insertion and deletion.

Records and named fields

A Record groups related fields that describe one entity. A student record might contain an identification number, a name, and a grade. Named fields make the relationship among these values explicit and allow the complete entity to move through an algorithm as one logical unit.

A Dictionary is a common representation of a record: keys identify fields and values contain their contents. A class or dataclass can provide a more explicit representation when the program benefits from declared fields and behavior.

Records should preserve meaningful rules about their fields. For example, a grade may be required to remain within an allowed range. Validation checks the proposed value before storing it, preventing an update from creating an invalid record.

Using records is clearer than maintaining separate parallel lists for names and grades. When records are sorted by grade, each student's name and grade remain together.

Takeaway: Use a record when several named values belong together, and validate updates before accepting them.

Tables and database operations

A Table organizes many similar records using a consistent set of fields. Its rows represent records, its columns represent fields or attributes, and each cell is the value at one row-column intersection. A key identifies a record or connects it to another table.

In a program, a table can be represented as a list of records. The collection can then be traversed, filtered, sorted, updated, or searched. In a database, comparable operations are expressed with SQL commands:

• INSERT stores a new record;

• SELECT accesses or searches records;

• UPDATE modifies existing records;

• DELETE removes records.

A table definition can also impose constraints. A primary key identifies records, a required field prevents missing values, and a check constraint limits which values are valid. When updating a record, use a stable key rather than assuming its current position will never change.

Takeaway: Tables scale the record concept to many entities while providing consistent fields, identity, and constraints.

Combining structures and avoiding errors

Real programs combine structures to mirror the problem being solved. A school system might use a string for a student's name, an integer for an identification number, a list for test scores, a record for one student, and a table for all students.

This nesting lets an algorithm move through layers in a meaningful order:

1. Traverse the outer collection of students.

2. Access each student's record fields.

3. Traverse that student's list of scores.

4. Compute a result such as a total or average.

5. Associate the result with the student's name.

When choosing among structures, consider the dominant need:

• use a string for text;

• use an array or list for position-based access and ordered values;

• use a record for named properties of one item;

• use a table or list of records for many similar items;

• use a dictionary or keyed table for lookup by unique labels;

• use an immutable or read-only structure when changes must be prevented.

Aliasing is a defensive concern when collections are mutable. If two variables refer to the same list, changing the list through one variable also changes what the other variable sees. Create an explicit copy when independent collections are required.

Other common errors include using an invalid index, confusing a position with the value stored there, requesting a missing key, and updating the wrong record. For a sequence of length $n$, the usual valid indexes are $0$ through $n-1$.

Final takeaway: A strong design connects the data's shape, the algorithm's operations, and the safeguards needed to preserve correct data.