lec3 List Stack Queue（1)

关于链表，栈，队列。

列表抽象数据类型（List ADT）

链表的重点在于代码，其他一带而过即可。

列表的基本概念

列表是一个有限的、有序的数据元素序列，称为元素（elements）。
表示法：<a0, a1, …, an-1>，其中a0, a1, ..., an-1表示列表中的元素。
位置：每个元素在列表中有一个位置，列表的元素是按顺序排列的。
元素类型：每个元素可以是任意类型，但列表中的所有元素必须是相同类型。
长度：列表的长度是当前存储的元素个数。
空列表：空列表不包含任何元素。
头部与尾部：列表的开头称为头部（head），而列表的末尾称为尾部（tail）。

常见的列表操作

insert：插入元素
append：追加元素
delete/remove：删除元素
find：查找元素
isEmpty：检查列表是否为空
prev：指向前一个元素
next：指向下一个元素
currPos：返回当前元素的位置
moveToPos：将指针移到指定位置
moveToStart：将指针移到列表开头
length：获取列表长度

列表抽象数据类型（List ADT）模板

template <typename E>
class List {
  public:
    List() {}
    virtual ~List() {}

    virtual bool insert(const E& item) = 0;
    virtual bool append(const E& item) = 0;
    virtual bool remove(E&) = 0;
    virtual void clear() = 0;
    virtual void moveToStart() = 0;
    virtual void moveToEnd() = 0;
    virtual void prev() = 0;
    virtual void next() = 0;
    virtual int currPos() const = 0;
    virtual void moveToPos(int pos) = 0;
    // 其他操作
};

基于数组的列表（Array-based List）

基本思想：
- 预分配一个大小为MAX_SIZE的数组。
- 使用一个变量count来跟踪当前的元素数量。
- 使用一个变量curr_position来跟踪当前的位置。
- 插入或删除元素时需要移动数组中的元素。
运行时间分析：
- 对于N个元素，平均情况下需要移动一半的元素来为新元素腾出空间，假设插入操作在各个位置的概率是均等的。
- 最坏情况是插入操作在位置0时，需要将所有N个元素向后移动一位。
- 这种操作的时间复杂度为O(N)，最好的情况是Θ(1)（例如在末尾插入元素时）。

插入元素操作：insert

基本思想

插入元素时，需要将当前位置之后的元素向右移动，为新元素腾出空间。

位置通过curr表示，元素通过listArray数组进行存储。

插入操作的步骤：

检查容量：确保当前列表的大小不超过最大容量（maxSize）。如果超过，抛出异常。

元素右移：从当前位置curr开始，将所有元素右移一位。具体实现通过从listSize向curr方向遍历，依次将元素向后移动。

插入元素：将新元素it插入到当前位置curr。

更新列表大小：插入完元素后，更新列表的大小listSize。

插入操作的代码实现：
1
2
3
4
5
6
7
8
9
void insert(const E& it) {
  Assert(listSize >= maxSize, "Exceed capacity");  // 检查是否超过容量
  // 从末尾到当前位置，将元素右移
  for(int i = listSize; i > curr; i--) {
      listArray[i] = listArray[i - 1];  // 右移元素
  }
  listArray[curr] = it;  // 在当前的位置插入元素
  listSize++;  // 更新列表大小
}
时间复杂度：

最坏情况：如果在列表的开头（curr = 0）插入元素，则需要将所有元素右移一位。时间复杂度为O(N)，其中N是列表的当前大小。

最佳情况：如果插入在列表末尾（curr = listSize），则不需要移动元素。时间复杂度为O(1)。

删除元素操作：remove

基本思想

删除元素时，需要将当前位置之后的元素向左移动，填补被删除元素的位置。

删除的元素通过listArray[curr]获取。

删除操作的步骤：

检查位置合法性：确保当前元素位置在有效范围内（curr >= 0 && curr < listSize）。

保存当前元素：将curr位置的元素存储到it中，并准备返回。

元素左移：从当前位置curr开始，所有后续的元素向左移动一位，填补被删除元素的位置。

更新列表大小：删除元素后，更新列表的大小listSize。

删除操作的代码实现：
1
2
3
4
5
6
7
8
9
10
E remove() {
  Assert((curr >= 0) && (curr < listSize), "No element");  // 检查当前元素有效性
  E it = listArray[curr];  // 保存删除的元素
  // 从当前位置开始，将元素左移
  for(int i = curr; i < listSize - 1; i++) {
    listArray[i] = listArray[i + 1];  // 左移元素
  }
  listSize--;  // 更新列表大小
  return it;  // 返回删除的元素
}
时间复杂度：

最坏情况：删除操作通常涉及将所有元素向左移动，时间复杂度为O(N)。

