JavaScript算法学废宝典--前置技能一--链表

news/2025/1/16 4:51:57/

链表是由一组节点组成的集合。每个节点都使用一个对象的引用指向它的后继，指向另一个节点的引用叫做链。数组元素靠它们的位置进行引用，链表元素则是靠相互之间的关系进行引用。

基于对象设计一个链表

Node类

Node类包含两个属性：element保存节点上的数据，next保存指向下一个节点的链接，使用构造函数来创建节点。

function Node(element){this.element = element;this.next = null;
}

LinkedList类

该类的功能包括插入删除节点，在列表中查找给定的值。该类也是一个构造函数，链表只有一个属性，使用一个Node对象来保存该链表的头结点。

function LList(){this.head = new Node("head");this.find = find;this.insert = insert;this.display = display;
}

插入新节点

向链表中插入新节点时，需要明确指出要在哪个节点前面或者后面插入，这里需要先创建一个辅助方法find()用来查找给定数据并返回给定数据对应的节点。
find()方法演示了如何在链表上进行移动。首先，创建一个新节点，并将链表的头节点赋给这个新创建的节点。然后在链表上进行循环，如果当前节点的 element属性和我们要找的信息不符，就从当前节点移动到下一个节点。如果查找成功，该方法返回包含该数据的节点，否则，返回null。

function find(item){var currNode = this.head;while(currNode.element!=item){currNode = currNode.next;}return currNode;
}

通过find()找到“后面”的节点，就可以通过insert()方法将新节点插入链表中了，首先将新节点的next属性设置为“后面”节点的next属性对应的值，然后设置“后面”节点的next属性指向新节点。

function insert(newElement,item){var newNode = new Node(newElement);var current = this.find(item);newNode.next = current.next;current.next = newNode;
}

定义一个display()方法显示链表中的元素：

function display(){var currNode = this.head;while(!(currNode.next == null)){console.log(currNode.next.element);currNode = currNode.next;}
}

汇总以上全部代码并进行测试：

function Node(element){this.element = element;this.next = null;
}
function LList(){this.head = new Node("head");this.find = find;this.insert = insert;this.display = display;
}
function find(item){var currNode = this.head;while(currNode.element!=item){currNode = currNode.next;}return currNode;
}
function insert(newElement,item){var newNode = new Node(newElement);var current = this.find(item);newNode.next = current.next;current.next = newNode;
}
function display(){var currNode = this.head;while(!(currNode.next == null)){console.log(currNode.next.element);currNode = currNode.next;}
}
var cities = new LList();
cities.insert("Conway","head");
cities.insert("Russellville","Conway");
cities.insert("Alma","Russellville");
cities.display();//Conway  Russellville  Alma

从链表中删除一个节点

当删除节点时，需要先找到待删除节点前面的节点。找到后修改它的next属性，使其执行待删除节点的下一个节点，通过一个方法findPrevious()来查找指定节点的前一个节点。
该方法遍历链表检查每一个节点的下一个节点是否是待删除节点，找到就返回该节点。

function findPrevious(item){var currNode = this.head;while(!(currNode.next == null) && (currNode.next.element != item)){currNode = currNode.next;}return currNode;
}

接下来是删除方法remove()

function remove(item){var prevNode = this.findPrevious(item);if(!(prevNode.next == null)){prevNode.next = prevNode.next.next;}
}

修改LList类添加两个新加的方法

function LList(){this.head = new Node("head");this.find = find;this.insert = insert;this.display = display;this.findPrevious = findPrevious;this.remove = remove;
}

汇总以上全部代码并进行测试：

function Node(element){this.element = element;this.next = null;
}
function LList(){this.head = new Node("head");this.find = find;this.insert = insert;this.display = display;this.findPrevious = findPrevious;this.remove = remove;
}
function find(item){var currNode = this.head;while(currNode.element!=item){currNode = currNode.next;}return currNode;
}
function insert(newElement,item){var newNode = new Node(newElement);var current = this.find(item);newNode.next = current.next;current.next = newNode;
}
function display(){var currNode = this.head;while(!(currNode.next == null)){console.log(currNode.next.element);currNode = currNode.next;}
}
function findPrevious(item){var currNode = this.head;while(!(currNode.next == null) && (currNode.next.element != item)){currNode = currNode.next;}return currNode;
}
function remove(item){var prevNode = this.findPrevious(item);if(!(prevNode.next == null)){prevNode.next = prevNode.next.next;}
}
var cities = new LList();
cities.insert("Conway","head");
cities.insert("Russellville","Conway");
cities.insert("Carlisle","Russellville");
cities.insert("Alma","Carlisle");
cities.display();//Conway Russellville Carlisle Alma
cities.remove("Carlisle");
console.log('删除Carlisle==============')//删除Carlisle==============
cities.display();//Conway Russellville Alma

