单向链表简介

链表和数组一样,可以用于存储一系列的元素,但是链表和数组的实现机制完全不同。链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有的语言称为指针或连接)组成。类似于火车头,一节车厢载着乘客(数据),通过节点连接另一节车厢。

image-20200707211620661

image-20200707211629678

image-20200707211641966

  • head属性指向链表的第一个节点;
  • 链表中的最后一个节点指向null;
  • 当链表中一个节点也没有的时候,head直接指向null;

数组存在的缺点

  • 数组的创建通常需要申请一段连续的内存空间(一整块内存),并且大小是固定的。所以当原数组不能满足容量需求时,需要扩容(一般情况下是申请一个更大的数组,比如2倍,然后将原数组中的元素复制过去)。
  • 在数组的开头或中间位置插入数据的成本很高,需要进行大量元素的位移。

链表的优势

  • 链表中的元素在内存中不必是连续的空间,可以充分利用计算机的内存,实现灵活的内存动态管理
  • 链表不必在创建时就确定大小,并且大小可以无限地延伸下去。
  • 链表在插入和删除数据时,时间复杂度可以达到O(1),相对数组效率高很多。

链表的缺点:

  • 链表访问任何一个位置的元素时,都需要从头开始访问(无法跳过第一个元素访问任何一个元素)。
  • 无法通过下标值直接访问元素,需要从头开始一个个访问,直到找到对应的元素。
  • 虽然可以轻松地到达下一个节点,但是回到前一个节点是很难的。

链表中的常见操作

  • append(element):向链表尾部添加一个新的项;
  • insert(position,element):向链表的特定位置插入一个新的项;
  • get(position):获取对应位置的元素;
  • indexOf(element):返回元素在链表中的索引。如果链表中没有该元素就返回-1;
  • update(position,element):修改某个位置的元素;
  • removeAt(position):从链表的特定位置移除一项;
  • remove(element):从链表中移除一项;
  • isEmpty():如果链表中不包含任何元素,返回trun,如果链表长度大于0则返回false;
  • size():返回链表包含的元素个数,与数组的length属性类似;
  • toString():由于链表项使用了Node类,就需要重写继承自JavaScript对象默认的toString方法,让其只输出元素的值;

首先需要弄清楚:下文中的position指的是两个节点之间,并且与index的关系如下图所示:

image-20200707211658363

position的值一般表示position所指位置的下一个节点。当position的值与index的值相等时,比如position = index = 1,那么它们都表示Node2。

封装单向链表类

创建单向链表类

先创建单向链表类Linklist,并添加基本属性,再实现单向链表的常用方法:

代码解析:

  • 封装LinkedList的类, 用于表示我们的链表结构. (和Java中的链表同名, 不同Java中的这个类是一个双向链表, 后面我们会讲解双向链表)
  • 在LinkedList类中有一个Node类, 用于封装每一个节点上的信息.(和优先级队列的封装一样)
  • 链表中我们保存两个属性, 一个是链表的长度, 一个是链表中第一个节点.

append(element)

向链表尾部追加数据可能有两种情况:

  • 链表本身为空, 新添加的数据时唯一的节点.
  • 链表不为空, 需要向其他节点后面追加节点.

代码实现:

过程详解:

  • 首先需要做的是将element传入方法, 并根据element创建一个Node节点.

  • 场景一: 链表本身是空的,我们只需要让head指向新建的node节点即可

  • 场景二: 链表中已经有元素了, 需要向最后的节点的next中添加节点.首先让current指向第一个节点:

image-20200707211826281

  • 通过while循环使current指向最后一个节点,最后通过current.next = newNode,让最后一个节点指向新节点newNode:

image-20200707211843432

测试代码:

//测试代码
//1.创建LinkList
let list = new LinkList()

//2.测试append方法
list.append('aaa')
list.append('bbb')
list.append('ccc')
console.log(list);

测试结果:

image-20200707211858675

toString()

代码实现:

// 实现toString方法
LinkList.prototype.toString = () => {
// 1.定义变量
let current = this.head
let listString = ""

// 2.循环获取一个个的节点
while(current){
listString += current.data + " "
current = current.next//千万不要忘了拼接完一个节点数据之后,让current指向下一个节点
}
return listString
}

