C++ | 四、指针、链表

指针

• 指针用来储存地址
• 定义方式，int *ptr;，使用*来表示所定义的变量是指针
• 取地址符，ptr = &a;，通过&来取得一个普通变量的地址，并储存到指针中
• 取值（解引用），想要取得一个指针变量所指向地址里储存的值，也是使用符号*，如b = *ptr即会把指针变量ptr存储地址里对应的值赋给b
• 指针和数组的关系，实际上，数据结构就是基于指针设计的，例如数组int arr[2] = {1, 2};，其数组名arr实际上是一个存储了数组第一个元素地址的指针，比如可以使用int *ptr = arr;来把数组首元素的地址赋值给ptr
• 指针的加减，指针可以通过加减来读取当前地址的相邻地址，并在使用取值符*（解引用）后可以读取相邻地址里的值，如int data = *(ptr + 2);
• 空地址，C++中，使用一个特殊的字符nullptr用来表示当前指针不指向任何有效的内存地址，如int *ptr = nullptr;

链表基础知识

• C++中为什么要使用链表结构
  • 可以充分利用小块的内存空间：因为诸如数组等数据结构，其必须占据一片连续的内存空间，此时如果数据量较大，则一些小内存空间就无法被利用，造成空间浪费；链表在内存中不连续储存，因此可以充分利用内存空间，具体见后面关于链表存储方式的介绍
  • 大小可变：数组不可变大小，因此不够灵活，而链表可以方便的进行增删等操作
  • 增删元素效率高：其它很多数据结构中，以增加元素为例，在增加之后，需要把后续所有元素都进行挪位，此时将严重影响效率，如图；而链表就没有这个问题，只需要改变所增加节点和其前一个节点，就可以完成增加元素的操作
  • 然而，链表也有缺点，就是查询效率低。这是因为链表中想要得到某一个节点的值，那就必须从前序节点依次寻址知道找到该节点
    • 
• 链表的结构：链表由多个节点组成，每个节点包括数据域data和指针域next，分别存储当前节点的数据和下一节点的地址
  • 
  • 链表的第一个节点称为头节点head，在C++中，为了简化链表的插入和删除元素操作，通常在头节点前添加一个虚拟头节点dummyNode（可以不添加该虚拟头节点），该虚拟节点的data可以为空，但是next指针指向头节点的地址
  • 最后一个节点的next为nullptr
• 链表的不同类型
  • 单链表，前面所提到的就是单链表，即单向链表，每个节点只存储下一节点的地址
  • 双链表，即双向链表，每个节点除了next指向下一节点外，还有prev指向上一节点，因此可以双向查询
    • 
  • 循环链表，即头尾相接，也就是最后一个节点的next存储了头节点的地址（这种链表可以用来解决约瑟夫环的问题）
    • 
• 链表的存储方式
  • 链表中的各个节点通过指针互相关联，因此不需要连续存储，具体的分配机制依不同的操作系统的内存管理机制而定
    • 

链表节点结构体（struct）的自定义

• 结构体struct可以用来自定义用户想要的数据类型，其地位等价于int、float、double这些数据类型（下面有一个结构体示例ListNode）
  • 结构体可以组合多种数据类型，如整型、浮点型、其它结构体等等
  • 定义一个结构体即一种新的数据类型之后，就可以使用该数据类型定义变量了
  • 定义的时候有多种初始化方式，常见的一种是使用构造函数。构造函数也是一种函数，但是它没有返回类型和返回值，另外它和结构体的名称相同，例如对于下面定义的这个ListNode结构体，其构造函数可以写为ListNode(int x) : val(x), next(nullptr) {}，这里int x是形参，: val(x), next(nullptr)是一种初始化写法，冒号表示初始化列表的开始，后面表示val被赋值为x，next被赋值为nullptr

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(nullptr) {}  // 节点结构的构造函数
};

链表的操作

• 删除节点
  • 将所删除节点上一节点的next指向所删除节点的下一节点即可
  • 在C++中，由于内存需要自己管理，因此最好把所删除节点的内存手动释放掉
  • 
• 添加节点
  • 只要把所添加节点位置的上一节点指向所添加节点，再把所添加节点的next指向下一节点即可
  • 

时间复杂度性能分析

• 可以看到，上面添加和删除节点操作本身的时间复杂度为O(1)，但是要找到对应的节点位置（即查询）的时间复杂度为O(n)，因此链表适用于需要频繁增删但是较少查询的场景
• 
• 有关时间复杂度更具体的介绍见我的另一篇文章