双向链表

尽管从链表的头节点遍历到尾节点很简单，但反过来，从后向前遍历则没那么简单。通过给 Node 对象增加一个属性，该属性存储指向前驱节点的链接，这样就容易多了。此时向链表插人一个节点需要更多的工作，我们需要指出该节点正确的前驱和后继。但是在从链表中删除节点时，效率提高了，不需要再查找待删除节点的前驱节点了。
为Node类增加一个previous属性：

function Node(element){this.element = element;this.next = null;this.previous = null;}

修改LList类，删除查找上一个节点的方法findPrevious：

function LList(){this.head = new Node("head");this.find = find;this.insert = insert;this.display = display;this.remove = remove;this.dispReverse = dispReverse;this.findLast = findLast;
}

修改insert方法，赋值previous属性，设置该节点的前驱：

function insert(newElement,item){var newNode = new Node(newElement);var current = this.find(item);newNode.next = current.next;newNode.previous = current;current.next = newNode;}

双向链表的 remove()方法比单向链表的效率更高，因为不需要再查找前驱节点了。首先需要在链表中找出存储待删除数据的节点，然后设置该节点前驱的 next 属性，使其指向待删除节点的后继，设置该节点后继的 previous 属性，使其指向待删除节点的前驱。

function remove(item){var currNode = this.find(item);if(!(currNode.next==null)){currNode.previous.next = currNode.next;currNode.next.previous = currNode.previous;currNode.next = null;currNode.previous = null;}
}

设置findLast()方法查找链表中的最后一个节点，用来辅助反序显示链表元素这类任务：

function findLast(){var currNode = this.head;while(currNode.next!=null){currNode = currNode.next;}return currNode;
}

反序显示链表中的元素：

function dispReverse(){var currNode = this.head;currNode = this.findLast();while(!(currNode.previous == null)){console.log(currNode.element);currNode = currNode.previous;}
}

汇总以上全部代码并进行测试：

function Node(element){this.element = element;this.next = null;this.previous = null;
}
function LList(){this.head = new Node("head");this.find = find;this.insert = insert;this.display = display;this.remove = remove;this.dispReverse = dispReverse;this.findLast = findLast;
}
function dispReverse(){var currNode = this.head;currNode = this.findLast();while(!(currNode.previous == null)){console.log(currNode.element);currNode = currNode.previous;}
}
function findLast(){var currNode = this.head;while(currNode.next!=null){currNode = currNode.next;}return currNode;
}
function find(item){var currNode = this.head;while(currNode.element!=item){currNode = currNode.next;}return currNode;
}
function insert(newElement,item){var newNode = new Node(newElement);var current = this.find(item);newNode.next = current.next;newNode.previous = current;current.next = newNode;
}
function display(){var currNode = this.head;while(!(currNode.next == null)){console.log(currNode.next.element);currNode = currNode.next;}
}
function remove(item){var currNode = this.find(item);if(!(currNode.next==null)){currNode.previous.next = currNode.next;currNode.next.previous = currNode.previous;currNode.next = null;currNode.previous = null;}
}var cities = new LList();
cities.insert("Conway","head");
cities.insert("Russellville","Conway");
cities.insert("Carlisle","Russellville");
cities.insert("Alma","Carlisle");
cities.display();//Conway Russellville Carlisle Alma
cities.remove("Carlisle");
console.log('删除Carlisle==============')//删除Carlisle==============
cities.display();//Conway Russellville Alma
console.log('反序==============')//反序==============
cities.dispReverse();//Alma Russellville Conway

循环链表

循环链表和单向链表相似，区别是在创建循环链表的时候，每个头节点的next属性指向它的本身，即：

head.next = head

这样每个节点的next属性都指向链表的头节点，链表的尾节点也指向头节点，形成了循环链表。
注意修改判断条件不然会进入死循环。例如：

function display(){var currNode = this.head;while(!(currNode.next == null) && currNode.next.element != "head"){console.log(currNode.next.element);currNode = currNode.next;}
}

全部代码

