Data Structures and Algorithms: BRIDGES

This module introduces terminology and definitions related to techniques used in managing the complexity of computer programs. It provides clear explanations for the fundamental yet sometimes elusive terms "data item" and "data structure." We begin by discussing the basic building blocks on which data structures are constructed.

A type represents a set of values. For instance, the Boolean type consists of the values true and false, while the integer type encompasses whole numbers. An integer is considered a simple type since its values have no internal components. On the other hand, a bank account record typically comprises various pieces of information like name, address, account number, and balance. Such a record exemplifies an aggregate type or composite type. A data item refers to a piece of information or a record whose value is drawn from a particular type. We say that a data item belongs to a type.

A data type is a type that comes with a collection of operations used to manipulate it. For example, an integer variable belongs to the integer data type, and addition is one operation applicable to the integer data type.

It is important to distinguish between the logical concept of a data type and its physical implementation in a computer program. For instance, there exist two traditional implementations for the list data type: the linked list and the array-based list. This means that a list data type can be implemented using either a linked list or an array. However, when we are working with a more complex design and need to utilize a list, we do not necessarily require knowledge of how it is implemented. For example, a list might be used to aid in implementing a graph data structure.

Similarly, the term "array" can refer to both a data type and an implementation. In computer programming, "array" commonly denotes a contiguous block of memory locations, where each location stores a fixed-length data item. In this sense, an array is a physical data structure. However, "array" can also denote a logical data type consisting of a collection of data items, typically of the same type, each identified by an index number. Arrays can be implemented in various ways beyond a contiguous block of memory locations. For instance, a sparse matrix is a large two-dimensional array that only stores a relatively small number of non-zero values. It can be implemented using a linked structure or a hash table, while still providing the same interface as if it were implemented as a block of contiguous memory locations using traditional row and column indices.

An abstract data type (ADT) specifies a data type within a particular programming language, independent of any specific implementation. The ADT interface is defined in terms of a type and a set of operations associated with that type. The behavior of each operation is determined by its inputs and outputs. An ADT does not dictate how the data type should be implemented. The implementation details are hidden from the ADT’s user, ensuring encapsulation and protecting them from external access.

A data structure represents the concrete implementation of an ADT. In object-oriented languages, an ADT and its implementation together form a class. Each operation associated with the ADT is implemented as a member function or method. The variables that define the storage space required by a data item are known as data members. An object is an instance of a class, meaning it is created and occupies memory during program execution.

The term "data structure" often refers to data stored in a computer’s main memory, while "file structure" typically describes the organization of data on peripheral storage devices like disk drives or CDs.