Introduction to Data Structures

Study Notes

A data structure is a systematic way to organize data in order to use it efficiently, making it possible to perform operations on the data quickly and efficiently.

As computers become more powerful, the need for efficient programs increases to tackle more complex problems.
Efficient programs are crucial to handle complex problems that demand more computation.
Using the proper data structure can significantly reduce the time required to run a program, from a few seconds to many days.

Interface: represents the set of operations that a data structure supports, including the type of parameters and return types.
Implementation: provides the internal representation of a data structure and defines the algorithms used in its operations.

Three common problems faced by applications today are:
- Data Search: searching for an item in a large collection of data can be slow.
- Processor Speed: high processor speeds are limited by large amounts of data.
- Multiple Requests: fast servers can fail when handling multiple requests simultaneously.
Data structures can solve these problems by organizing data in a way that minimizes search time and memory usage.

Correctness: a data structure implementation should correctly implement its interface.
Time Complexity: the running time of operations should be as small as possible.
Space Complexity: memory usage of a data structure operation should be as little as possible.

Data: values or a set of values.
Data Item: a single unit of values or a piece of information.
Group Items: data items divided into sub-items.
Elementary Items: data items that cannot be divided.
Attribute and Entity: an entity has certain attributes or properties with assigned values.
Entity Set: entities of similar attributes form a set.
Field: a single elementary unit of information representing an attribute of an entity.
Record: a collection of field values of a given entity.
File: a collection of records of the entities in a given entity set.