方法解读:

  • 该方法比较简单, 主要是获取每一个元素
  • 还是从head开头, 因为获取链表的任何元素都必须从第一个节点开头.
  • 循环遍历每一个节点, 并且取出其中的element, 拼接成字符串.
  • 将最终字符串返回.

测试代码:

//测试代码
//1.创建LinkList
let list = new LinkList()

//2.插入数据
list.append('aaa')
list.append('bbb')
list.append('ccc')

//3.测试toString方法
console.log(list.toString());

测试结果:

image-20200707211945460

insert(position,element)

代码实现:

// 实现insert方法
LinkList.prototype.insert = (position, data) => {
//理解positon的含义:position=0表示新界点插入后要成为第1个节点,position=2表示新界点插入后要成为第3个节点
//1.对position进行越界判断:要求传入的position不能是负数且不能超过LinkList的length
if(position < 0 || position > this.length){
return false
}
//2.根据data创建newNode
let newNode = new Node(data)

//3.插入新节点
//情况1:插入位置position=0
if(position == 0){
// 让新节点指向第一个节点
newNode.next = this.head
// 让head指向新节点
this.head = newNode
//情况2:插入位置position>0(该情况包含position=length)
} else{
let index = 0
let previous = null
let current = this.head
//步骤1:通过while循环使变量current指向position位置的后一个节点(注意while循环的写法)
while(index++ < position){
//步骤2:在current指向下一个节点之前,让previous指向current当前指向的节点
previous = current
current = current.next
}
// 步骤3:通过变量current(此时current已经指向position位置的后一个节点),使newNode指向position位置的后一个节点
newNode.next = current
//步骤4:通过变量previous,使position位置的前一个节点指向newNode
previous.next = newNode
/*
启示:
1.我们无法直接操作链表中的节点,但是可以通过变量指向这些节点,以此间接地操作节点(替身使者);
比如current指向节点3,想要节点3指向节点4只需要:current.next = 4即可。
2.两个节点间是双向的,想要节点2的前一个节点为节点1,可以通过:1.next=2,来实现;
*/
}
//4.新节点插入后要length+1
this.length += 1;

return true
}

过程详解:

inset方法实现的过程:根据插入节点位置的不同可分为多种情况:

  • 情况1:position = 0

通过: newNode.next = this.head,建立连接1;

通过: this.head = newNode,建立连接2;(不能先建立连接2,否则this.head不再指向Node1)

image-20200707212003041

  • 情况2:position > 0

首先定义两个变量previous和curent分别指向需要插入位置pos = X的前一个节点和后一个节点;

然后,通过:newNode.next = current,改变指向3;

最后,通过:previous.next = newNode,改变指向4;

image-20200707212021082

  • 情况2的特殊情形:position = length

情况2也包含了pos = length的情况,该情况下current和newNode.next都指向null;建立连接3和连接4的方式与情况2相同。

image-20200707212045666

添加到其他位置:

  • 如果是添加到其他位置, 就需要先找到这个节点位置了.
  • 我们通过while循环, 一点点向下找. 并且在这个过程中保存上一个节点和下一个节点.
  • 找到正确的位置后, 将新节点的next指向下一个节点, 将上一个节点的next指向新的节点.

测试代码:

//测试代码
//1.创建LinkList
let list = new LinkList()

//2.插入数据
list.append('aaa')
list.append('bbb')
list.append('ccc')

//3.测试insert方法
list.insert(0, '在链表最前面插入节点');
list.insert(2, '在链表中第二个节点后插入节点');
list.insert(5, '在链表最后插入节点');
alert(list);
console.log(list);

image-20200707212112493

get(position)

代码实现:

//实现get方法
LinkList.prototype.get = (position) => {
//1.越界判断
// 当position = length时,取到的是null所以0 =< position < length
if(position < 0 || position >= this.length){
return null
}
//2.获取指定的positon位置的后一个节点的data
//同样使用一个变量间接操作节点
let current = this.head
let index = 0
while(index++ < position){
current = current.next
}
return current.data
}

