IB Computer Science Topic B2.2: Data Structures Key Definitions

A fixed-size, ordered collection of elements that all share the same data type. Each element is reached by an integer index that starts at 0, and the length is set when the array is created.

Call stack is the area of memory a running program uses to track active function calls, pushing a frame holding the local variables and return address each time a function is called and popping that frame when the function returns.

An array-backed queue whose front and rear indices wrap back to 0 using the modulo operator, so slots freed by earlier dequeues are reused instead of being left unusable.

Contiguous memory allocation places every element of a structure in one unbroken block of memory, so the address of any element can be calculated from the start address and the index.

A dynamic data structure can change size while the program runs, requesting memory from the operating system as elements are added and releasing it as elements are removed.

An ordered, resizable collection of elements whose length can change while the program runs. Python provides it as the built-in list, and Java provides it as the ArrayList class.

A linear data structure in which elements are added at the rear and removed from the front, so the first element added is the first one removed.

Stack is a linear data structure in which every insertion and every removal happens at one end, called the top, so the most recently added item is always the first one removed.

A static data structure has a size that is fixed when it is created and cannot change while the program runs, so its memory is reserved as one unbroken block up front.

Task scheduling is the process of determining the order and timing of process execution.

Visiting every element of a data structure in order, once each. A for-each loop traverses a list without needing an index, while a counted loop traverses it by index.