Data Structures Flashcards

Think of the definition and time/space complexity (for access, search, insertion/deletion)

1
Q

Array ( Java )

A

Definition:
A contiguous block of memory storing elements of the same type, enabling random access by index.

  • Access: O(1)
  • Search: O(n)
  • Insertion/Deletion: O(n) (in the worst case)
  • Space: O(n) (fixed size).
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Dynamic Array (e.g., Python list)

A

Definition:
A resizable array that automatically reallocates memory when capacity is exceeded.

  • Access: O(1) amortized
  • Search: O(n)
  • Insertion (append): O(1) amortized, can be O(n) worst case
  • Space: O(n).
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Singly Linked List

A

Definition:
Each node stores data and a pointer to the next node.

  • Access/Search: O(n)
  • Insertion/Deletion at head: O(1)
  • Space: O(n).
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Doubly Linked List

A

Definition:
Each node stores pointers to both its next and previous nodes.

  • Access/Search: O(n)
  • Insertion/Deletion given a node reference: O(1)
  • Space: O(n).
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Stack

A

Definition:
A LIFO (Last In, First Out) structure supporting push and pop at one end.

  • Push/Pop/Peek: O(1)
  • Space: O(n)
  • Commonly used for function calls, undo operations, expression parsing.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Queue

A

Definition:
A FIFO (First In, First Out) structure supporting enqueue (add) at one end and dequeue (remove) at the other.

  • Enqueue/Dequeue: O(1)
  • Space: O(n).
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Hash Table

A

Definition:

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Binary Search Tree (BST)

A

Definition:

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Heap (Min-Heap/Max-Heap)

A

Definition:
A complete binary tree that satisfies the heap property (parent < children in a min-heap).

  • Peek (min/max): O(1)
  • Insert/Remove: O(log n)
  • Space: O(n)
  • Often used in priority queues.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Trie

A

Definition:
A prefix tree that stores strings character by character in nodes.

  • Insert/Search/Delete: O(k), where k is the string length
  • Space: O(n * k) in worst case
  • Used in auto-completion, spell-checking, IP routing.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Red-Black Tree

A

Definition:
A generalization of BST where each node can have multiple children, commonly used in databases/filesystems.

  • Search/Insert/Delete: O(log n)
  • Space: O(n)
  • Minimizes disk access by storing multiple keys per node.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Disjoint Set (Union-Find)

A

Definition:
Manages elements partitioned into disjoint sets and efficiently merges them.

  • Union/Find: ~O(α(n)), where α is the inverse Ackermann function
  • Space: O(n)
  • Useful in Kruskal’s MST and connectivity problems.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q
A