过程详解:

get方法的实现过程:以获取position = 2为例,如下图所示:

  • 首先使current指向第一个节点,此时index=0;

image-20200707212133575

  • 通过while循环使current循环指向下一个节点,注意循环终止的条件index++ < position,即当index=position时停止循环,此时循环了1次,current指向第二个节点(Node2),最后通过current.data返回Node2节点的数据;

image-20200707212150175

测试代码:

//测试代码
//1.创建LinkList
let list = new LinkList()

//2.插入数据
list.append('aaa')
list.append('bbb')
list.append('ccc')

//3.测试get方法
console.log(list.get(0));
console.log(list.get(1));

测试结果:

image-20200707212204745

indexOf(element)

代码实现:

//实现indexOf方法
LinkList.prototype.indexOf = data => {
//1.定义变量
let current = this.head
let index = 0

//2.开始查找:只要current不指向null就一直循环
while(current){
if(current.data == data){
return index
}
current = current.next
index += 1
}

//3.遍历完链表没有找到,返回-1
return -1
}

代码解析:

  • 代码1的位置还是定义需要的变量.
  • 代码2的位置, 通过while循环获取节点
  • 通过节点获取元素和element进行对比, 如果和传入element相同, 表示找到, 直接返回index即可.
  • 如果没有找到, index++, 并且指向下一个节点.
  • 到最后都没有找到, 说明链表中没有对应的元素, 那么返回-1即可.

过程详解:

indexOf方法的实现过程:

  • 使用变量current记录当前指向的节点,使用变量index记录当前节点的索引值(注意index = node数-1)

image-20200707212224834

测试代码:

//测试代码
//1.创建LinkList
let list = new LinkList()

//2.插入数据
list.append('aaa')
list.append('bbb')
list.append('ccc')

//3.测试indexOf方法
console.log(list.indexOf('aaa'));
console.log(list.indexOf('ccc'));

测试结果:

image-20200707212236303

update(position,element)

代码实现:

//实现update方法
LinkList.prototype.update = (position, newData) => {
//1.越界判断
//因为被修改的节点不能为null,所以position不能等于length
if(position < 0 || position >= this.length){
return false
}
//2.查找正确的节点
let current = this.head
let index = 0
while(index++ < position){
current = current.next
}
//3.将position位置的后一个节点的data修改成newData
current.data = newData
//返回true表示修改成功
return true
}

测试代码:

//测试代码
//1.创建LinkList
let list = new LinkList()

//2.插入数据
list.append('aaa')
list.append('bbb')
list.append('ccc')

//3.测试update方法
list.update(0, '修改第一个节点')
list.update(1, '修改第二个节点')
console.log(list);
console.log(list.update(3, '能修改么'));

测试结果:

image-20200707212247902

removeAt(position)

代码实现:

//实现removeAt方法
LinkList.prototype.removeAt = position => {
//1.越界判断
if (position < 0 || position >= this.length) {//position不能为length
return null
}
//2.删除元素
//情况1:position = 0时(删除第一个节点)
let current = this.head
if (position ==0 ) {
//情况2:position > 0时
this.head = this.head.next
}else{
let index = 0
let previous = null
while (index++ < position) {
previous = current
current = current.next
}
//循环结束后,current指向position后一个节点,previous指向current前一个节点
//再使前一个节点的next指向current的next即可
previous.next = current.next
}
//3,length-1
this.length -= 1

//返回被删除节点的data,为此current定义在最上面
return current.data
}

过程详解:

removeAt方法的实现过程:删除节点时存在多种情况:

  • 情况1:position = 0,即移除第一个节点(Node1)。

通过:this.head = this.head.next,改变指向1即可;

虽然Node1的next仍指向Node2,但是没有引用指向Node1,则Node1会被垃圾回收器自动回收,所以不用处理Node1指向Node2的引用next。

image-20200707212300727

  • 情况2:positon > 0,比如pos = 2即移除第三个节点(Node3)。

注意:position = length时position后一个节点为null不能删除,因此position != length;

