Flashcards

A static, ordered set of elements of the same data type under one name, each found by its index (starting at 0).

With three indexes, such as readings[2,13,0]: for example day 2, hour 13, sensor 0.

A group of named fields, which can be of different types, describing one item. A field is accessed with a dot, as in student.surname.

A tuple is immutable: once created, its items cannot be changed, added or removed. A list is mutable and dynamic.

A static structure (an array) has a fixed size set when it is created. A dynamic structure (a list or linked list) can grow and shrink while the program runs.

Its data and a pointer to the next node. A start pointer gives the first node and the last node's pointer is null.

Store the item in a free node. Follow the pointers to find its place. Set the new node's pointer to the previous node's old pointer, then set the previous node's pointer to the new node.

Follow the pointers to the node before it, set that node's pointer to the removed node's next pointer so it is skipped, and return the removed node to the free list.

A last in, first out (LIFO) structure. push adds to the top, pop removes and returns the top item, and peek returns it without removing it.

Overflow is pushing onto a full stack. Underflow is popping from an empty stack.

A first in, first out (FIFO) structure. enqueue adds an item at the rear, and dequeue removes and returns the item at the front.

In a linear queue, space freed at the front is never reused. A circular queue wraps its pointers round to the start, so all the spaces in the array can be reused.

rear = (rear + 1) MOD maxSize, so it wraps from the last position back to 0.

The root is the top node, with no parent. A leaf is a node with no children. A subtree is a node together with all the nodes below it.

Each node has at most two children. Everything in a node's left subtree is smaller than it, and everything in its right subtree is larger.

Pre-order: node, left, right. In-order: left, node, right. Post-order: left, right, node. In-order visits a binary search tree's items in sorted order.

Replace its value with its in-order successor, the smallest value in its right subtree (or its in-order predecessor, the largest in its left subtree), then remove that node, which has at most one child.

In a directed graph each edge goes one way only. In an undirected graph each edge can be followed both ways.

For a sparse graph (few edges): the list only stores edges that exist, so it uses less memory. A matrix is quicker for checking whether a particular edge exists.

Depth-first uses a stack (or recursion). Breadth-first uses a queue.

A collision is when two keys hash to the same index. Linear probing stores the new item in the next free space, wrapping round to the start of the table if needed.

Hash the key and probe until the item is found, then mark its space as deleted rather than empty, so later searches still probe past it.