1.1 Core Concepts of Data Structures

Data structure

A data structure is a storage method used to organize, process, retrieve, and store data in a computer so that it can be accessed and updated efficiently.

Algorithm

An algorithm is a step-by-step procedure that defines a set of instructions to be executed in a specific order to achieve a desired output.

Primitive data structures

These are data structures that operate directly based on machine instructions. Examples include int, char, float, double, and pointer.

Non-primitive data structures

These are complex data structures that are derived from primitive data structures.

Linear data structure

A data structure where elements are arranged sequentially or linearly, with each element connected to its previous and next adjacent elements. Examples include arrays, stacks, queues, and linked lists.

Non-linear data structure

A data structure where data elements are not arranged sequentially or linearly. Examples include trees and graphs.

Static data structure

A data structure with a fixed memory size. An array is an example of a static data structure.

Dynamic data structure

A data structure with a flexible size that can be updated during runtime, making it efficient regarding memory complexity. Examples include queues and stacks.

Data type

A form of a variable to which a value can be assigned. It holds a value but not data and its implementation is considered abstract. Examples are int, float, and double.

Abstract Data Type (ADT)

A keyword in a programming language that specifies the amount of memory needed to store data and the kind of data that will be stored in that memory location.

A Priori Analysis

A theoretical analysis of an algorithm's efficiency, assuming factors like processor speed are constant and have no effect on the implementation.

A Posteriori Analysis

An empirical analysis of an algorithm where the algorithm is implemented and executed on a target computer to collect actual statistics like running time and space required.

Main memory (RAM)

The main memory of a computer where instructions and data are stored. It is volatile, meaning data can be lost when the computer is powered down.

Cache memory

Located in the CPU, this memory is used to store frequently used instructions and data for quick access. It has the fastest access speed among all memory types.

Persistent storage

External storage devices like a hard disk used to store instructions and data. It is non-volatile, meaning data is not lost when the computer is powered down.

Memory address

A unique number assigned to each byte (group of eight bits) in the main memory.

Integer (ADT)

An Abstract Data Type that stores whole numbers and signed numbers. Examples in Java include byte, short, int, and long.

Floating-point (ADT)

An Abstract Data Type that stores real numbers (fractional values) with decimal points. Examples in Java include float (single precision) and double (double precision).

Character (ADT)

An Abstract Data Type that stores a single character as an integer value corresponding to a character set. In Java, it reserves 16 bits of main memory.

Boolean (ADT)

An Abstract Data Type that stores a true or false value, which is represented as a zero or one. In Java, it reserves 1 bit of main memory.

ASCII

A character set that uses one byte to represent a maximum of 256 characters of a language like English.

Unicode

A character set that uses two bytes to represent each character, used for languages with more than 256 characters like Russian, Arabic, Japanese, and Chinese.

Search

An algorithm category used to find a specific item within a data structure.

Sort

An algorithm category used to arrange items in a specific order.

Insert

An algorithm category used to add an item into a data structure.

Update

An algorithm category used to modify an existing item in a data structure.

Delete

An algorithm category used to remove an item from a data structure.