首先,定义两个变量previous和curent分别指向需要删除位置pos = x的前一个节点和后一个节点;

然后,通过:previous.next = current.next,改变指向1即可;

随后,没有引用指向Node3,Node3就会被自动回收,至此成功删除Node3 。

image-20200707212314952

测试代码:

  //测试代码
//1.创建LinkList
let list = new LinkList()

//2.插入数据
list.append('aaa')
list.append('bbb')
list.append('ccc')

//3.测试removeAt方法
console.log(list.removeAt(0));
console.log(list.removeAt(0));
console.log(list);

测试结果:

image-20200707212327149

其他方法

其他方法包括:remove(element)、isEmpty()、size()

代码实现:

/*-------------其他方法的实现--------------*/
//一.实现remove方法
LinkList.prototype.remove = (data) => {
//1.获取data在列表中的位置
let position = this.indexOf(data)
//2.根据位置信息,删除结点
return this.removeAt(position)
}

//二.实现isEmpty方法
LinkList.prototype.isEmpty = () => {
return this.length == 0
}

//三.实现size方法
LinkList.prototype.size = () => {
return this.length
}

测试代码:

    //测试代码
//1.创建LinkList
let list = new LinkList()

//2.插入数据
list.append('aaa')
list.append('bbb')
list.append('ccc')

/*---------------其他方法测试----------------*/
//remove方法
console.log(list.remove('aaa'));
console.log(list);
//isEmpty方法
console.log(list.isEmpty());
//size方法
console.log(list.size());

测试结果:

image-20200707212339289

完整实现

使用ES5实现

    // 封装链表类
function LinkList(){
// 封装一个内部类:节点类
function Node(data){
this.data = data;
this.next = null;
}

// 属性
// 属性head指向链表的第一个节点
this.head = null;
this.length = 0;

// 一.实现append方法
LinkList.prototype.append = data => {
//1.创建新节点
let newNode = new Node(data)

//2.添加新节点
//情况1:只有一个节点时候
if(this.length == 0){
this.head = newNode
//情况2:节点数大于1,在链表的最后添加新节点
}else {
//让变量current指向第一个节点
let current = this.head
//当current.next(下一个节点不为空)不为空时,一直循环,直到current指向最后一个节点
while (current.next){
current = current.next
}
// 最后节点的next指向新的节点
current.next = newNode
}
//3.添加完新结点之后length+1
this.length += 1
}

// 二.实现toString方法
LinkList.prototype.toString = () => {
// 1.定义变量
let current = this.head
let listString = ""

// 2.循环获取一个个的节点
while(current){
listString += current.data + " "
current = current.next//千万不要忘了拼接完一个节点数据之后,让current指向下一个节点
}
return listString
}

// 三.实现insert方法
LinkList.prototype.insert = (position, data) => {
//理解positon的含义:position=0表示新界点插入后要成为第1个节点,position=2表示新界点插入后要成为第3个节点
//1.对position进行越界判断:要求传入的position不能是负数且不能超过LinkList的length
if(position < 0 || position > this.length){
return false
}
//2.根据data创建newNode
let newNode = new Node(data)

//3.插入新节点
//情况1:插入位置position=0
if(position == 0){
// 让新节点指向第一个节点
newNode.next = this.head
// 让head指向新节点
this.head = newNode
//情况2:插入位置position>0(该情况包含position=length)
} else{
let index = 0
let previous = null
let current = this.head
//步骤1:通过while循环使变量current指向position位置的后一个节点(注意while循环的写法)
while(index++ < position){
//步骤2:在current指向下一个节点之前,让previous指向current当前指向的节点
previous = current
current = current.next
}
// 步骤3:通过变量current(此时current已经指向position位置的后一个节点),使newNode指向position位置的后一个节点
newNode.next = current
//步骤4:通过变量previous,使position位置的前一个节点指向newNode
previous.next = newNode

//我们无法直接操作链表中的节点,但是可以通过变量指向这些节点,以此间接地操作节点;
}
//4.新节点插入后要length+1
this.length += 1;

return true
}

//四.实现get方法
LinkList.prototype.get = (position) => {
//1.越界判断
// 当position = length时,取到的是null所以0 =< position < length
if(position < 0 || position >= this.length){
return null
}
//2.获取指定的positon位置的后一个节点的data
//同样使用一个变量间接操作节点
let current = this.head
let index = 0
while(index++ < position){
current = current.next
}
return current.data
}

//五.实现indexOf方法
LinkList.prototype.indexOf = data => {
//1.定义变量
let current = this.head
let index = 0

//2.开始查找:只要current不指向null就一直循环
while(current){
if(current.data == data){
return index
}
current = current.next
index += 1
}

//3.遍历完链表没有找到,返回-1
return -1
}

//六.实现update方法
LinkList.prototype.update = (position, newData) => {
//1.越界判断
//因为被修改的节点不能为null,所以position不能等于length
if(position < 0 || position >= this.length){
return false
}
//2.查找正确的节点
let current = this.head
let index = 0
while(index++ < position){
current = current.next
}
//3.将position位置的后一个节点的data修改成newData
current.data = newData
//返回true表示修改成功
return true
}

//七.实现removeAt方法
LinkList.prototype.removeAt = position => {
//1.越界判断
if (position < 0 || position >= this.length) {
return null
}
//2.删除元素
//情况1:position = 0时(删除第一个节点)
let current = this.head
if (position ==0 ) {
//情况2:position > 0时
this.head = this.head.next
}else{
let index = 0
let previous = null
while (index++ < position) {
previous = current
current = current.next
}
//循环结束后,current指向position后一个节点,previous指向current前一个节点
//再使前一个节点的next指向current的next即可
previous.next = current.next
}
//3,length-1
this.length -= 1

//返回被删除节点的data,为此current定义在最上面
return current.data
}

/*-------------其他方法的实现--------------*/
//八.实现remove方法
LinkList.prototype.remove = (data) => {
//1.获取data在列表中的位置
let position = this.indexOf(data)
//2.根据位置信息,删除结点
return this.removeAt(position)
}

//九.实现isEmpty方法
LinkList.prototype.isEmpty = () => {
return this.length == 0
}

//十.实现size方法
LinkList.prototype.size = () => {
return this.length
}
}

