链表作为一种数据结构,它存放着有序元素的集合。元素与元素之间通过指针连接,因此在链表中添加或删除元素只需要修改指针的指向即可,执行速度相比数组有得到显著的提升。 现实生活中也有许多使用到链表的例子,例如兔子舞,每个人勾肩搭背组合而成,其中人相当于链表中的元素,勾肩搭背的手相当于链接每个人的指针,在队列中加入一个人,只需要找到想加入的点,断开连接,插入一个人再重新连接起来。 本文将详解链表以及链表其他变相的实现思路并使用TypeScript将其实现,欢迎各位感兴趣的开发者阅读本文。
本文主要讲解链表的代码实现,对链表还不是很了解的开发者可以移步我的另一篇文章:数据结构:链表的基础知识。
在实现链表之前,我们先来看看数组与链表的区别都有哪些。 数组可能是最常用的一种数据结构,每种语言都实现了数组,元素在内存中是连续存放的,因此数组提供了一个非常方便的[]方法来访问其元素。 链表存储有序元素的集合,链表中的元素在内存中并非连续存放,每个元素由一个存储元素本身的结点和一个指向下一个元素的指针组成,因此增加或删除链表内的元素只需要改变指针指向即可。 我们来总结下链表与数组各自的优点:
链表的优点:元素通过指针连接,改变链表内的元素只需要找到元素改变其指针即可,因此数据需要频繁修改时,使用链表作为数据结构是最优解决方案。数组的优点:元素连续存放在内存中,访问元素可以直接通过元素下标来访问,因此数据需要频繁查询时,使用数组作为其数据结构是最优解决方案。
上面我们总结了它们的优点,接下来我们来看下它们各自的缺点:
链表的缺点:由于链表是通过指针连接的,我们只能直接拿到链表头部的元素,要想访问其他元素需要从头遍历整个链表才能找到我们想找的元素。因此数据需要频繁查询时,使用链表将适得其反。数组的缺点:由于元素是连续存放在内存中的,改变数组内的元素时,需要调整其他元素的位置。因此数据需要频繁修改时,使用数组将适得其反。
链表是由指针将元素连接到一起,根据链表的特性,我们可以知道要实现一个链表必须必备以下方法:
经过上述分析后,我们知道了链表的实现思路,接下来我们就将上述思路转化为代码:
// 助手类: 用于表示链表中的第一个以及其他元素
export class Node<T>{
element: T;
next: any;
// 默认传一个元素进来
constructor (element: T) {
this.element = element;
this.next = undefined;
}
}
// 默认验证函数
export function defaultEquals(a: any,b: any) {
return a === b;
}
// @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(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(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(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(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(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(element: T) {
// 获取element的索引,移除索引位置的元素
this.removeAt(this.indexOf(element))
}
// 获取链表长度
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
链表实现后,接下来我们来测试下链表中的每个函数是否正常工作
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)。 接下来我们来捋一下,上述需要重写函数的实现思路:
我们已经捋清了实现思路,接下来我们将上述实现思路转换为代码: 实现双向链表之前,我们需要对链表的辅助类进行修改。
export class DoublyNode<T> extends Node<T>{
prev: any;
constructor(element: T, next?: any, prev?: any) {
// 调用Node类的构造函数
super(element,next);
// 新增prev属性,指向链表元素的上一个元素
this.prev = prev;
}
}
export default class DoublyLinkedList extends LinkedList{
}
private tail: any;
constructor(equalsFn = defaultEquals) {
// 调用Node类的构造函数
super(equalsFn);
// 新增属性,用于指向链表的最后一个元素
this.tail = undefined;
}
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(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(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(){
return this.tail;
}
clear() {
super.clear();
this.tail = undefined;
}
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
双向链表实现后,我们测试下双线链表中的函数是否都正常工作。
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。
循环链表相对于链表,改动地方较少,在首、尾插入或删除元素时,需要更改其指针指向,因此我们只需要继承链表,然后重写插入和移除方法即可。
我们捋清思路后,将上述思路转化为代码
export default class CircularLinkedList<T> extends LinkedList<T>{
}
constructor(equalsFn = defaultEquals) {
super(equalsFn);
}
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(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
循环链表实现后,我们来测试下上述代码是否正常运行
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
有序链表也属于链表的一种变相实现,它不同于链表的是,插入链表的元素会通过一个元素比对函数,对要插入的元素和链表内的元素进行比较,将要插入的元素放到链表合适的位置。
因为有序链表属于链表的一种变相,所以我们可以继承链表,只需要重写链表的插入函数实现获取插入元素正确位置函数即可。
我们有了实现思路,接下来我们将上述思路转化为代码:
export default class OrderedList<T> extends LinkedList<T>{
}
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(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(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
我们来测试下上面写的有序链表内的函数是否都正常工作
const orderedList = new OrderedList();
orderedList.insert(12);
orderedList.insert(11);
orderedList.insert(18);
orderedList.insert(1);
console.log(orderedList.toString());
完整代码请移步:OrderedListTest.js