05 — Data Structures Free Online FlashCards

What is a data structure?

A data structure organizes and stores data so programs can use it efficiently. Its design makes some operations easier and others more expensive.

Why is array indexing typically O(1)?

Arrays provide typically O(1) indexed access because an element’s address can be calculated from the array’s starting address and its index.

Why can middle updates be costly in arrays?

Inserting or deleting near an array’s beginning or middle may require shifting many elements, making the operation O(n).

How does a linked list store its elements?

A linked list stores values in separate nodes connected by references. Its nodes do not need to occupy adjacent memory locations.

What removal rule does a stack follow?

A stack removes the most recently inserted item first: it follows last in, first out (LIFO).

What removal rule does a queue follow?

A queue removes the earliest inserted item first: it follows first in, first out (FIFO).

How does a tree differ from a general graph?

A tree is connected and contains no cycles, whereas a general graph may contain cycles and need not have a single hierarchical root.

What ordering rule defines a binary search tree?

In a binary search tree, values in the left subtree are smaller than the node’s value and values in the right subtree are larger, assuming unique keys.

How does a hash table locate a value?

A hash table uses a hash function to transform a key into an array index, allowing average-case O(1) key lookup with a suitable table and hash function.

What is a hash-table collision?

A collision occurs when different keys produce the same hash-table index. Chaining and open addressing are two ways to handle collisions.

What are the costs of an adjacency matrix?

An adjacency matrix uses a two-dimensional array; edge lookup is O(1), but the representation uses O(V²) space.

When is an adjacency list useful?

An adjacency list stores each vertex’s neighboring vertices. It uses O(V + E) space and is efficient for traversing neighbors in sparse graphs.