2018/01/05

单向链表

链表是一种数据结构,有单向链表、双向链表和循环链表,单向链表事其中最简单的一种。它有一个 head 指针,整个链表有很多节点构成,而 head 会始终指向链表的头节点;每个节点由两个信息组成:节点数据和指向下一个节点的指针,最后一个节点的指针为 null

节点

单向链表是由一个个节点组成的数据结构类型,每个节点都包含该节点的数据和指向下一个节点的指针,构造一个节点很简单,只需要包含这两项内容就可以了,用 ES6 的写法可以这样描述一个节点:

/**
* 单个链表节点
*/

class Node {
constructor(val) {
this.val = val;
this.next = null;
}
}

链表结构

一个链表除了由一个个节点之外,还包含一些属性,如:长度、head指针(用以指向链表的第一个节点),这里新建一个类作如下描述:

/**
* 链表
*/

class LinkedList {
constructor(val = null) {
this.head = null; // 链表的head指针
this.length = 0; // 链表的长度
if (val) {
this.head = new Node(val);
this.length = 1;
}
}
}

这样这个链表结构就有了额外的长度、head指针信息,我们可以构造一个实例看看:

<img src="//static.bingqichen.me/2018-01-14-5c4decde-QQ20180114-162739%402x.png" width="300">

添加一些方法

一般链表都会包含一些操作方法,比如 append、remove...下面就来来添加这些操作函数。

append(在链表尾部添加一个节点)

这里的重点是如何找到链表尾部,这里使用循环整个链表,找到一个节点,它的 next 指向为空即可:

class LinkedList {
...
append(val) {
const node = new Node(val); // 创建节点
if (this.head === null) { // 如果是个空列表
this.head = node;
} else {
let current = this.head;
while (current.next) { // 找到 next 指向为空的节点
current = current.next;
}
current.next = node;
}
this.length += 1; // 整个链表的长度增加
}
...
}

removeAt(删除指定位置的节点)

从一个链表删除某节点,只需要将该节点前一个的 next 指向替换为该节点的 next 指向即可,这样从整个链表来看就跳过了该节点,需要注意的是需要对用户的输入进行判断:

class LinkedList {
...
removeAt(position) {
if (position >= this.length || position < 0) { // 判断输入
return null;
}
let current = this.head;
if (position === 0) { // 删除头节点,只需改变 head 指针即可
this.head = current.next;
} else {
let index = 0;
let prev = null;
while (index < position) {
prev = current;
current = current.next;
index += 1;
}
prev.next = current.next; // 改变上一个节点的 next 指向
}
this.length -= 1; // 长度减少
return current.val; // 返回删除节点的值
}
...
}

insert(在指定位置插入节点)

跟前面的尾部插入不同,这里需要找到插入的位置,再执行插入操作:

class LinkedList {
...
insert(position, val) {
if (position >= this.length || position < 0) {
return false;
}
const node = new Node(val);
if (position === 0) { // 插入位置在头节点
node.next = this.head;
this.head = node;
} else {
let index = 0;
let current = this.head;
let prev = null;
while (index < position) { // 遍历链表找到指定位置的节点,并记录下前一个节点和该位置原节点
prev = current;
current = current.next;
index += 1;
}
node.next = current;
prev.next = node;
}
this.length += 1;
return true;
}
...
}

这里可以看到关键的两步是:把插入位置的前一个节点的 next 指向待插入的节点;把待插入的节点的 next 指向原来在该位置上的节点。

indexOf(返回第一个指定值的节点的位置)

这个功能也比较简单,只需要从第一个节点开始遍历,直到找到值符合要求的节点位置即可,在这里加入了一个可以设置起始位置的功能,无非是多了一个判断:

class LinkedList {
...
indexOf(val, start = 0) {
if (start >= this.length) { // 判断起始位置是否合法
return -1;
}
let index = 0;
let current = this.head;
while (index < this.length) {
if (current.val === val && index >= start) {
return index;
}
current = current.next;
index += 1;
}
return -1;
}
...
}

remove(移除第一个指定值的节点)

这个功能可以结合上面的 indexOfremoveAt 来完成:

class LinkedList {
...
remove(val, start = 0) {
const index = this.indexOf(val, start);
return this.removeAt(index);
}
...
}

size(返回链表长度)

class LinkedList {
...
size() {
return this.length;
}
...
}

isEmpty(返回是否为空链表)

class LinkedList {
...
isEmpty() {
return !!this.length;
}
...
}

添加了这些方法之后,就是一个完整的单向链表 js 实现了。