+
+
Posts List
  1. 链表的结构
    1. 单链表
    2. 循环链表
    3. 双向链表
    4. 双向循环链表
  2. 真实的插入、删除复杂度
  3. 链表VS数组
  4. 理解指针或引用的含义
    1. 引用传递
    2. 引用重新赋值
    3. == 和 ===
    4. 函数传参
  5. 警惕指针丢失和内存泄露
  6. 哨兵结点
  7. 留意边界条件

数据结构与算法之美:链表

链表的结构

链表通过指针将一组零散的内存块串联在一起。其中的内存块称为链表的「结点」,为了将所有结点串联起来,每个结点还需记录下一个结点的地址。

在底层存储结构上,链表与数组就有本质上的不同——数组需要一块连续的内存空间,而链表通过「指针」将一组零散的内存块串联起来。

链表有三种最常见的结构:

  • 单链表
  • 循环链表
  • 双向链表

单链表

记录下一个结点地址的指针next叫做「后继指针」。单链表中第一个结点称为「头结点」,记录链表的基地址;最后一个结点称为「尾结点」,指向一个空地址null

同数组一样,链表也支持数据的查找、插入和删除操作。但链表和数组在这些操作上的时间复杂度刚好互补:

  • 在插入或删除数据时,链表不需要保持内存的连续性而搬移结点,对应的时间复杂度为$O(1)$。
  • 在访问元素时,链表无法通过寻址公式直接计算出元素对应的内存地址,而需要根据指针一个结点一个结点地遍历。

循环链表

循环链表是一种特殊的单链表,它的尾结点指向的是头结点。

与单链表相比,循环节点的优点是从链尾到链头比较方便,适合用来处理具有环形结构特点的数据(比如约瑟夫问题)。

双向链表

双向链表,每个结点不只有后继指针next,还有前驱指针prev

因此,存储同样多的数据,双向链表比单链表要占用更多的内存空间。但双向链表的优点也很明显——支持双向遍历,支持O(1)时间复杂度的情况下找到前驱结点,使得双向链表在某些情况下的插入、删除等操作都比单链表简单高效。除此之外,在链表有序的情况下,双向链表也更加高效。

可以说,双向链表是「空间换时间」的一个有力体现。

双向循环链表

将循环链表和双向链表整合在一起,就形成了双向循环链表。

真实的插入、删除复杂度

之前说,链表的插入、删除的时间复杂度是$O(1)$,但这其实是不准确的。

以删除操作为例,在实际开发过程中,删除结点无外乎两种情况:

  1. 删除“结点值符合给定值”的结点
  2. 删除给定指针指向的结点

对于第一种情况,无论是单链表还是双向链表,都需要从头结点开始依次遍历。尽管实际的删除操作复杂度为$O(1)$,但遍历查找的时间却耗费了大量时间,导致总时间复杂度为$O(n)$。

对于第二种情况,在已经找到要删除的结点的情况下,双向链表可以直接对前驱结点进行操作,而单链表仍然需要进行$O(n)$的遍历。

链表VS数组

上面说过,链表和数组在插入、删除、随机访问操作的时间复杂度正好互补。

不过,在实际开发中,不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。

数组简单易用,由于使用的是连续的内存空间,可以借助CPU的缓存机制,预读数组中的数据,访问效率更高。而链表天然地不是连续存储的性质对CPU缓存机制就不友好。

数组的缺点是大小固定,一经声明就要占用整块连续内存空间,后期扩容需要大量数据搬移耗费时间。而链表本身没有大小限制,天然地支持动态扩容。

不过,在对内存要求十分苛刻的情况下,数组更适合。链表每个结点都需要消耗额外的存储空间去存储指针,内存消耗翻倍。此外,对链表进行频繁的插入删除操作会导致频繁的内存申请和释放,容易造成内存碎片,在Java中有可能导致频繁的垃圾回收。

理解指针或引用的含义

有些语言有「指针」的概念,有些语言虽然没有指针,但有「引用」的概念。不管是指针还是引用,它们的意思都是一样的,都是存储所指对象的内存地址。

将某个变量赋值给指针,实际上就是将这个变量的地址赋值给指针,也就是指针中存储了这个变量的内存地址,指向了这个变量。

JavaScript有5种基本类型——Boolean、null、undefined、String和Number,这些基本类型在赋值时通过「值传递」的方式,还有另外三种类型——Array、function和Object则通过「引用传递」。Array、function和Object从底层上来看其实都是Object。

对于基本数据类型,当使用=将一个变量赋值给另一变量时,实际上是将对应的值拷贝了一份,然后再将这个值赋给新的变量,这种方式称为「值传递」。

1
2
3
4
5
6
7
8
9
10
let x = 10; //Number
let y = 'abc'; //String

let a = x; //值传递
let b = y; //值传递

a = 5;
b = 'def'; //拷贝是独立的,互不干涉