使用ES6实现

// 单向链表
export class Node {
constructor (element) {
// 保存元素
this.element = element;
// 指向下一个节点
this.next = null
}
}

export class LinkedList {
constructor () {
this.head = null;
this.length = 0
}

append (element) {
const newNode = new Node(element)
if (!this.head) {
this.head = newNode
} else {
let current = this.head
while (current.next) {
current = current.next
}
current.next = newNode
}
this.length++
}

insert (position, element) {
if (position < 0 || position > this.length -1) return false
const newNode = new Node(element)
if (position === 0) {
newNode.next = this.head
this.head = newNode
} else {
let index = 0
let current = this.head
let previous = null
while (index++ < position) {
previous = current
current = current.next
}
previous.next = newNode
newNode.next = current
}
this.length++
return true
}

get (position) {
if (position < 0 || position > this.length -1) return null
let index = 0
let current = this.head
while (index++ < position) {
current = current.next
}
return current.element
}

indexOf (element) {
let current = this.head
let index = 0
while (current) {
if (current.element === element) {
return index
}
index++
current = current.next
}
return -1
}

removeAt (position) {
if (position < 0 || position > this.length -1) return null
let current = this.head
if (position === 0) {
this.head = current.next
} else {
let index = 0
let previous = null
while (index++ < position) {
previous = current
current = current.next
}
previous.next = current.next
}
this.length--
return current.element

}

// update (position, element) {
// if (position < 0 || position >= this.length) return false
// let current = this.head
// let index = 0
// while (index++ < position) {
// current = current.next
// }
// current.element = element
// return true
// }

update (position, element) {
const result = this.removeAt(position)
this.insert(position, element)
return result
}

remove () {
const index = this.indexOf(element);
if (index === -1) return;
this.removeAt(index)
}

isEmpty () {
return this.length === 0
}

size () {
return this.length
}

}