郑州做网站建设公司排名,山东网站建设和游戏开发的公司排名,如果一个网站的域名是,node怎么做网站什么是链表#xff1f; 链表和数组的对比#xff1a;在大多数语言中#xff0c;数组的大小是固定的#xff0c;从数组的起点或中间添加或删除元素的成本很高#xff0c;因为需要移动元素。链表中的每一个元素在内存中不是连续放置的#xff0c;和它左右两侧元素是没有关系…什么是链表 链表和数组的对比在大多数语言中数组的大小是固定的从数组的起点或中间添加或删除元素的成本很高因为需要移动元素。链表中的每一个元素在内存中不是连续放置的和它左右两侧元素是没有关系的。每个元素有一个存储元素本身的节点和指向下一个元素的引用组成。相对于数组链表的好处在于添加或删除元素的时候不需要移动其它元素。在数组中我们可以直接访问任何位置的任何元素而要想访问链表中的某一个元素则需要从起点链表头开始迭代链表直到找到所需的元素。举个栗子 一列火车是由一系列车厢组成的。每节车厢或车皮都相互连接你很容易分离一节车箱改变它的位置、添加或移除它。每节车厢相当于链表的元素车厢间的对接扣就是元素的引用。 创建一个链表类 const defaultCompare function (a, b) { // 一个比较函数 if (a b) return 0; return a b ? -1 : 1; } class Node { // 一个助手类用来表示我们想要添加到链表中的元素 constructor(element, next) { this.element element; // 元素的值 this.next next; // 指向链表中下一个元素的指针 } } class LinkedList { // 链表类 constructor(equalsFn defaultEquals) { this.equalsFn equalsFn; // 比较链表中的元素是否相等默认ab this.count 0; // 链表中的元素数量 this.head undefined; // 表头 } } 创建几个链表的方法 向链表的尾部添加元素push(element) {const node new Node(element); // 创建node项let current; // 声明一个指向链表中的临时项 if (this.head undefined) { // 如果链表头为空即链表为空 this.head node; // 直接让表头等于当前元素就好了下一项next未传因此为undefined } else { current this.head; // 先让current等于第一个元素 while (current.next ! null) { // 只要当前元素的下一项元素不是假的便继续循环 current current.next; } current.next node; // 找到最后一个元素后让它的下一个元素等于传进来的元素 } this.count;// 最后把总长度自增就好了 } 首先初始化node类把element作为值传入。尾部添加元素分为两种情况一种是链表为空一种是链表有值在后者时因为链表只有链表头的引用因此在向链表尾部添加元素时我们需要循环列表直到找到最后一个元素为此 我们需要一个指向链表中current项的变量。如果链表头没值表示在向链表添加第一个元素直接让表头等于当前元素就好了下一项的引用next未传因此为undefined然后就是第二种情况首先让current等于链表头然后循环访问列表直到找到最后一个元素然后就是让最后一个元素的下一项的引用指向想要添加到链表的节点。最后把总长度自增就好了从特定位置移除一个元素removeAt(index) {if (index 0 index this.count) { // 检查越界值let current this.head; if (index 0) { // 如果是表头 this.head current.next; // 就让表头等于下一个引用 } else { let previous for (let i 0; i index i) { // 嗯开始迭代把~~~ previous current; current current.next; } previous.next current.next; // 上一个的下一个等于现在的下一个现在内心os:我是谁我在哪当前节点就会被丢弃在计算机内存中等着被垃圾回收器移除 } this.count--;// 长度自减 return current.element; // 返回移除的元素 } return undefined; } 由于该方法需要得到移除元素的index位置我们需要验证该index是从0到链表的长度之间的。如果不是就返回undefined。如果移除的是链表中的第一个元素就要让head指向列表的第二个元素。我们将current变量创建一个对链表中第一个元素的引用。这样current变量就是对链表中第一个元素的引用。这时候如果如果把head赋为current.next就会移除第一个元素。我们也可以直接把head赋为head.next不使用current。如果我们要移除的是链表的最后一个元素或者中间的某个元素。就需要对链表进行迭代直到到达目标位置。在到达目标位置后current变量就会变成我们想要从链表中移除的节点。因此要从链表中移除当前元素要做的就是将previous.next和current.next链接起来。这样当前节点就会被丢弃在计算机内存中等着被垃圾回收器清除。循环迭代链表直到目标位置getElementAt(index) {if (index 0 index this.count) return undefined; // 检查越界值 let node this.head; // 默认等于表头 for (let i 0; i index node ! null; i) { // 嗯开始迭代把~~~ node node.next; } return node; } 在remove方法中我们需要迭代整个链表直到到达我们的目标索引index(位置)。循环到目标index的代码片段在链表方法中会经常用到。因此我们可以将这部分逻辑独立为单独的办法这样就可以在不同的地方复用它。然后我们可以使用刚刚创建的getElementAt方法来重构remove方法if(index0){// 第一个位置的逻辑
} else {const previous this.getElementAt(index - 1); current previous.next; previous.next current.next; } this.count--; 在任何位置插入元素insert(element, index) {if (index 0 index this.count) { // 边界处理const node new Node(element); // 实例化当前元素 if (index 0) { // 如果插在表头 const current this.head;// 声明一个变量等于原来的表头 node.next current;// 传入元素的下一个引用等于current this.head node; // 当前表头等于传入的元素 } else { const previous this.getElementAt(index - 1);// 找到传入索引的上一个值 previous.next node;// 上一个的引用等于传入的值 node.next previous.next;// 传入值的下一个引用等于上一个的下一个引用 } this.count;// 总长度自增 return true; // 最后返回true } return false; // 如果位置未找到返回false } 先惯例的做一下边界处理。首先如果是插在链表头我们先声明一个变量等于原来的链表头再让插入元素的先一个引用等于原来的current变量最后让当前表头等于传入的元素。如果是在链表中间或者末尾我们需要用getElementAt方法先找到目标位置的上一个元素然后让上一个的引用等于传入的值。再把传入值的下一个引用等于上一个的下一个引用。最后一定记得把总长度加一返回true返回一个元素的位置indexOf(element) {let current this.head; // 等于表头for (let i 0; i this.size() current ! null; i) { // 循环迭代所有元素 if (this.equalsFn(element, current.element)) { // 找到和当前元素相等的第一个元素 return i;// 返回索引 } current current.next;// 如果不相等就继续迭代下一个 } return -1; // 如果都没找到就返回-1 } indexOf方法接收一个元素的值如果在链表中找到了它就返回元素的位置否则返回-1。一如既往需要一个变量来帮助我们循环访问列表。该变量是current它的初始值是head然后迭代元素从链表头开始直到链表长度为止。为了确保不会发生运行时错误我们可以验证一下current变量是否为null或undefined。循环迭代所有元素直到找到和当前元素相等的第一个元素返回它的所在位置如果没找到就返回-1移除传入的元素remove(element) { const index this.indexOf(element); // 先找到这个元素的第一个索引return this.removeAt(index); // 利用删除指定位置元素的方法搞掉它 } 我们已经有了一个用来移除给定位置元素的方法也有了indexOf方法。利用indexOf方法找到它的位置利用删除指定位置元素的方法搞掉它。检查是否为空长度获取链表头isEmpty() {return this.size() 0;}size() {return this.count; } 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; // 最后把这个字符串返回 } 首先如果链表为空我们就返回一个空字符串。如果有值我们就用链表第一个元素的值来初始化方法最后返回的字符串。然后我们迭代链表中的所有其它元素将元素值添加到字符串上。最后把这个字符串返回。最后 今天的随手笔记就记到这里了等有时间我会再写一篇关于链表的各种增强版本。总之在我阅读完这一章后觉得链表相比数组更适合做增删操作而数组更适合存储一些比较固定不变的有序集合。转载于:https://www.cnblogs.com/xingyongwang/p/11125934.html
