Gain insights into array and linked list-based implementations, delve into advanced structures like skiplists and trees, and explore template-based collections for efficient data optimization and retrieval.

java.tar.gz

Data structures and algorithms are essential in computer science since they play a crucial role in efficient information retrieval and processing, dealing with files, storing contacts on phones, social networks and web searches.

In this course, you’ll learn about the array-based implementation of various linear data structures, stack, and queues. You’ll also learn about linked list-based implementation. Next, you’ll explore advanced data structures like skiplists and hashing. You’ll learn how to implement a variety of trees and graphs, and data structures related to bits of an integer. Toward the end of the course, you’ll learn the implementation of structures based on external storage.

After completing this course, you’ll be able to create reusable programs with template-based collections that can efficiently analyze how to optimize the storage and retrieval of very large amounts of data. Overall, this course will enhance your productivity and performance as a software developer.

Data Structures with Generic Types in C++

Next, we consider the cost of the `gather(u)` and `spread(u)` methods that may be executed by the `add(i, x)` and `remove(i)` methods. For the sake of completeness, here they are:

void spread(Node u) {
  Node w = u;
  for (int j = 0; j < b; j++) {
    w = w.next;
  }
  w = addBefore(w);
  while (w != u) {
    while (w.d.size() < b)
      w.d.add(0, w.prev.d.remove(w.prev.d.size() - 1));
    w = w.prev;
  }
}

void gather(Node u) {
  Node w = u;
  for (int j = 0; j < b - 1; j++) {
    while (w.d.size() < b)
      w.d.add(w.next.d.remove(0));
    w = w.next;
  }
  remove(w);
}

# Amortization
The running time of each of these methods is dominated by the two nested loops. Both the inner and outer loops execute at most $b + 1$ times, so the total running time of each of these methods is $O((b + 1)^2) = O(b^2)$. However, the following lemma shows that these methods execute on at most one out of every b calls to `add(i, x)` or `remove(i)`.

**Lemma:** If an empty `SEList` is created and any sequence of $m \ge 1$ calls to `add(i, x)` and `remove(i)` is performed, then the total time spent during all calls to `spread()` and `gather()` is $O(bm)$.

**Proof:** We'll use the potential method of amortized analysis. We say that a node `u` is fragile if `u`’s block does not contain $b$ elements (so that `u` is either the last node or contains $b − 1$ or $b + 1$ elements). Any node whose block contains $b$ elements is rugged. Define the potential of an `SEList` as the number of fragile nodes it contains. We will consider only the `add(i, x)` operation and its relation to the number of calls to `spread(u)`. The analysis of `remove(i)` and `gather(u)` is identical.

Notice that, if Case 1 occurs during the `add(i, x)` method, then only one node, $u_r$ has the size of its block changed. Therefore, at most one node, namely $u_r$, goes from being rugged to being fragile. If Case 2 occurs, then a new node is created, and this node is fragile, but no other node changes size, so the number of fragile nodes increases by one. Therefore, in either Case 1 or Case 2 the potential of the `SEList` increases by at most one.

Finally, if Case 3 occurs, it is because $u_0,...,u_{b−1}$ are all fragile nodes. Then $\text{spread}(u_0)$ is called and these $b$ fragile nodes are replaced with $b+1$ rugged nodes. Finally, $x$ is added to $u_0$’s block, making $u_0$ fragile. In total, the potential decreases by $b − 1$.

In summary, the potential starts at $0$ (there are no nodes in the list). Each time Case 1 or Case 2 occurs, the potential increases by at most $1$. Each time Case 3 occurs, the potential decreases by $b − 1$. The potential (which counts the number of fragile nodes) is never less than $0$. We conclude that, for every occurrence of Case 3, there are at least $b − 1$ occurrences of Case 1 or Case 2. Hence, for every call to `spread(u)` there are at least $b$ calls to `add(i, x)`. This completes the proof.

# Summary
The following theorem summarizes the performance of the `SEList` data structure:

**Theorem:** An `SEList` implements the List interface. Ignoring the cost of calls to `spread(u)` and `gather(u)`, an `SEList` with block size $b$ supports the operations.

- `get(i)` and `set(i, x)` in $O(1+\min\{i,n−i\}/b)$ time per operation; and
- `add(i, x)` and `remove(i)` in $O(b+\min\{i,n−i\}/b)$ time per operation.

Furthermore, beginning with an empty `SEList`, any sequence of $m$ `add(i, x)` and `remove(i)` operations results in a total of $O(bm)$ time spent during all calls to `spread(u)` and `gather(u)`.

The space measured in words used by an `SEList` that stores n elements is $n+O(b+n/b)$.

The `SEList` is a trade-off between an `ArrayList` and a `DLList` where the relative mix of these two structures depends on the block size $b$. At the extreme $b = 2$, each `SEList` node stores at most three values, which is not much different than a `DLList`. At the other extreme, $b > n$, all the elements are stored in a single array, just like in an `ArrayList`. In between these two extremes lies a trade-off between the time it takes to add or remove a list item and the time it takes to locate a particular list item.


Learn about the analysis of gather and spread methods.

Overview

Array-Based Lists

Linked Lists

Skiplists

Hash Tables

Binary Trees

Random Binary Search Trees

Scapegoat Trees

Red-Black Trees

Heaps

Sorting Algorithms

Graphs

Data Structures for Integers

External Memory Searching

Wrap Up

Amortized Analysis of Spreading and Gathering

Amortization