function Node(element){this.element = element;this.next = null;
}
function LList(){this.head = new Node("head");this.head.next = this.head;this.find = find;this.insert = insert;this.display = display;this.findPrevious = findPrevious;this.remove = remove;
}
function find(item){var currNode = this.head;while(currNode.element!=item){currNode = currNode.next;}return currNode;
}
function insert(newElement,item){var newNode = new Node(newElement);var current = this.find(item);newNode.next = current.next;current.next = newNode;
}
function display(){var currNode = this.head;while(!(currNode.next == null) && currNode.next.element != "head"){console.log(currNode.next.element);currNode = currNode.next;}
}
function findPrevious(item){var currNode = this.head;while(!(currNode.next == null) && (currNode.next.element != item) && currNode.next.element != "head"){currNode = currNode.next;}return currNode;
}
function remove(item){var prevNode = this.findPrevious(item);if(!(prevNode.next == null)){prevNode.next = prevNode.next.next;}
}var cities = new LList();
cities.insert("Conway","head");
cities.insert("Russellville","Conway");
cities.insert("Carlisle","Russellville");
cities.insert("Alma","Carlisle");
cities.display();
cities.remove("Carlisle");
console.log('删除Carlisle==============')
cities.display();

http://www.ppmy.cn/news/1060263.html

相关文章

如何快速从逆境脱身

如何快速从逆境脱身

近期发生的新闻热点再度引发公众对稳定情绪和心理健康的关注。有时候我们遇到的最大的敌人，不是运气也不是能力，而是失控的情绪和口无遮拦的自己。如何在工作中保持稳定的情绪？谈谈你的看法。 方向一：分享工作中让你有强烈情绪波…
阅读更多...
vue3权限管理——（路由权限）动态路由设置

vue3权限管理——（路由权限）动态路由设置

1.大概思路 设置基础路由login和home等页面；登录后从后端获取user,token,rights等数据，并将数据同时存储到vuex和sessionStorage中将后端获取的权限数据（作为不同用户显示不同菜单及不同路由的依据）和路由页面进行映射&#xff1…
阅读更多...
Midjourney 完整版教程（从账号注册到设计应用）

Midjourney 完整版教程（从账号注册到设计应用）

目录 一、Midjourney 介绍 二、Midjourney 的AI出图示例 三、手把手教你上手Midjourney 1、账号&初始化 1.1 账号注册登录 1.2 账号付费 1.3 账号初始化 2、Midjourney的基础设置 3、Midjourney 出图步骤。 （一）直接描述出图 （二）垫图生图。 4、Midjourney的…
阅读更多...
Git企业开发控制理论和实操-从入门到深入（一）｜为什么需要Git｜Git的安装

Git企业开发控制理论和实操-从入门到深入（一）｜为什么需要Git｜Git的安装

前言 那么这里博主先安利一些干货满满的专栏了！ 首先是博主的高质量博客的汇总，这个专栏里面的博客，都是博主最最用心写的一部分，干货满满，希望对大家有帮助。 高质量博客汇总https://blog.csdn.net/yu_cblog/cate…
阅读更多...
淘宝API技术解析，实现按图搜索淘宝商品

淘宝API技术解析，实现按图搜索淘宝商品

淘宝提供了开放平台接口（API）来实现按图搜索淘宝商品的功能。您可以通过以下步骤来实现： 1. 获取开放平台的访问权限：首先，您需要在淘宝开放平台创建一个应用，获取访问淘宝API的权限。具体的申请步骤和要求…
阅读更多...
Java中Comparable和Comparator有什么区别？

Java中Comparable和Comparator有什么区别？

1. 字面含义不同 Comparable字面意思是“具有比较能力”，Comparator字面意思是“比较器”。 2. 用法不同 Comparable用法：对需要排序的类，实现Comparable接口，重写compareTo()方法。 Comparator用法：创建自定义比较…
阅读更多...
题解：ABC279D-Freefall

题解：ABC279D-Freefall

题解：ABC279D-Freefall 题目 链接：Atcoder。 链接：洛谷。 难度 算法难度：C。 思维难度：A。 调码难度：C。 综合评价：普及/提高。 算法 模拟。 思路 引入3个数组：u&#x…
阅读更多...
小程序微信营销活动策划成功的关键因素

小程序微信营销活动策划成功的关键因素

随着移动互联网的发展，小程序已经成为许多企业进行数字化营销的重要渠道之一。而在小程序内开展微信营销活动，是提升用户参与度、增强品牌影响力的有效方法。然而，要使这些活动取得成功，需要考虑诸多因素。本文将深入探讨小程序微…
阅读更多...
最新文章

Copyright @ 2022~2023