数据结构：数组与链表

敖炜 Lv5
  2023-10-23 13:59:21 2023-10-23 13:59:21 创建   2024-04-19 09:30:09 2024-04-19 09:30:09 更新      3.3k 字  14 分钟  

这一篇博客将介绍最基础的数据结构——数组与链表

数组

按逻辑结构来说，数组是一种线性数据结构，将相同类型元素存储在连续的内存空间中，元素在数组中的位置叫做元素的索引。

数组定义与存储方式

常用操作

  1. 初始化数组

  2. 访问元素

    索引的含义本质上是数组内存地址（数组首地址）的偏移量。访问数组元素十分高效，可在时间内随机访问数组中的任意一个元素

    数组元素的内存地址计算

  3. 插入元素

    要在数组中间插入元素，需要将插入位置之后的所有元素都向后移动，再把元素赋值给该位置，这样的后移操作会导致数组的最后一个元素丢失

    数组插入元素示例

    1
    2
    3
    4
    5
    6
    def insert(arr, item, index):
        """在arr的index处插入item"""
        # 把索引index及之后的所有元素向后移动一位
        for i in range(len(arr) - 1, index, -1): # range(len(arr) - 1, index, -1)获得(index, len(num) - ]范围
            arr[i] = arr[i - 1]
        num[index] = item
    1
    2
    3
    4
    5
    6
    void insert(int[] arr, int item, int index){
        for(int i = arr.length - 1; i > index; i--){
            arr[i] = arr[i-1];
        }
        num[index] = item;
    }
    1
    2
    3
    4
    5
    6
    void insert(int* arr, int size, int item, int index){
        for(int i = size - 1; i > index; i--){
            arr[i] = arr[i - 1];
        }
        arr[index] = item;
    }

  4. 删除元素

    要删除索引index处的元素，要将index之后的所有元素都向前移动

    数组删除元素示例

    1
    2
    3
    def remove(arr, index):
        for i in range(index, len(arr) - 1):
            arr[i] = arr[i + 1]
    1
    2
    3
    4
    5
    6
    void remove(int[] arr, int index){
        for(int i = index; i < arr.length - 1; i++){
            //注意：数组的索引最多只能达到arr.length - 1，因此是i < arr.length - 1
            arr[i] = arr[i + 1];
        }
    }
    1
    2
    3
    4
    5
    void remove(int* arr, int size, int index){
        for(int i = index; i < size - 1; i++){
            arr[i] = arr[i + 1];
        }
    }

    可以看到，数组的插入与删除操作有以下缺点：
    - 时间复杂度高：数组插入和删除的平均时间复杂度均为(n为数组长度)
    - 元素丢失：插入元素时，数组最后一个元素将    丢失**(也有可能最后一个元素是无效元素)
    - 内存浪费：数组长度是固定的，可能有部分空间未被使用，造成内存浪费

  5. 遍历数组

  6. 查找元素

    在数组中查找元素需要遍历数组，进行线性查找，直到找到目标元素（返回目标元素索引）或者遍历结束仍未找到（通常返回-1）

  7. 扩容数组

    无法保证数组末尾之后的内存空间可用，大多数编程语言中，数组长度是不可变的。想要扩容数组，需要重新建立一个更大的数组，再将原数组元素一一拷贝，复杂度为

    1
    2
    3
    4
    5
    def extend(arr, enlarge):
        res = [0] * (len(arr) + enlarge)
        for i in range(len(num)):
            res[i] = arr[i]
        return res
    1
    2
    3
    4
    5
    6
    7
    int* extend(int* arr, int size, int enlarge){
        int* res = new int[size + enlarge];
        for(int i = 0; i < size; i++){
            res[i] = arr[i];
        }
        return res;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int* extend(int*arr, int size, int enlarge){
        int* res = (int*)malloc(sizeof(int) * (size + enlarge));
        for(int i = 0; i < size; i++){
            res[i] = arr[i];
        }
        // 初始化扩展后的空间
        for(int i = size; i < size + enlarge; i++){
            res[i] = 0;
        }
        return res;
    }

数组优点与局限性总结

数组的特点：存储空间连续、元素类型相同

优点：

  • 空间效率高：连续的内存空间，不需要除数据空间外的额外空间用以维护结构信息。
  • 可随机访问：访问任一元素的时间复杂度为
  • 缓存局部性良好：访问数组元素时，缓存会加载周围的局部性信息，通过局部性原理加快后续执行速度

缺点：

  • 插入和删除效率低：特别是数组中元素较多时，需要移动大量的元素
  • 长度不可变：数组内存空间初始固定分配，扩容数组开销很大
  • 空间浪费：数组空间往往未被完全运用，造成空间浪费

典型应用

  • 随机访问
  • 排序和搜索：快速排序、归并排序、二分查找都主要在数组上进行
  • 查找表
  • 机器学习：存储向量、矩阵、张量
  • 实现复杂数据结构

链表

按逻辑结构来说，链表是一种线性数据结构，节点（包含数据和引用或指针）存储在分散的内存空间中，节点引用或指针指向下一个节点，因此比数组多了一部分结构开销。

链表定义与存储方式

节点类实现方法

1
2
3
4
class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
1
2
3
4
5
struct ListNode{
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {} //构造函数
}
1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct ListNode{
    int val;
    struct ListNode* next;
}ListNode

//构造函数
ListNode* newListNode(int val){
    ListNode *node;
    node = (ListNode*)malloc(sizeof(ListNode));
    node->val = val;
    node->next = NULL;
    return node
}

链表常用操作

  1. 初始化链表

    • 初始化各个节点对象
    • 构建引用指向关系（头节点常用于代称链表）

  2. 插入节点

    • 插入节点只需改变节点引用（指针）即可，时间复杂度为

    链表插入节点示例

    1
    2
    3
    def insert(pre_node, new_node):
        new_node.next = pre_node.next
        pre_node.next = new_node
    or C
    1
    2
    3
    4
    void insert(ListNode* pre_node, ListNode* new_node){
        new_node->next = pre_node->next;
        pre_node->next = new_node;
    }

  3. 删除节点

    • 删除节点只需改变一个（被删除节点的前驱节点）节点的引用（指针）

    链表删除节点

    1
    2
    3
    4
    5
    6
    def remove(n):
        # 删除n节点后的首个节点
        if not n.next:
            # 若n节点为尾节点
            return
        n.next = n.next.next
    or C
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    void remove(ListNode* n){
        // 删除n节点后的首个节点
        if(n->next == nullptr){
            return;
        }
        ListNode* n0 = n->next; // 待删除节点
        ListNode* n1 = n0->next; // 删除后n节点的后继节点
        n->next = n1;

        delete n0; //free(n0);

        /*
        n->next = n->next->next;
        注意：不能直接这样写，C++需要手动释放内存，必须要存储带删除节点的指针值
        */
    }

  4. 访问节点

    链表仅支持顺序访问，需要从头节点开始向后遍历，效率较低，时间复杂度为

    1
    2
    3
    4
    5
    6
    7
    8
    def access(head, index) -> ListNode | None:
        for _ in range(index):
            # 沿着head向后走index次，到达(0(head) + index处)
            if not head:
                # 访问到空节点
                return None
            head = head.next
        return head
    1
    2
    3
    4
    5
    6
    7
    8
    9
    ListNode* access(ListNode* head, int index){
        for(int i = 0; i < index; i++){
            if(head == nullptr){
                return nullptr;
            }
            head = head->next;
        }
        return head;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    ListNode* access(ListNode* head, int index){
        for(int i = 0; i < index; i++){
            if(!head){
                return NULL;
            }
            head = head->next;
        }
        return head; 
    }

  5. 查找节点

    • 遍历链表，线性查找
    1
    2
    3
    4
    5
    6
    7
    8
    def find(head, target):
        index = 0
        while head:
            if head.val == target:
                return index
            head = head.next
            index += 1
        return -1
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int find(ListNode* head, int target){
        int index = 0;
        while(head != nullptr){
            if(head->val == target){
                return index;
            }
            head = head->next;
            index++;
        }
        return -1;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    int find(ListNode* head, int target){
        int index = 0;
        while(head){
            if(head->val == target){
                return index;
            }
            head = head->next;
            index++;
        }
        return -1;
    }

常见链表类型

  • 单向链表
  • 环形链表：令单向链表的尾节点指向头节点即可得到，任一节点都可视作头节点
  • 双向链表

常见链表种类

典型应用

  • 单向链表：实现栈、队列、哈希表和图等数据结构
  • 双向链表：高级数据结构（红黑树、B树）、浏览器历史、LRU算法（一种缓存淘汰算法）
  • 循环链表：时间片轮转调度算法、数据缓冲区

列表

一个抽象的数据结构概念，表示元素的有序集合，能够访问、修改、添加、删除和遍历元素等，不必考虑容量限制的问题，可基于链表或动态数组（动态扩容）实现。许多编程语言中的标准库提供的列表都是基于动态数组实现的，如Python中的list、Java中的ArrayList、C++中的vector和C#中的List等（C未提供内置动态数组）。

常用操作

  1. 初始化列表

  2. 访问元素

    • 列表本质上是数组，因此访问和更新元素的时间复杂度为

  3. 插入和删除元素

    • 在列表尾部进行插入或删除操作的时间复杂度为，在列表中间进行插入或删除操作的时间复杂度为。下面是使用Python和C++内置的列表进行插入删除操作的示例
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    # 有初始值初始化列表
    nums: nums[int] = [1, 3, 2, 5, 4]

    # 尾部添加元素
    nums.append(1)

    # 在中间插入元素
    nums.insert(3, 6) # 索引3插入6

    # 删除元素
    nums.pop(3) # 删除索引3处元素

    # 清空列表
    nums.clear()
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    // 有初始值初始化
    vector<int> nums = { 1, 3, 2, 5, 4 };

    nums.push_back(1);

    nums.insert(nums.begin() + 3, 6);

    nums.erase(nums.begin() + 3);

    nums.clear();

  4. 遍历列表

    • 可用索引遍历，Python中用len()函数获取列表长度，C++中用list.size()获取列表长度
    • 可直接迭代遍历，Python中用for num in nums语句，C++中用for(int num : nums)语句

  5. 拼接列表

    1
    2
    nums1 = [6, 8, 7, 10, 9]
    nums += nums1
    1
    2
    3
    4
    5
    // 有初始值初始化
    vector<int> nums1 = { 6, 8, 7, 10, 9 };

    // nums.end()指定插入位置，nums1.begin()指定插入元素起始位置，nums1.end()指定插入元素结束位置
    nums.insert(nums.end(), nums1.begin(), nums1.end());

  6. 排序列表

    1
    nums.sort() # 增序
    1
    sort(nums.begin(), nums.end()) // 增序

（整数）列表简单实现

三个设计重点：初始容量、数量记录和扩容机制

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# 单下划线前缀：一种约定，表示一个类的内部使用变量或方法，但不会被Python解释器认为是私有的，只是提示开发人员不要直接访问或修改这些变量

# 双下划线前缀：触发Python中的名称修饰机制，将变量名转换为`_类名__变量名`的形式，以防止类外部意外访问，但类内部仍然可通过`__变量名`访问变量。但这并不是真正的私有，你可以在类外部通过`obj._类名__变量名`访问变量

# 名称修饰机制：名称修饰会将变量名转换为`_类名__变量名`的形式，可有效避免在类继承中的变量命名冲突和某些变量被外界访问。在以下情况被触发：
#   1.基类和一个派生类都有相同名称的属性时
#   2.手动为变量名加上双下划线前缀时

# 名称修饰只在定义属性的类内部有效，在类外部或子类中，需要使用转换后的名称才能访问属性。只是使属性名更复杂，并没有提供真正的私有性
class MyList:
    def __init__(self):
        self._capacity = 10 # 列表容量
        self._arr = [0] * self._capacity
        size._size = 0 # 列表长度（当前元素数量）
        self._extend_ratio = 2

    def size(self):
        return self._size

    def capacity(self):
        return self.capacity

    def get(self, index):
        if index < 0 of index >= self._size:
            raise IndexError("索引越界")
        return self._arr[index]

    def set(self, data, index):
        if index < 0 of index >= self._size:
            raise IndexError("索引越界")
        self._arr[index] = data

    def add(self, data):
        # 在尾部添加元素
        if self.size() == self.capacity():
            self.extend_capacity()
        self._arr[self._size] = data
        self.size += 1

    def insert(self, data, index):
        if index < 0 of index >= self._size:
            raise IndexError("索引越界")
        if self.size() == self.capacity():
            self.extend_capacity()
        for j in range(self._size - 1, index - 1, -1):
            self._arr[j + 1] = self._arr[j]
        self._arr[index] = data
        self._size += 1

    def remove(self, index):
        if index < 0 of index >= self._size:
            raise IndexError("索引越界")
        data = self._arr[index]
        for j in range(index, self._size -1):
            self._arr[j] = self._arr[j + 1]
        self._size -= 1
        return data

    def extend_capacity(self):
        self._arr = self._arr + [0] * self._capacity * (self._extend_ratio - 1)
        self._capacity = len(self._arr)

    def to_array(self):
        # 返回有效长度的列表
        return self._arr[ : self._size]
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
class MyList{
    private:
        int* arr;
        int capacity = 10;
        int size = 0;
        int extendRation = 2;

    public:
        MyList(){
            arr = new int[capacity];
        }

        ~MyList(){
            delete[] arr;
        }

        int size(){
            return size;
        }

        int capacity(){
            return capacity;
        }

        int get(int index){
            if(index < 0 || index >= size()){
                throw out_of_range("索引越界")
            }
            return arr[index];
        }

        void set(int index, int data){
            if(index < 0 || index >= size()){
                throw out_of_range("索引越界")
            }
            arr[index] = data;
        }

        void add(int data){
            if(size() == capacity()){
                extendCapacity();
            }
            arr[size()] = data;
            size++;
        }

        void insert(int index, int data){
            if(index < 0 || index >= size()){
                throw out_of_range("索引越界")
            }
            if(size() == capacity()){
                extendCapacity();
            }
            for(int j = size(); j > index; j--){
                arr[j] = arr[j-1];
            }
            arr[index] = data;
            size++;
        }

        int remove(int index){
            if(index < 0 || index >= size()){
                throw out_of_range("索引越界")
            }
            int data = arr[index];
            for(int j = index; j < size() - 1; j++){
                arr[j] = arr[j + 1];
            }
            size--;
            return data;
        }

        void extendCapacity(){
            capacity = capacity() * extendRatio;
            int* tmp = arr;
            int* arr = new int[capacity()];
            for(int i = 0; i < size(); i++){
                arr[i] = tmp[i];
            }
            delete[] tmp;
        }

        vector<int> toVector(){
            vector<int> vec(size());
            for(int i = 0; i < size(); i++){
                vec[i] = arr[i];
            }
            return vec;
        }
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
typedef struct{
    int *arr;
    int capacity;
    int size;
    int extendRation;
}MyList;

//构造函数
MyList* newMyList(){
    MyList* nums = (MyList*)malloc(sizeof(MyList));
    nums->capacity = 10;
    nums->arr = (int*)malloc(sizeof(int) * nums-> capacity);
    nums->size = 0;
    nums->extendRatio = 2;
    return nums;
}

//析构函数
void delMyList(MyList* nums){
    free(num->arr);
    free(num);
}

int size(MyList* nums){
    return nums->size;
}

int capacity(MyList* nums){
    return nums->capacity;
}

int get(MyList* nums, int index){
    assert(index >= 0 && index < nums->size);
    return nums->arr[index];
}

void set(MyList* nums, int index, int data){
    assert(index >= 0 && index < nums->size);
    nums->arr[index] = data;
}

void add(MyList* nums, int data){
    if(size(nums) == capacity(nums)){
        extendCapacity(nums);
    }
    nums->arr[size(nums)] = data;
    nums->size++;
}

void insert(MyList* nums, int index, int data){
    assert(index >= 0 && index < size(nums));
    if(size(nums) == capacity(nums)){
        extendCapacity(nums);
    }
    for(int j = size(nums); j > index; --j){
        nums->arr[j] = nums->arr[j-1];
    }
    nums->arr[index] = data;
    nums->size++;
}

int remove(MyList* nums, int index){
    assert(index >= 0 && index < size(nums));
    int data = nums->arr[index];
    for(int i = index; i < size(nums) - 1; ++i){
        nums->arr[i] = nums->arr[i + 1];
    }
    nums->size--;
    return data;
}

void extendCapacity(MyList* nums){
    nums->capacity *= nums->nums.extendRatio;
    int* tmp = nums->arr;
    nums->arr = (int*)malloc(sizeof(int) * nums->capacity);

    for(int i = 0; i < size(nums); i++){
        nums->arr[i] = tmp[i];
    }

    free(tmp);
}

int* toArray(MyList* nums){
    return nums->arr;
}
  • 标题: 数据结构：数组与链表
  • 作者: 敖炜
  • 创建于 : 2023-10-23 13:59:21
  • 更新于 : 2024-04-19 09:30:09
  • 链接: https://ao-wei.github.io/2023/10/23/数据结构：数组与链表/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论
此页目录
数据结构：数组与链表
  1. 数组
    1. 常用操作
    2. 数组优点与局限性总结
    3. 典型应用
  2. 链表
    1. 链表常用操作
    2. 常见链表类型
    3. 典型应用
  3. 列表
    1. 常用操作
    2. （整数）列表简单实现