前端算法系列之二:数据结构链表、双向链表、闭环链表、有序链表
2021/1/27 5:07:33
本文主要是介绍前端算法系列之二:数据结构链表、双向链表、闭环链表、有序链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
前言
上一次我们讲到了数据结构:栈和队列,并对他们的运用做了一些介绍和案例实践;我们也讲到了怎么简单的实现一个四则运算、怎么去判断标签是否闭合完全等等,anyway,今天接着和大家介绍一些数据结构:
上一篇:前端算法系列之一:时间复杂度、空间复杂度以及数据结构栈、队列的实现
链表
链表是一种怎么样的结构呢?链表就是一种可以把数据串联起来的结构,每个元素会有指向下一个元素的指针(末尾的没有普通链表),就像现实世界中的火车一样一节一节的串联起来;链表根据自身的指针指向又可以分为:单向链表、双向链表、循环链表;
链表首先会有一个表头,表头作为起始的指针,然后每一个元素我们称作为节点(node);每个节点有一个指向下一个节点的指针(next),直到链表的末尾指针会指向undefined;
链表的实现
1、节点
节点的创建和定义;每个节点会有一个保存自己数据的属性(element),然后有一个指针(next)
export class Node { constructor(element, next = null) { this.element = element; this.next = next; } }
2、链表的api
getElementAt(position): 获取某个位置的元素
append(element): 向链表末尾中添加元素
removeAt(idx): 移除某个元素
insert(element, position = 0, dir = 'before'): 向指定位置添加元素
insertAfter(element, position): 向指定的位置后面添加元素
size(): 链表的长度
remove(): 删除链表末端元素
removeAll(): 删除整个链表
isEmpty(): 检查链表是否为空
import { defaultEquals } from "../util.js"; import { Node } from './Node.js' export default class LinkedList { constructor(equalsFn = defaultEquals) { this.count = 0; this.head = null; this.equalsFn = equalsFn; } getElementAt(position) { if(position >= 0 && position <= this.count) { let node = this.head; for (let i = 0; i < position && !!node; i++) { node = node.next; } return node; } return undefined; } insertAfter(element, position) { return this.insert(element, position, 'after'); } size() { return this.count; } remove() { return this.removeAt(this.size() - 1); } removeAll() { this.count = 0; this.head = null; } isEmpty() { return this.size() === 0; } getHead() { return this.head; } }
3、链表末尾添加一个元素append;
append(element) { const node = new Node(element); let current = this.head; if(current == null) { this.head = node; } else { current = this.head; while (current.next != null) { current = current.next; } current.next = node } this.count++; return element; }
4、插入一个元素
insert(element, position = 0, dir = 'before') { if (element === undefined) { throw Error('缺少需要插入的元素'); return; } if (position >= this.count) { return this.append(element); } const node = new Node(element); const targetNode = dir === 'before' ? this.getElementAt(position - 1) : this.getElementAt(position); if (!targetNode) { let prev = this.head; this.head = node; node.next = prev; } else { let next; next = targetNode.next targetNode.next = node; node.next = next; } this.count++; return element; }
5、删除一个元素
removeAt(idx) { if (idx >= 0 && idx < this.count) { let current = this.head; if (idx === 0) { this.head = current.next; current.next = null; } else { let prev = this.getElementAt(idx - 1); current = prev.next; prev.next = current.next; } this.count--; return current.element; } return undefined; }
6、双向链表
单向链表元素指向都是一个方向的,也只能被单向递归搜索,而双向链表不仅仅有指向下一个元素的指针同时具有指向上一个元素的指针;
import LinkedList from "./LinkedList"; import {defaultEquals} from "../util"; import { DoubleNode } from "./DoubleNode"; export default class DoubleLinkedList extends LinkedList{ constructor(equalIsFn = defaultEquals){ super(equalIsFn); this.tail = null;// 队列尾部 } getElementAt(position) { if(position >= 0 && position <= this.count) { if (position > this.count/2) { let cur = this.tail; for (let i = this.count - 1; i > position; i--){ cur = cur.prev; } return cur; } else { return super.getElementAt(position) } } return undefined; } removeAll() { super.removeAll(); this.tail = null; } removeAt(position) { if (position >= 0 && position < this.count) { let cur = this.getElementAt(position); if(position === 0) { this.head = cur.next; cur.next = null; this.prev = null; } else if (position === this.count - 1) { this.tail = cur.prev; this.tail.next = null; cur.prev = null; } else { let prev = cur.prev; let next = cur.next; prev.next = next; next.prev = prev; cur.prev = null; cur.next = null; } this.count--; return cur.element; } return undefined; } }
队列末尾插入元素(append)
双向链表插入元素和单向比较类似,不同的是双向不仅要链接他的下级还得关联他的前一级;
append(element) { const node = new DoubleNode(element); if (!this.tail) { this.head = node; this.tail = node; } else { let cur = this.tail; cur.next = node; node.prev = cur; this.tail = node; } this.count++; return element; }
中间某个位置插入元素
insert(element, position = 0, dir = 'before'){ if (element === undefined) { throw Error('缺少需要插入的元素'); return; } if (position >= this.count) { return this.append(element); } const node = new DoubleNode(element); let cur; const targetNode = dir === 'before' ? this.getElementAt(position - 1) : this.getElementAt(position); if (!targetNode) { cur = this.head; node.next = cur; cur.prev = node; this.head = node; } else { let next; next = targetNode.next targetNode.next = node; node.prev = targetNode; node.next = next; next.prev = node; } this.count++; return element; }
移除某个元素也是上述相同,修改节点的前后指针就可以了,这里不再赘述,详情看源码
https://github.com/JasonCloud/DataStructuresAndAlgorithms
闭环链表
闭环链表也称环,是一个闭合的结构,尾部会指向头部
有序链表
有序链表就是在append元素的时候进行排序加入从而得到一个有顺序的链表,比较函数可以根据实例化的时候传入比较函数equalIsFn;
这篇关于前端算法系列之二:数据结构链表、双向链表、闭环链表、有序链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-26uniapp 哪里看mp-html 是否有引用-icode9专业技术文章分享
- 2024-09-26uniapp 怎么显示html 代码-icode9专业技术文章分享
- 2024-09-26uniapp 有没有自带mp-html 吗-icode9专业技术文章分享
- 2024-09-25前端高频大厂面试真题解析与实战教程
- 2024-09-25前端高频面试题详解:新手必看指南
- 2024-09-25前端高频面试真题详解与实战攻略
- 2024-09-25前端大厂面试真题及答案详解:从零开始的初级面试攻略
- 2024-09-25前端面试实战:新手必备技巧与案例解析
- 2024-09-25前端面试题及答案详解:初级面试必备
- 2024-09-25前端面试真题及答案详解:适合入门与初级用户