最佳情况：删除操作在末尾元素时，不需要移动其他元素，时间复杂度为O(1)。

这两步操作的核心是判断+移动+更新。

其他操作

moveToPos：移动到指定位置

将当前元素指针移动到指定位置pos。

参数检查：确保pos在有效范围内（0 <= pos < listSize）。
1
2
3
4
5
bool moveToPos(int pos) {
  Assert((pos >= 0) && (pos < listSize), "Out of range");
  curr = pos;  // 移动到指定位置
  return true;
}
moveToStart：移动到开头

将当前位置重置为列表的开头，即curr = 0。
1
2
3
void moveToStart() { 
  curr = 0;  // 移动到列表开头
}
moveToEnd：移动到末尾

将当前位置设置为列表的末尾，即curr = listSize。
1
2
3
void moveToEnd() { 
  curr = listSize;  // 移动到列表末尾
}
prev：移动到前一个位置

如果当前元素不是列表的第一个元素，指针向前移动。
1
2
3
void prev() { 
  if(curr != 0) curr--;  // 如果不是第一个元素，则向前移动
}
next：移动到后一个位置

如果当前元素不是列表的最后一个元素，指针向后移动。
1
2
3
void next() { 
  if(curr < listSize) curr++;  // 如果不是最后一个元素，则向后移动
}
Length：获取列表长度

返回当前列表中元素的个数。
1
2
3
int Length() const { 
  return listSize;  // 返回列表的大小
}
currPos：获取当前元素位置

返回当前指针的位置。
1
2
3
int currPos() const { 
  return curr;  // 返回当前位置
}
查找元素操作：find

基本思想

查找元素K是否存在于列表中。如果存在，返回true；如果不存在，返回false。

通过遍历列表，逐个比较每个元素与目标值K。

查找操作的代码实现：
1
2
3
4
5
6
7
8
bool find(List<int>& L, int K) {
  int it;
  for(L.moveToStart(); L.currPos() < L.Length(); L.next()) {    
    it = getValue();  // 获取当前位置的元素值
    if (K == it) return true;  // 如果找到了目标元素，返回true
  }  
  return false;  // 如果未找到，返回false
}
时间复杂度：

最坏情况：需要遍历整个列表，时间复杂度为O(N)，其中N是列表的大小。

平均情况：与最坏情况相同，平均需要遍历整个列表，时间复杂度为O(N)。

基于指针的列表（链表，Linked List）

基本思想：
- 每个元素是一个节点（node），节点包含两个部分：
  - 数据域：存储元素的数据。
  - 指针域：指向下一个节点的指针（对于双向链表，可能还会有指向前一个节点的指针）。
- 链表中每个节点的地址（指针）通过前一个节点来访问。
优点：
- 插入和删除操作的时间复杂度为O(1)，因为不需要移动其他元素，只需要修改节点之间的指针。
缺点：
- 访问某个位置的元素需要从头开始遍历链表，时间复杂度为O(N)。

链表是一种动态数据结构，它由一系列通过指针相连的元素（称为节点）组成。每个节点包含数据部分和指向下一个节点的指针部分。链表可以动态增长或收缩，因此它在插入和删除操作中比数组具有更高的灵活性。

链表的基本特性是：通过动态内存分配为新的元素分配空间，并使用指针将这些元素连接起来。每个节点都保存着数据，并且通过指针链接到下一个节点。通过这种方式，链表可以表示一个有序的元素集合。

链表的基本结构

链表的每个元素称为节点（Node），每个节点包含以下部分：

元素：存储数据的部分。

指针：指向下一个节点的指针。对于单向链表，这个指针仅指向下一个节点；对于双向链表，还会有一个指针指向前一个节点。

单向链表节点结构

一个简单的单向链表节点可以通过如下结构表示：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <typename E>
class Link {
public:
    E element;   // 节点存储的元素
    Link* next;  // 指向下一个节点的指针

    // 构造函数，初始化节点元素和指针
    Link(const E& elemval, Link* nextval = NULL) {
        element = elemval;
        next = nextval;
    }

    // 仅初始化指针的构造函数
    Link(Link* nextval = NULL) {
        next = nextval;
    }
};
element：存储该节点的值。

next：指向链表中下一个节点的指针。

链表的实现类（LList）

链表实现类通常包括头指针、尾指针、当前指针（访问指针）和链表的大小。链表的实现类通常继承自一个抽象类（如 List 类），并包含用于操作链表的各种方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
template <typename E>
class LList : public List<E> {
private:
    Link<E>* head;  // 指向链表头的指针
    Link<E>* tail;  // 指向链表尾的指针
    Link<E>* curr;  // 当前指针，指向当前节点
    int cnt;        // 链表的元素个数

