Introduction to Algorithms - Lecture 2: Data Structures and Dynamic Arrays

This post is a derivative from Introduction to Algorithms of MIT OpenCourseWare, used under CC BY-NC-SA 4.0.

You can watch this lecture on Youtube and see PDF.

Data Structure Interfaces

Interface (API/ADT) vs. Data Structure. The idea is to separate what you want to do versus how to do it. The same problem can be solved by many different data structures.

In this class, two main interfaces: Sequence and Set.

Interface (problem)

• What data can store
• Collection of supported operations is called an interface (also API or ADT)
• Interface is a specification: what operations are supported (the problem!)

Data Structure (solution)

• How to store data
• A data structure is a way to store data, with algorithms that support operations on the data
• Data structure is a representation: how operations are supported (the solution!)

Interfaces

Sequence

Static

The number of items doesn’t change. Maintain a sequence of items x0, x1, …, xn-1 subject to these operations:

• build
• len
• iter_seq
• get_at
• set_at

Dynamic

• Insert_at
• delete_at
• insert/delete first/last

Set

Data Structure

(Static) Array Sequence

• Consecutive chunk of memory
• Array[i] = memory[address(array) + i]
• Array access is constant time (assume w >= log n)
• O(1) per get_at / set_at / len
• O(n) per build / iter_seq

Linked List Sequence

• Point based
• We’re relying on the fact that pointers can be stored in a single word, which means we can see what’s on the other side of the pointer in constant time in our word RAM model.
• This is really nice because it’s easy to manipulate the order of a linked list without actually physically moving nodes around, whereas arrays are problematic.

Dynamic Sequence ops

Static array

• If I try to insert at the beginning of the static array (that’s kind of the worst case), then everybody has to shift over.
• insert/delete cost Θ(n) time because of shifting, allocation and copying.
• Can we do delete last in constant time? No, because the size is constant.

Linked list

• We can insert and delete at the front really efficient. Θ(1) time.
• But get and set each take O(n) time.

Dynamic Array Sequence (Python Lists)

• Relax constraint size(array) = n <- # of items in sequence.
• Enforce size = Θ(n) & >= n. E.g., 2n, 10n, 1.1 times n.
• Maintain a[i] = xi