discuz图片网站模板,郑州官网网络营销外包,wordpress评论分页不显示不出来,担路网络科技有限公司的证书前言上一次我们讲到了数据结构#xff1a;栈和队列#xff0c;并对他们的运用做了一些介绍和案例实践#xff1b;我们也讲到了怎么简单的实现一个四则运算、怎么去判断标签是否闭合完全等等#xff0c;anyway#xff0c;今天接着和大家介绍一些数据结构#xff1a;链表链…前言上一次我们讲到了数据结构栈和队列并对他们的运用做了一些介绍和案例实践我们也讲到了怎么简单的实现一个四则运算、怎么去判断标签是否闭合完全等等anyway今天接着和大家介绍一些数据结构链表链表是一种怎么样的结构呢链表就是一种可以把数据串联起来的结构每个元素会有指向下一个元素的指针(末尾的没有普通链表)就像现实世界中的火车一样一节一节的串联起来链表根据自身的指针指向又可以分为单向链表、双向链表、循环链表链表首先会有一个表头表头作为起始的指针然后每一个元素我们称作为节点(node);每个节点有一个指向下一个节点的指针(next)直到链表的末尾指针会指向undefined链表的实现1、节点节点的创建和定义每个节点会有一个保存自己数据的属性(element)然后有一个指针(next)export class Node {constructor(element, next null) {this.element element;this.next next;}}2、链表的apigetElementAt(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.jsexport 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 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.nexttargetNode.next node;node.next next;}this.count;return element;}5、删除一个元素removeAt(idx) {if (idx 0 idx 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 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.nexttargetNode.next node;node.prev targetNode;node.next next;next.prev node;}this.count;return element;}移除某个元素也是上述相同修改节点的前后指针就可以了这里不再赘述详情看源码闭环链表闭环链表也称环是一个闭合的结构尾部会指向头部有序链表有序链表就是在append元素的时候进行排序加入从而得到一个有顺序的链表比较函数可以根据实例化的时候传入比较函数equalIsFn