    // 初始化链表
    void init() {
        curr = tail = head = new Link<E>;  // 创建一个空链表头
        cnt = 0;  // 初始大小为 0
    }

    // 删除所有元素
    void removeAll() {
        while (head != NULL) {
            curr = head;
            head = head->next;
            delete curr;  // 删除当前节点
        }
    }

public:
    // 构造函数
    LList() {
        init();  // 初始化链表
    }

    // 析构函数
    ~LList() {
        removeAll();  // 删除链表中的所有节点
    }
};
头指针 head：指向链表的第一个节点。

尾指针 tail：指向链表的最后一个节点。

当前指针 curr：用于遍历链表，指向当前操作的节点。

元素计数 cnt：用于记录链表的元素个数。

链表的基本操作

插入操作（Insertion）

插入一个新的节点到链表的过程中，涉及以下三个步骤：

创建新的节点：将新元素存入节点，并设置其指针指向下一个节点。

更新当前节点指针：将当前节点的指针指向新的节点。

更新尾指针：如果插入的是尾节点，更新尾指针。

在链表中插入新节点的代码实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 插入一个节点到当前位置
void insert(const E& it) {
    curr->next = new Link<E>(it, curr->next);  // 在当前节点后插入新节点
    if (tail == curr) {
        tail = curr->next;  // 更新尾指针
    }
    cnt++;  // 增加链表的大小
}

// 在链表尾部追加一个节点
void append(const E& it) {
    tail = tail->next = new Link<E>(it, NULL);  // 在尾部插入新节点
    cnt++;  // 增加链表的大小
}
insert(const E& it)：插入一个新节点到当前节点之后。如果当前节点是尾节点，还需要更新尾指针。

append(const E& it)：在链表的尾部插入一个新节点。

删除操作（Removal）

删除操作通常需要重新调整指针，确保指向被删除节点的前一个节点正确地指向被删除节点之后的节点。删除节点后，还需要释放节点占用的内存。

以下是删除操作的实现：
1
2
3
4
5
6
7
8
9
10
11
12
// 删除并返回当前节点的元素
E remove() {
    E it = curr->next->element;  // 保存当前节点元素
    Link<E>* ltemp = curr->next;
    if (tail == curr->next) {
        tail = curr;  // 如果删除的是尾节点，更新尾指针
    }
    curr->next = curr->next->next;  // 删除当前节点
    delete ltemp;  // 释放被删除节点的内存
    cnt--;  // 减少链表的大小
    return it;  // 返回被删除节点的元素
}
remove()：删除当前节点的下一个节点，并返回其存储的元素。

当前指针的移动

next()：将当前指针向后移动一个节点。
1
2
3
4
5
void next() {
    if (curr != tail) {  // 如果当前指针不在尾部
        curr = curr->next;  // 当前指针后移
    }
}
prev()：将当前指针向前移动一个节点。需要从头节点开始遍历，找到当前节点的前一个节点。
1
2
3
4
5
6
7
8
void prev() {
    if (curr == head) return;  // 如果当前指针已经在头节点，不能再向前移动
    Link<E>* temp = head;
    while (temp->next != curr) {
        temp = temp->next;  // 找到当前节点的前一个节点
    }
    curr = temp;  // 当前指针前移
}

基于数组的列表 vs. 链表

在选择基于数组的列表和链表之间时，通常需要权衡内存效率、操作速度和数据的特性。两者的实现方式不同，管理方式也不同。

1. 基于数组的列表

基于数组的列表使用固定大小的数组存储元素，数组中的元素是连续存储的。数组的大小通常在使用前就确定好，且只有在需要扩展数组时才会进行调整。

基于数组的列表的优点：

随机访问： 通过索引访问元素的时间复杂度是 $O(1)$，因为数组中的元素是连续存储的。
固定大小时内存高效： 一旦确定了数组的大小，内存会提前分配，并且没有额外的指针空间开销。

基于数组的列表的缺点：

固定大小： 必须在分配前确定最大元素数量，如果超过了这个大小，就需要重新分配数组，且这个操作的时间复杂度为 $O(n)$。
插入和删除： 插入或删除元素（尤其是中间的元素）需要移动大量元素，操作时间复杂度为 $O(n)$。
可能存在空间浪费： 如果数组的大小远大于实际存储的元素数量，会浪费大量内存。

空间复杂度：

设定以下变量：

$n$：当前列表中的元素数量。
$D$：数组的最大大小。
$E$：每个元素的大小（以字节为单位）。

数组所需的空间是： $ = D E $ 即，数组必须为最大数量 $D$ 的元素预先分配空间，无论实际存储的元素数量如何。

2. 链表

