前言
链表作为一种数据结构，它存放着有序元素的集合。元素与元素之间通过指针连接，因此在链表中添加或删除元素只需要修改指针的指向即可，执行速度相比数组有得到显著的提升。 现实生活中也有许多使用到链表的例子，例如兔子舞，每个人勾肩搭背组合而成，其中人相当于链表中的元素，勾肩搭背的手相当于链接每个人的指针，在队列中加入一个人，只需要找到想加入的点，断开连接，插入一个人再重新连接起来。 本文将详解链表以及链表其他变相的实现思路并使用TypeScript将其实现，欢迎各位感兴趣的开发者阅读本文。
链表的实现
本文主要讲解链表的代码实现，对链表还不是很了解的开发者可以移步我的另一篇文章：数据结构:链表的基础知识。
链表与数组的区别
在实现链表之前，我们先来看看数组与链表的区别都有哪些。 数组可能是最常用的一种数据结构，每种语言都实现了数组，元素在内存中是连续存放的，因此数组提供了一个非常方便的[]方法来访问其元素。 链表存储有序元素的集合，链表中的元素在内存中并非连续存放，每个元素由一个存储元素本身的结点和一个指向下一个元素的指针组成，因此增加或删除链表内的元素只需要改变指针指向即可。 我们来总结下链表与数组各自的优点：
链表的优点：元素通过指针连接，改变链表内的元素只需要找到元素改变其指针即可，因此数据需要频繁修改时，使用链表作为数据结构是最优解决方案。数组的优点：元素连续存放在内存中，访问元素可以直接通过元素下标来访问，因此数据需要频繁查询时，使用数组作为其数据结构是最优解决方案。
上面我们总结了它们的优点，接下来我们来看下它们各自的缺点：
链表的缺点：由于链表是通过指针连接的，我们只能直接拿到链表头部的元素，要想访问其他元素需要从头遍历整个链表才能找到我们想找的元素。因此数据需要频繁查询时，使用链表将适得其反。数组的缺点：由于元素是连续存放在内存中的，改变数组内的元素时，需要调整其他元素的位置。因此数据需要频繁修改时，使用数组将适得其反。
实现思路
链表是由指针将元素连接到一起，根据链表的特性，我们可以知道要实现一个链表必须必备以下方法:
- 链表尾部添加元素
- 声明一个结点变量，以添加的元素为参数，生成一个结点，将生成的结点赋值给接待你变量。
- 判断链表头部元素是否为null，如果为null直接将链表头部赋值为结点变量
- 从链表头部开始遍历链表内的元素，直至链表的下一个元素指向null
- 向null区域追加结点变量
- 链表长度自增
- 移除链表指定位置的元素
- 判断当前要删除的位置是否为链表头部的元素，如果为链表头部元素则将当前链表头部元素指向当前链表头部元素中的next元素
- 从链表头部开始遍历链表内的元素，直至找到目标结点和目标结点的上一个结点
- 将目标结点元素指向目标结点的下一个结点元素
- 链表长度自减，返回当前删除的元素内容
- 获取链表指定位置的元素
- 声明一个变量，用于接收遍历到的结点，默认值为链表头部元素。
- 从链表头部开始遍历元素，遍历至要获取的元素位置。
- 返回遍历到的结点数据
- 链表任意位置插入元素
- 声明结点变量，将当前要插入的元素作为参数生成结点，将生成的结点赋值给结点变量
- 判断要插入的元素位置是否为0，将结点变量的下一个元素指向链表的头部元素，链表头部元素赋值为结点变量
- 获取要插入位置的上一个结点元素
- 将结点变量的下一个元素指向目标结点
- 将目标结点位置的元素赋值为结点变量
- 链表长度自增，返回true
- 根据元素获取该元素在链表中的位置
- 声明一个变量用于接收遍历到的结点
- 从链表头部开始遍历，判断当前遍历到的结点与目标结点是否相等
- 如果相等，直接返回当前遍历的索引
- 否则接收链表的下一个结点，继续执行遍历，直至遍历完链表中的所有元素为止。
- 链表的所有元素遍历完成后，仍没有发现与目标结点匹配的元素，元素不存在返回-1
- 移除链表中的指定元素
- 获取目标元素在链表中的索引
- 调用移除链表指定位置元素方法，将获取到的索引作为参数传给方法
- 获取量表长度
- 返回链表的长度即可
- 判断链表是否为空
- 调用获取链表长度方法，返回获取到的值
- 获取链表头部元素
- 返回当前链表头部元素
- 获取链表中所有元素
- 声明字符串对象变量，用于拼接获取到的元素
- 声明一个元素变量用于接收获取到的元素
- 变量链表内的所有元素
- 字符串对象变量使用","拼接元素变量获取到的元素
- 元素变量赋值其下一个元素，继续下一轮遍历。直至所有元素遍历完为至。
实现代码
经过上述分析后，我们知道了链表的实现思路，接下来我们就将上述思路转化为代码：
- 实现Node类，因为链表中每个元素是通过结点的形式来存储的，因此我们需要一个实现一个node类，为了便于复用我们创建一个utils文件夹，将其放在里面。
- 新建linked-list-models.ts文件用于存放链表的相关公用类，实现Node类
// 助手类: 用于表示链表中的第一个以及其他元素
export class Node<T>{
element: T;
next: any;
// 默认传一个元素进来
constructor (element: T) {
this.element = element;
this.next = undefined;
}
}- 新建Util.ts文件，用于存放一些常用函数，此处我们实现一个默认验证函数，实现根据元素获取元素所在链表的位置时需要用到。
// 默认验证函数
export function defaultEquals(a: any,b: any) {
return a === b;
}- 新建LinkedList.ts文件，用于实现链表，在文件中导入我们刚才写好的函数和类
// @ts-ignore
import {defaultEquals} from "../../utils/Util.ts";
// @ts-ignore
import {Node} from "../../utils/linked-list-models.ts";- 在链表类内部的构造器中，定义实现链表所需要的变量。
// 定义验证函数要传的参数和返回结果
interface equalsFnType<T> {
(a: T,b: T) : boolean;
}
// 声明链表内需要的变量并定义其类型
private count: number;
private next: any;
private equalsFn: equalsFnType<T>;
private head: any;
constructor(equalsFn = defaultEquals) {
// 初始化链表内部变量
this.count = 0;
this.next = undefined;
this.equalsFn = equalsFn;
this.head = null;
}- 实现向链表末尾插入元素函数(push)
// 链表尾部添加元素
push(element: T) {
// 声明结点变量，将元素当作参数传入生成结点
const node = new Node(element);
// 存储遍历到的链表元素
let current;
if(this.head==null){
// 链表为空，直接将链表头部赋值为结点变量
this.head = node;
}else{
// 链表不为空，我们只能拿到链表中第一个元素的引用
current = this.head;
// 循环访问链表
while (current.next !=null){
// 赋值遍历到的元素
current = current.next;
}
// 此时已经得到了链表的最后一个元素(null)，将链表的下一个元素赋值为结点变量。
current.next = node;
}
// 链表长度自增
this.count ;
}- 实现移除链表指定位置元素函数(removeAt)
removeAt(index: number) {
// 边界判断: 参数是否有效
if(index >= 0 && index < this.count){
// 获取当前链表头部元素
let current = this.head;
// 移除第一项
if(index === 0){
this.head = current.next;
}else{
// 获取目标参数上一个结点
let previous = this.getElementAt(index - 1);
// 当前结点指向目标结点
current = previous.next;
/**
* 目标结点元素已找到
* previous.next指向目标结点
* current.next指向undefined
* previous.next指向current.next即删除目标结点的元素
*/
previous.next = current.next;
}
// 链表长度自减
this.count--;
// 返回当前删除的目标结点
return current.element
}
return undefined;
}- 实现获取链表指定位置结点函数(getElementAt)
getElementAt(index: number) {
// 参数校验
if(index >= 0 && index <= this.count){
// 获取链表头部元素
let current = this.head;
// 从链表头部遍历至目标结点位置
for (let i = 0; i < index && current!=null; i ){
// 当前结点指向下一个目标结点
current = current.next;
}
// 返回目标结点数据
return current;
}
return undefined;
}- 实现向链表中插入元素函数(insert)
insert(element: T, index: number) {
// 参数有效性判断
if(index >= 0 && index <= this.count){
// 声明结点变量，将当前要插入的元素作为参数生成结点
const node = new Node(element);
// 第一个位置添加元素
if(index === 0){
// 将结点变量(node)的下一个元素指向链表的头部元素
node.next = this.head;
// 链表头部元素赋值为结点变量
this.head = node;
}else {
// 获取目标结点的上一个结点
const previous = this.getElementAt(index - 1);
// 将结点变量的下一个元素指向目标结点
node.next = previous.next;
/**
* 此时node中当前结点为要插入的值
* next为原位置处的结点
* 因此将当前结点赋值为node，就完成了结点插入操作
*/
previous.next = node;
}
// 链表长度自增
this.count ;
return true;
}
return false;
}- 实现根据元素获取其在链表中的索引函数(indexOf)
indexOf(element: T) {
// 获取链表顶部元素
let current = this.head;
// 遍历链表内的元素
for (let i = 0; i < this.count && current!=null; i ){
// 判断当前链表中的结点与目标结点是否相等
if (this.equalsFn(element,current.element)){
// 返回索引
return i;
}
// 当前结点指向下一个结点
current = current.next;
}
// 目标元素不存在
return -1;
}- 实现移除链表指定元素函数(remove)
remove(element: T) {
// 获取element的索引,移除索引位置的元素
this.removeAt(this.indexOf(element))
}- 实现获取链表长度(size)、链表头部元素(getHead)、链表判空(isEmpty)
// 获取链表长度
size() {
return this.count;
}
// 判断链表是否为空
isEmpty() {
return this.size() === 0;
}
// 获取链表头部元素
getHead() {
return this.head;
}- 实现链表内所有元素转字符串函数
toString(){
if (this.head == null){
return "";
}
let objString = `${this.head.element}`;
// 获取链表顶点的下一个结点
let current = this.head.next;
// 遍历链表中的所有结点
for (let i = 1; i < this.size() && current!=null; i ){
// 将当前结点的元素拼接到最终要生成的字符串对象中
objString = `${objString}, ${current.element}`;
// 当前结点指向链表的下一个元素
current = current.next;
}
return objString;
}完整代码请移步: LinkedList.ts
编写测试代码
链表实现后，接下来我们来测试下链表中的每个函数是否正常工作
代码语言：javascript复制const linkedList = new LinkedList();
linkedList.push(12);
linkedList.push(13);
linkedList.push(14);
linkedList.push(15);
linkedList.push(16);
linkedList.push(17);
linkedList.push(18);
linkedList.push(19);
// 移除索引为2的元素
linkedList.removeAt(2);
// 获取0号元素
console.log(linkedList.getElementAt(0));
// 查找19在链表中的位置
console.log(linkedList.indexOf(19));
// 在2号位置添加22元素
linkedList.insert(22,2);
// 获取链表中的所有元素
console.log(linkedList.toString());完整代码请移步：LinkedListTest.js
双向链表的实现
链表有多种不同的类型，双向链表就是其中一种，接下来我们来讲解双向链表的实现。 实现之前我们先来看看双向链表与普通链表的区别：
- 链表内的的结点只能链接它的下一个结点
- 双向链表的链接是双向的，双向链表内的结点一个链接下一个元素，另一个链接上一个元素。
说完他们的区别后，我们来看看双向链表的优点：双向链表相比普通链表多了一个指针，这个指针指向链表中元素的上一个元素，因此我们可以从链表的尾部开始遍历元素对链表进行操作，假设我们要删除链表中的某个元素，这个元素的位置靠近链表的末尾，我们就可以从链表的末尾来找这个元素，而链表只能从其头部开始找这个元素，此时双向链表的性能相比链表会有很大的提升，因为它需要遍历的元素少，时间复杂度低。
实现思路
我们拿双向链表和链表进行比对后发现，双向链表是在链表的基础上加多了一个指针(prev)的维护，因此我们可以继承链表，重写与链表不同的相关函数。 双向链表需要重写的函数有：尾部插入元素（push）、任意位置插入元素（insert）、任意位置移除元素（removeAt）。 接下来我们来捋一下，上述需要重写函数的实现思路：
- 尾部插入元素(push)
- 创建双向链表辅助结点(node)
- 判断链表的头部是否为空，如果为空将链表头部和尾部都指向node
- 链表头部不为空时，将链表尾部结点中的next指向node，将node结点中的prev指向当前链表尾部元素(this.tail)。
- 将当前链表尾部元素（this.tail）指向node
- 链表长度自增
- 链表任意位置插入元素(insert)
- 声明previous变量，接收链表中要插入位置的元素
- current指向previous中的next
- node中的next指向current
- previous中的nextnext指向node
- current中的prev指向node
- node中的prev指向previous
- current指向当前链表尾部元素
- current结点中的next指向node
- node结点中的prev指向current
- 当前链表尾部元素指向node
- 链表头部为null，直接调用push函数即可
- 链表头部不为null，将node结点中的next指向头部元素，current结点中的prev指向node，当前链表头部（this.head）指向node结点
- 函数需要的参数：要插入的结点(element)，要插入的位置(index)
- 对index参数进行有效性判断，index必须大于等于0且小于等于当前链表的长度，否则就返回undefined
- 创建双向链表辅助结点（node）
- 声明链表元素辅助变量（current），默认指向当前链表头部(this.head)
- 向链表中插入元素分为三种情况：链表头部(index = 0)、链表尾部(index = this.count)、其他位置
- index = 0时，即向链表头部插入元素，分为两种情况
- index = this.count时，即向链表尾部插入元素
- index为其他数字时，即向链表的其他位置插入元素
- 链表长度自增，返回true。
- 任意位置移除元素
- current指向当前要删除位置的元素
- 声明previous变量，将其指向current中的prev
- previous中的next指向current中的next
- current中的next元素里的prev指向previous
- current指向当前链表的末尾元素
- 当前链表的末尾元素指向current中的prev
- 当前链表末尾元素中的next指向undefined
- 当前头部元素指向指向current中的next
- 判断链表长度是否为1，如果为1则将当前链表末尾元素指向undefined
- 链表长度不为1，将链表头部中的prev指向undefined
- 参数有效性判断，要删除的位置参数必须大于等于0且小于等于当前链表的长度
- 声明链表元素辅助变量（current），默认指向链表头部
- 移除链表中的元素分为三种情况：链表头部(index = 0)、链表尾部(index = this.count - 1)、其他位置
- index = 0时，即删除链表头部元素
- idnex = this.count - 1时，即删除链表尾部元素
- index为其他数字时，即删除链表其他位置元素
- 链表长度自减，返回当前要移除的元素
实现代码
我们已经捋清了实现思路，接下来我们将上述实现思路转换为代码： 实现双向链表之前，我们需要对链表的辅助类进行修改。
- 在linked-list-models.ts中添加DoublyNode类，继承Node类
export class DoublyNode<T> extends Node<T>{
prev: any;
constructor(element: T, next?: any, prev?: any) {
// 调用Node类的构造函数
super(element,next);
// 新增prev属性，指向链表元素的上一个元素
this.prev = prev;
}
}- 新建DoublyLinkedList.ts文件，用于实现双向链表
- 声明DoublyLinkedList类，继承LinkedList类
export default class DoublyLinkedList extends LinkedList{
}- 类内部的构造函数中声明实现双向链表需要使用的变量
private tail: any;
constructor(equalsFn = defaultEquals) {
// 调用Node类的构造函数
super(equalsFn);
// 新增属性，用于指向链表的最后一个元素
this.tail = undefined;
}- 重写链表尾部插入元素函数（push）
push(element: T) {
// 创建双向链表辅助结点
const node = new DoublyNode(element);
if (this.head == null){
// 链表头部为空，头部和尾部都指向node
this.head = node;
this.tail = node;
}else{
// 将链表尾部结点中的next指向node
this.tail.next = node;
// 将node结点中的prev指向当前链表尾部元素
node.prev = this.tail;
// 当前链表末尾元素指向node
this.tail = node;
}
// 链表长度自增
this.count ;
}- 重写链表任意位置插入元素函数(insert)
insert(element: T, index: number) {
// 参数有效性判断
if(index >=0 && index <= this.count){
// 创建结点
const node = new DoublyNode(element);
// 声明链表元素辅助变量（current），默认指向当前链表头部(this.head)
let current = this.head;
// 链表头部添加元素
if(index === 0){
// 链表头部为空
if(this.head == null){
// 调用push方法
this.push(element);
}else{
// 不为空，将node.next指向当前头部元素
node.next = this.head;
// 链表头部的元素结点中上一个位置指向node
current.prev = node;
// 头部元素指向node
this.head = node;
}
}else if(index === this.count){
// 链表尾部添加元素，链表元素辅助变量指向挡脸链表尾部元素
current = this.tail;
// 链表元素辅助变量结点中的下一个元素指向node
current.next = node;
// node结点中的prev指向current
node.prev = current;
// 当前链表尾部元素指向node
this.tail = node;
}else{
// 链表的其他位置插入元素
const previous = super.getElementAt(index - 1);
// 元素变量指向目标结点
current = previous.next;
// node的下一个指向目标结点位置的元素
node.next = current;
// 目标结点指向结点变量
previous.next = node;
// 目标结点的上一个结点指向结点变量
current.prev = node;
// 结点插入完毕，调整结点的上一个指针指向
node.prev = previous;
}
// 链表长度自增
this.count ;
// 返回true
return true;
}
return false
}- 重写移除链表任意位置元素(removeAt)
removeAt(index: number): any {
// 参数有效性判断
if(index >=0 && index < this.count){
// current变量指向链表头部
let current = this.head;
if(index === 0){
this.head = current.next;
if(this.count === 1){
// 链表长度为1，直接将链表的末尾元素指向设为undefined
this.tail = undefined;
}else{
// 将链表头部的上一个元素指向undefined
this.head.prev = undefined;
}
}else if(index === this.count - 1){
// 链表末尾移除元素
current = this.tail;
// 链表末尾元素指向其上一个元素
this.tail = current.prev;
// 链表末尾的下一个元素设为undefined
this.tail.next = undefined;
}else{
// 双向链表其他位置移除元素
current = super.getElementAt(index);
// 获取当前要移除元素的上一个元素
const previous = current.prev;
// 目标元素的下一个元素指向当前要移除元素的下一个元素
previous.next = current.next;
// 当前要移除元素的下一个元素指向要移除元素的上一个元素
current.next.prev= previous;
}
// 链表长度自减
this.count--;
// 返回当前要移除的元素
return current.element;
}
return undefined;
}- 实现获取链表尾部元素(getTail)
getTail(){
return this.tail;
}- 重写清空函数(clear)
clear() {
super.clear();
this.tail = undefined;
}- 实现从链表尾部向链表头部获取链表内所有元素函数(inserseToString)
inverseToString() {
if(this.tail == null){
return "";
}
let objString = `${this.tail.element}`;
// 获取链表尾部元素的上一个元素
let previous = this.tail.prev;
while (previous!=null){
// 将当前获取到的链表元素拼接至链表字符串对象中
objString = `${objString}, ${previous.element}`;
// 获取当前链表尾部元素的上一个元素
previous = previous.prev;
}
return objString;
}完整代码请移步：DoublyLinkedList.ts
编写测试代码
双向链表实现后，我们测试下双线链表中的函数是否都正常工作。
代码语言：javascript复制const doublyLinkedList = new DoublyLinkedList();
// 双向链表尾部插入元素
doublyLinkedList.push(12);
doublyLinkedList.push(14);
doublyLinkedList.push(16);
// 双向链表任意位置插入元素
doublyLinkedList.insert(13,1);
doublyLinkedList.insert(11,0);
doublyLinkedList.insert(14,4);
//移除指定位置元素
doublyLinkedList.removeAt(4);
doublyLinkedList.insert(15,4);
// 删除链表中的元素
doublyLinkedList.remove(16);
console.log(doublyLinkedList.toString());
// 获取链表尾部元素
console.log(doublyLinkedList.getTail());
console.log(doublyLinkedList.inverseToString());
// 获取链表长度
console.log("链表长度",doublyLinkedList.size())
doublyLinkedList.removeAt(4);
// 清空链表
doublyLinkedList.clear();
console.log(doublyLinkedList.isEmpty());完整代码请移步：DoublyLinkedListTest.js
循环链表的实现
循环链表也属于链表的一种变体，它与链表的唯一区别在于，最后一个元素指向链表头部元素，并非undefined。
实现思路
循环链表相对于链表，改动地方较少，在首、尾插入或删除元素时，需要更改其指针指向，因此我们只需要继承链表，然后重写插入和移除方法即可。
- 重写插入方法(insert)
- 链表头部为null时，则将当前头部元素指向node，node结点中的next指向当前头部元素。
- 链表头部不为null时，将node中的next指向current
- current指向链表的末尾元素
- 链表头部指向node
- current中的next指向链表头部
- 插入位置参数(index)有效性判断，index必须大于等于0且小于等于链表成都
- 声明结点变量(node)，将当前要插入的元素放进Node结点中
- 声明链表元素变量(current),默认指向当前链表头部元素(this.head)
- 向链表中插入元素有两种情况：链表头部插入元素、链表其他位置插入元素
- index = 0，即链表头部插入元素，分为两种情况：
- index不为0，即链表其他位置插入元素，与链表的写法一致
- 重写移除方法(removeAt)
- 链表长度为1，直接将链表头部指向undefined
- 链表长度不为1
- 声明变量removed，用于保存链表头部元素，将其从循环链表中移除
- current指向链表末尾元素
- 链表头部指向链表头部元素中的next
- 链表尾部元素中的next指向新的链表头部
- 更新current的引用，将其指向removed，用于返回当前移除的元素值
- 移除位置参数(index)有效性判断，index必须大于等于0且小雨链表长度
- 移除链表中的元素分为2种情况：链表头部移除元素、链表其他位置移除元素
- index = 0，即链表头部移除元素，分为两种情况
- index不为0，即链表其他位置插入元素，与链表的写法一致。
实现代码
我们捋清思路后，将上述思路转化为代码
- 新建CircularLinkedList.ts文件，用于实现循环链表类
- 声明CircularLinkedList类并继承LinkedList
export default class CircularLinkedList<T> extends LinkedList<T>{
}- 构造器中初始化
constructor(equalsFn = defaultEquals) {
super(equalsFn);
}- 重写链表中插入元素函数(insert)
insert(element: T, index: number) {
if(index >= 0 && index <= this.count){
// 声明结点变量
const node = new Node(element);
// 声明链表元素变量，默认指向当前链表头部元素
let current = this.head;
if(index === 0){
// 链表头部添加元素
if(this.head == null){
// 链表头部为空
this.head = node;
// 链表的最后一个结点指向链表头部
node.next = this.head;
}else{
// 链表头部不为空，node中的next指向当前链表头部
node.next = current;
// 确保最后一个元素指向新添加的元素，current指向当前元素的最后一个元素
current = this.getElementAt(this.size());
// 更新最后一个元素
this.head = node;
current.next = this.head;
}
}else{
// 链表其他位置插入元素
const previous = this.getElementAt(index - 1);
node.next = previous.next;
previous.next = node;
}
this.count ;
return true;
}
return false;
}- 重写移除链表元素函数(removeAt)
removeAt(index: number): any {
if(index >= 0 && index < this.count){
let current = this.head;
if (index === 0){
if(this.size() === 1){
//链表长度为1直接将链表头部指向undefined
this.head = undefined;
}else{
// 链表长度不为1，保存链表头部元素，将其从循环链表中移除
const removed = this.head;
// 链表元素变量指向链表尾部
current = this.getElementAt(this.size() - 1);
// 链表头部指向链表头部元素中的next
this.head = this.head.next;
// 链表尾部元素中的next指向新的链表头部
current.next = this.head;
// 更新链表元素的引用，用于返回当前移除的值
current = removed;
}
}else{
const previous = this.getElementAt(index - 1);
current = previous.next;
previous.next = current.next;
}
this.count--;
return current.element;
}
return undefined;
}完整代码请移步: CircularLinkedList.ts
编写测试代码
循环链表实现后，我们来测试下上述代码是否正常运行
代码语言：javascript复制const circularLinkedList = new CircularLinkedList();
circularLinkedList.push(11);
circularLinkedList.push(12);
circularLinkedList.push(13);
// 循环链表的0号位置插入元素
circularLinkedList.insert(10,0);
console.log(circularLinkedList.toString());
// 获取链表的最后一个元素
console.log(circularLinkedList.getElementAt(3))完整代码请移步: CircularLinkedListTest.js
有序链表的实现
有序链表也属于链表的一种变相实现，它不同于链表的是，插入链表的元素会通过一个元素比对函数，对要插入的元素和链表内的元素进行比较，将要插入的元素放到链表合适的位置。
实现思路
因为有序链表属于链表的一种变相，所以我们可以继承链表，只需要重写链表的插入函数实现获取插入元素正确位置函数即可。
- 实现获取插入元素正确位置函数（getIndexNextSortedElement）
- 声明链表元素变量，默认指向当前链表的头部元素
- 遍历整个链表，直至找到需要插入的元素位置
- 将要插入的元素和遍历到链表元素进行大小比较，计算出插入位置
- 如果整个链表遍历完后，仍没找到合适的位置则直接返回链表的末尾位置
- 重写插入元素函数(insert)
- 如果链表为空则直接调用往链表的0号位置插入元素
- 链表不为空，则调用getIndexNextSortedElement函数计算出正确的插入位置
- 调用insert函数将元素插入正确的位置
实现代码
我们有了实现思路，接下来我们将上述思路转化为代码：
- 新建OrderedList.ts文件，用于实现有序链表
- 声明OrderedList类，继承LinkedList类
export default class OrderedList<T> extends LinkedList<T>{
}- 声明Compare对象和defaultCompare函数，调用时如果不传比较函数时，用于比较要插入元素和链表中元素的大小
const Compare = {
LESS_THAN: -1,
BIGGER_THAN: 1
}
// 比较两个元素大小，如果a < b则返回-1，否则返回1
function defaultCompare(a: any, b: any) {
if(a === b){
return 0;
}
return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}- 在构造器，初始化相关变量
constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
super(equalsFn);
this.compareFn = compareFn;
}- 实现获取插入元素正确位置函数(getIndexNextSortedElement)
getIndexNextSortedElement(element: T) {
let current = this.head;
let i = 0;
// 遍历整个链表，直至找到需要插入元素的位置
for (; i < this.size() && current; i ) {
// 用compareFn函数比较传入构造函数的元素
const comp = this.compareFn(element, current.element);
// 要插入小于current的元素时，我们就找到了插入元素的位置
if (comp === Compare.LESS_THAN) {
return i;
}
// 继续下一轮遍历
current = current.next;
}
// 迭代完所有的元素没有找到符合条件的，则返回链表的最后一个元素位置
return i;
}- 重写插入函数(insert)
insert(element: T, index: number = 0): boolean {
if(this.isEmpty()){
// 链表为空直接调用父级的insert方法往0号元素插入元素
return super.insert(element, 0);
}
// 链表不为空，获取插入元素的正确位置
const pos = this.getIndexNextSortedElement(element);
// 得到位置后调用父级的插入方法往正确位置插入元素
return super.insert(element,pos);
}完整代码请移步: OrderedList.ts
编写测试代码
我们来测试下上面写的有序链表内的函数是否都正常工作
代码语言：javascript复制const orderedList = new OrderedList();
orderedList.insert(12);
orderedList.insert(11);
orderedList.insert(18);
orderedList.insert(1);
console.log(orderedList.toString());完整代码请移步：OrderedListTest.js
写在最后
- 文中如有错误，欢迎在评论区指正。
- 本文首发于掘金，未经许可禁止转载
参考资料
[1]
兔子舞: https://baike.baidu.com/item/兔子舞/2641271?fr=aladdin
[2]
数据结构:链表的基础知识: https://juejin.im/post/6844904067651600392
[3]
LinkedList.ts: https://github.com/likaia/JavaScript-test/blob/master/src/LinkedListTest/lib/LinkedList.ts
[4]
LinkedListTest.js: https://github.com/likaia/JavaScript-test/blob/master/src/LinkedListTest/LinkedListTest.js
[5]
DoublyLinkedList.ts: https://github.com/likaia/JavaScript-test/blob/master/src/LinkedListTest/lib/DoublyLinkedList.ts
[6]
DoublyLinkedListTest.js: https://github.com/likaia/JavaScript-test/blob/master/src/LinkedListTest/DoublyLinkedListTest.js
[7]
CircularLinkedList.ts: https://github.com/likaia/JavaScript-test/blob/master/src/LinkedListTest/lib/CircularLinkedList.ts
[8]
CircularLinkedListTest.js: https://github.com/likaia/JavaScript-test/blob/master/src/LinkedListTest/CircularLinkedListTest.js
[9]
OrderedList.ts: https://github.com/likaia/JavaScript-test/blob/master/src/LinkedListTest/lib/OrderedList.ts
[10]
OrderedListTest.js: https://github.com/likaia/JavaScript-test/blob/master/src/LinkedListTest/OrderedListTest.js
·END·