console.log(x, y, a, b); //10, 'abc', 5,'def'

对于引用数据类型,当变量赋值给一个另一个变量时,后者只会记录前者的内存地址,本身不包含数据。

1
let arr = [];

执行后,内存为arr分配一块内存,其地址为#001arr指向该地址。

变量 地址 对象
arr #001 []
1
arr.push(1);

当往数组中push一个新元素时,数组对象中多了一个元素,但数组的地址不变。

变量 地址 对象
arr #001 [1]

引用传递

1
let arrCopy = arr;

再将arr赋值给新创建的数组arrCopy时,内存并不会开辟一个新的空间给arrCopyarrCopy只接受了arr的地址。

变量 地址 对象
arr #001 [1]
arrCopy #001

arrCopyarr指向同一个数组,当其中一个改动时,另一个也会发生变化。

1
2
arrCopy.push(2);
console.log(arr,arrCopy); //[1,2], [1,2]

引用重新赋值

上面我们是给一个新的数组arrCopy进行了引用赋值,如果是给一个已经赋值过的数组呢?

1
2
let obj = {first: "hello"};
obj = {second: "world"};

给一个已经赋值过的变量重新赋值,这个变量将包含新的数据或引用地址。

变量 地址 对象
#001 {first: “hello”}
obj #002 {second: “world”}

如果一个对象没有被任何变量指向,JavaScript引擎的垃圾回收机制会将该对象销毁并释放内存。

== 和 ===

对于引用数据类型,=====只会判断引用的地址是否相同,而不会判断对象具体的属性和值是否相同。

1
2
3
let x = {1: 1};
let y = {1: 1};
console.log(x==y, x===y); //false, false

如果想判断两个对象的值是否相同,需要JSON.stringify将它们转换为字符串再判断。

函数传参

当函数传入的参数是基本数据类型时,进行的是「值传递」。如果一个函数,给定一个输入,返回一个唯一的输出,而不对外界环境产生任何影响,这种函数称为纯函数。

当函数输入的是对象,进行的是「引用传递」,对该变量的操作会影响原本的变量。为了防止代码的逻辑复杂和可读性变低,数组自带的很多函数是以纯函数形式(通过JSON.parse(JSON.stringify())深度拷贝赋值给新的变量,在新变量的基础上操作)实现的,这样原始数组就不会被更改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function changeAgeAndReference(person) {
person.age = 25;
person = {
name: "John",
age: 50
};
return person;
}

var personObj1 = {
name: "Alex",
age: 30
};

var personObj2 = changeAgeAndReference(personObj1);

console.log(personObj1); // {name: "Alex", age: 25}
console.log(personObj2); // {name: "John", age: 50}

警惕指针丢失和内存泄露

以单链表的插入操作为例,如果代码写成下面这个样子:

1
2
p.next = x;
x.next = p.next;

x的后继结点就指向了自己。因此,插入结点时一定要注意操作的顺序。删除链表结点时,也一定要记得手动释放内存空间。

哨兵结点

针对链表的插入删除操作,需要对特殊情况(插入第一个结点,删除最后一个结点)进行特别处理。这时候,引入「哨兵结点」,在任何时候,不管链表是否为空,head指针都一直指向这个哨兵结点。这种有哨兵结点的链表称为「带头链表」,反之为「不带头链表」。

哨兵结点不存储数据,因为哨兵结点一直存在,所以无论是插入第一个结点或是删除最后一个结点,都可以按常规方法统一处理。

哨兵不只存在于链表中,也可运用于数组中。比如我们要在数组中查找一个值,返回它的下标:

1
2
3
4
5
6
7
8
9
10
11
//代码一:常规方法
function find(arr, target) {
for (var i = 0; i < arr.length; i++) {
if (arr[i] === target) return i;
}
return -1
}

console.log(find([4, 2, 3, 5, 9, 6], 7)); //-1
console.log(find([4, 2, 3, 5, 9, 6], 5)); //3
console.log(find([], 7)); //-1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//代码二:引入哨兵
function find(arr, target) {
arr.push(target);

var i = 0;
while (arr[i] !== target) {
i++;
}

if (i === arr.length - 1) return -1;
else return i;
}

console.log(find([4, 2, 3, 5, 9, 6], 7)); //-1
console.log(find([4, 2, 3, 5, 9, 6], 5)); //3
console.log(find([], 7)); //-1

相比代码一,代码二减少了每次循环需要比对i<n,当数据量很大时,能有效减少时间。

留意边界条件

  • 链表为空
  • 链表只包含一个结点
  • 链表只包含两个结点
  • 代码逻辑在处理头结点和尾结点时

本文作者: rhinoc

本文链接: https://www.rhinoc.top/cid216_5/

版权声明: 本博客所有文章除特别声明外,均采用BY-NC-SA 4.0国际许可协议,转载请注明。

打赏
Love U 3000
  • Through WeChat
  • Through Alipay