链表由若干节点构成，每个节点包含两部分：

数据元素：实际存储的数据。
指针：指向下一个节点（单向链表）或指向下一个和上一个节点（双向链表）的指针。

链表的空间是动态分配的，随着元素的增加或删除而变化。

链表的优点：

动态大小： 链表可以随着需求的变化动态增减，不需要事先知道元素的数量，适合元素数量不确定的场景。
插入和删除效率高： 在已知位置的情况下，插入和删除操作的时间复杂度为 $O(1)$，无需移动其他元素。

链表的缺点：

指针开销： 每个节点除了存储数据外，还需要额外的空间存储指针，这会导致内存开销增大。
随机访问效率低： 通过索引访问元素的时间复杂度是 $O(n)$，因为必须从头节点开始逐一遍历，直到找到目标节点。

空间复杂度：

对于链表：

$n$：当前列表中的元素数量。
$P$：指针的大小（以字节为单位）。
$E$：每个元素的大小（以字节为单位）。

链表所需的空间是： $ = n (P + E) $ 这个公式考虑了每个节点中数据元素和指针的空间。

空间效率比较

为了比较基于数组的列表和链表的空间效率，我们可以对比它们的空间需求。

基于数组的列表空间需求： $ D E $，其中 $D$ 是数组的最大大小，$E$ 是每个元素的大小。
链表空间需求： $ n (P + E) $，其中 $n$ 是当前列表中的元素数量，$P$ 是指针的大小，$E$ 是每个元素的大小。

当 $ n > $ 时，基于数组的列表 在空间效率上更具优势。

计算链表在空间效率上优于基于数组的列表的平衡点

为了确定链表在空间效率上相对于基于数组的列表的优势，我们需要计算在什么条件下链表的空间开销低于基于数组的列表的空间开销。通过这个计算，我们可以找到 链表更高效的“平衡点”。

我们将使用以下的公式：

$ = n (P + E) $ $ = D E $

其中：

$n$ 为链表中的元素数量。
$P$ 为指针的大小（字节）。
$E$ 为数据元素的大小（字节）。
$D$ 为数组的元素最大数量。

平衡点计算

我们希望找到链表的元素数量 $n$，使得链表的空间开销小于数组的空间开销。因此，我们需要满足以下条件：

$ n (P + E) < D E $

从中，我们可以解出 $n$ 的值：

$ n < $

这个公式告诉我们，当链表的元素数量 $n$ 小于 $ $ 时，链表的空间开销会比数组更低。

练习

数据字段大小为 2 字节，指针为 4 字节，数组有 30 个元素

代入公式：

$ n < = = = 10 $

也就是说，当链表中元素数量 $n$ 小于 10 时，链表的空间效率更高。
数据字段大小为 8 字节，指针为 4 字节，数组有 30 个元素

代入公式：

$ n < = = = 20 $

当链表中元素数量 $n$ 小于 20 时，链表的空间效率更高。
数据字段大小为 32 字节，指针为 4 字节，数组有 40 个元素

代入公式：

$ n < = = $

当链表中元素数量 $n$ 小于约 35.56 时，链表的空间效率更高。

lec3 List Stack Queue（1)

列表抽象数据类型（List ADT）

列表的基本概念

常见的列表操作

列表抽象数据类型（List ADT）模板

基于数组的列表（Array-based List）

插入元素操作：insert

基本思想

插入操作的步骤：

插入操作的代码实现：

时间复杂度：

删除元素操作：remove

基本思想

删除操作的步骤：

删除操作的代码实现：

时间复杂度：

其他操作

moveToPos：移动到指定位置

moveToStart：移动到开头

moveToEnd：移动到末尾

prev：移动到前一个位置

next：移动到后一个位置

Length：获取列表长度

currPos：获取当前元素位置

查找元素操作：find

基本思想

查找操作的代码实现：

时间复杂度：

基于指针的列表（链表，Linked List）

链表的基本结构

单向链表节点结构

链表的实现类（LList）

链表的基本操作

插入操作（Insertion）

删除操作（Removal）

当前指针的移动

基于数组的列表 vs. 链表

1. 基于数组的列表

基于数组的列表的优点：

基于数组的列表的缺点：

空间复杂度：

2. 链表

链表的优点：

链表的缺点：

空间复杂度：

空间效率比较

计算链表在空间效率上优于基于数组的列表的平衡点

平衡点计算

练习

插入元素操作：`insert`

删除元素操作：`remove`

`moveToPos`：移动到指定位置

`moveToStart`：移动到开头

`moveToEnd`：移动到末尾

`prev`：移动到前一个位置

`next`：移动到后一个位置

`Length`：获取列表长度

`currPos`：获取当前元素位置

查找元素操作：`find`