Recap what algorithm does: Manipulating memory with operation.

Memory is a big array.

Data structures: How to organize data such that operations can be done efficiently.

Array

The basic data structure.

• Read an element on some position \(i\). x=v[i] \(O(1)\).
• Write an element on some position \(i\). v[i]=x \(O(1)\).
• Create a new array inside and initialize to \(0\). v=new arr[n] \(O(n)\).
• Get the length of the array. v.length() \(O(1)\).

There are some important operation that are not just read/write/create.

For example, we may want to know is element \(x\) in array \(v\)? v.contains(x) should return true of false.

Trivial solution: Scan through the array, which takes \(O(n)\) time.

Vector

As known as resizable array. Don't need to specify the size when creating.

Read an element: \(O(1)\)

Write an element: \(O(1)\).

Create a vector: \(O(1)\).

Insert an element to the end: amortized \(O(1)\).

• When the length is less than \(2^i\), just normal write, taking \(O(1)\).
• When the length of vector is exceed \(2^i\), we need to allocated more \(2^i\) space, taking \(O(n)\) time (Here \(n\approx 2^i\)).

Check whether an element \(x\) is in vector \(v\): \(O(n)\). Not good though.

Dictionary

It is not a concrete data structure, rather an abstract data type. In practice, it needs more specification and implementation.

Create a new dictionary d=new dict()

Insert a key-value pair d.insert(key, val)

Find a value with a key d.find(key) returns the value or nothing.

Delete a key-value pair d.delete(key)

Get all elements d.as_vec()

Some Implementations

	find, insert, delete operations
Hash table	\(O(1)\) in expectation
Red-black tree	\(O(\log n)\)
B-tree	\(O(\log n)\)
AVL tree	\(O(log n)\)

Linked List

There are many variants. We use it less nowadays.

For each cell, we have a value, a pointer from the last cell and a pointer to the next cell.

\(O(1)\): Create a new one, insert front, insert back, remove front, remove back, remove given a concrete address.