CS61B 课程笔记（Lecture 06）

1. ALists 和 SLists 的比较

AList

AList 的特性：
- 使用数组实现的列表结构。
- 可以通过索引快速访问元素，例如使用 A[i] 语法。
- 在添加、获取和删除操作中具有更高的效率，尤其是当元素数量较大时。

SList

SList 的缺点：
- 双向链表（DLList）在获取第 \(i\) 个元素时效率较低，因为需要从头部或尾部逐个扫描，直到找到该元素。

2. 数组列表（Naive Array Lists）

AList 不变式

addLast：下一个插入的位置始终是当前大小（size）。
getLast：最后一个项目总是在位置 \(size - 1\)。
size：始终表示 AList 中的项目数量。

简单的 AList 的具体实现，展示了 addLast、getLast 和 size 方法：

public class AList<Item> {
    private Item[] items;
    private int size;

    // Constructor to initialize the AList
    public AList() {
        items = (Item[]) new Object[10]; // 初始容量为 10
        size = 0;
    }

    // Adds an item to the end of the list
    public void addLast(Item item) {
        if (size == items.length) {
            resize(items.length * 2); // 扩大容量
        }
        items[size] = item; // 将新元素添加到最后
        size++;
    }

    // Returns the last item in the list
    public Item getLast() {
        if (size == 0) {
            throw new IllegalArgumentException("List is empty");
        }
        return items[size - 1]; // 返回最后一个元素
    }

    // Returns the current size of the list
    public int size() {
        return size; // 返回当前元素数量
    }

    // Resize the array to the new capacity
    private void resize(int capacity) {
        Item[] newArray = (Item[]) new Object[capacity]; // 创建新数组
        for (int i = 0; i < size; i++) {
            newArray[i] = items[i]; // 复制旧数组的元素
        }
        items = newArray; // 更新指向新数组的引用
    }
}

说明：

构造函数：

初始化一个空的数组 items，并设置初始大小为 10。

addLast(Item item)：

在添加新元素之前，检查当前数组是否已满。如果满了，调用 resize 方法将数组大小加倍。

将新元素放在数组的末尾，然后更新 size。

getLast()：

返回数组中最后一个元素（即位置 size - 1 的元素）。如果数组为空，抛出异常。

size()：

返回当前数组中元素的数量。

resize(int capacity)：

创建一个新的数组，容量为 capacity，并将旧数组中的元素复制到新数组中。

3. 数组调整大小

调整大小的过程

当数组满了，我们不能直接改变数组的大小。
解决方案是创建一个更大的新数组，然后将旧数组的值复制到新数组中。

调整大小的慢速性

调整数组大小时可能会导致性能下降，因为需要复制所有元素。

4. 内存效率

使用率定义

使用率 \(R = \frac{\text{size}}{\text{items.length}}\)
当使用率 \(R < 0.25\) 时，通常将数组大小减半。

数组调整大小的实现

public class ResizableArrayList<Item> {
    private Item[] items;
    private int size;

    // Constructor to initialize the array list
    public ResizableArrayList() {
        items = (Item[]) new Object[10]; // 初始容量为 10
        size = 0;
    }

    // Adds an item to the end of the list
    public void addLast(Item item) {
        if (size == items.length) {
            resize(items.length * 2); // 扩大容量
        }
        items[size] = item; // 将新元素添加到最后
        size++;
    }

    // Resizes the array to the new capacity
    private void resize(int capacity) {
        Item[] newArray = (Item[]) new Object[capacity]; // 创建新数组
        for (int i = 0; i < size; i++) {
            newArray[i] = items[i]; // 复制旧数组的元素
        }
        items = newArray; // 更新指向新数组的引用
    }

    // Returns the current size of the list
    public int size() {
        return size; // 返回当前元素数量
    }

    // Returns the item at a specific index
    public Item get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        return items[index]; // 返回指定索引的元素
    }
}

调整大小的过程和慢速性说明：

调整大小的过程：
- 当调用 addLast 方法并检测到数组已满时，调用 resize 方法。
- 在 resize 方法中，创建一个新的更大的数组（容量为当前数组的两倍）。
- 使用循环将旧数组中的所有元素复制到新数组中。
- 更新原数组的引用，使其指向新数组。
调整大小的慢速性：
- 调整大小操作的时间复杂度是 \(O(n)\)，因为需要复制 \(n\) 个元素。
- 在频繁的添加操作中，调整大小可能会导致性能下降。为了优化性能，通常会在容量低于某个比例时进行缩小，通常是当数组的使用率低于 25% 时。

缩小数组的实现

在上面的实现中，可以添加一个方法来缩小数组：

// Optionally, add a method to downsize the array when necessary
public void downsize() {
    if (size < items.length / 4) {
        resize(items.length / 2); // 缩小到一半
    }
}

5. 泛型 ALists

泛型数组的限制

在 Java 中，不能直接创建泛型对象数组。为了创建一个泛型 AList，我们可以使用 Object 数组，并在必要时进行类型转换。以下是一个示例实现：

public class GenericAList<Item> {
    private Object[] items; // 使用 Object 数组来存储泛型项
    private int size;

    // 构造函数，初始化数组
    public GenericAList() {
        items = new Object[10]; // 初始容量为 10
        size = 0;
    }

    // 添加项到列表末尾
    public void addLast(Item item) {
        if (size == items.length) {
            resize(items.length * 2); // 扩大数组
        }
        items[size] = item; // 存储元素
        size++;
    }

    // 获取指定索引的元素
    public Item get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        return (Item) items[index]; // 类型转换
    }

    // 删除指定索引的元素并将其置为 null
    public void remove(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        items[index] = null; // 将已删除项置为 null
        for (int i = index; i < size - 1; i++) {
            items[i] = items[i + 1]; // 移动后续元素
        }
        items[size - 1] = null; // 清空最后一个位置
        size--; // 减少大小
    }

    // 调整数组大小
    private void resize(int capacity) {
        Object[] newArray = new Object[capacity];
        for (int i = 0; i < size; i++) {
            newArray[i] = items[i]; // 复制旧数组的元素
        }
        items = newArray; // 更新引用
    }

    // 返回当前大小
    public int size() {
        return size;
    }
}