用JavaScript实现链表

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了用JavaScript实现链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7754字，纯文字阅读大概需要12分钟。

内容图文

什么是链表

链表是一种动态的数据结构，用来存储一系列有序的元素。每个元素由一个存储元素本身的节点和一个指向下一个元素的指针构成。
技术分享图片

与数组的区别在于

链表分配内存空间灵活，并非保存在连续的存储空间中。
且链表不提供利用特定索引进行访问。因此，如果需要链表表中的第三个元素，则必须遍历第一个和第二个节点才能到得到它。
当要移动或删除元素时，只需要修改相应元素上的指针就可以了。对链表元素的操作要比对数组元素的操作效率更高。

要实现链表数据结构，关键在于保存head元素（即链表的头元素）以及每一个元素的next指针，有这两部分我们就可以很方便地遍历链表从而操作所有的元素。

（详见JavaScript数据结构——链表的实现与应用）
单向链表具体实现

创建一个辅助类，来描述链表中的节点

        let?Node?=?function(element){
????this.element?=?element;?//?属性1:保存节点值
????this.next?=?null;?//?属性2:next指针
}

或者写成这样

        class?Node?{
????constructor(element)?{
????????this.element?=?element;
????????this.next?=?null;?
????}
}

搭链表类的骨架/属性+方法

        class?LinkedList{
????constructor(){
????????this.length?=?0;
????????this.head?=?null;
????}
????append(element){}???//?向链表尾部中添加新节点
????insert(position,?element){}?//?向链表的指定位置插入节点
????removeAt(position){}????//?删除链表中指定位置的元素,并返回这个元素的值
????remove(element){}???//?删除链表中对应的元素
????indexOf(element){}??//?在链表中查找给定元素的索引
????getElementAt(position){}????//?返回链表中索引对应的元素
????isEmpty(){}?//判断链表是否为空
????size(){}????//?返回链表的长度
????getHead(){}?//?返回链表的头元素
????clear(){}???//?清空链表
????toString(){}????//?辅助方法,按指定格式输出链表中的所有元素,方便验证结果
}

getElementAt()方法，返回链表中索引对应的元素

        ????getElementAt(position){
????????if?(position?<?0?||?position?>=?this.length)
????????????return?null;
????????let?current?=?this.head;
????????for(let?i=0;?i<position;?i++){
????????????current?=?current.next;?//?next()获得匹配元素集合中每个元素紧邻的同胞元素。(jQuery)
????????}
????????return?current;
????}

append()方法，向链表尾部中添加新节点

        ????append(element){
????????let?node?=?new?Node(element);
????????//?如果当前链表为空,则将head指向node
????????if?(this.head?===?null){
????????????this.head?=?node;
????????}else{
????????????//?否则在链表尾部元素后添加新元素
????????????let?current?=?this.getElementAt(this.length?-?1);
????????????current.next?=?node;
????????}
????????this.length++;
????}

insert()方法，向链表的指定位置插入节点

        ????insert(position,?element){?//?向链表的指定位置插入节点
????????//?判断position是否超出边界
????????if?(position?<?0?||?position?>?this.length)
????????????return?false;
????????let?node?=?new?Node(element);
????????if?(position?===?0){
????????????node.next?=?this.head;
????????????this.head?=?node;
????????}else{
????????????let?previous?=?this.getElementAt(position?-?1);
????????????node.next?=?previous.next;
????????????previous.next?=?node;
????????}
????????this.length++;
????????return?true;
????}

removeAt()方法，删除链表中指定位置的元素,并返回这个元素的值

        ????removeAt(position){
????????//?判断position合法
????????if?(position?<?0?||?position?>?this.length)
????????return?null;?//?找不到
????????let?current?=?this.head;
????????if?(position?===?0){
????????????this.head?=?current.next;
????????}else{
????????????let?previous?=?this.getElementAt(position?-?1);
????????????current?=?previous.next;
????????????previous.next?=?current.next;
????????}
????????this.length--;
????????return?current.element;
????}

如果当前链表只有一个节点，那么下一个节点为null，此时将head指向下一个节点等同于将head设置成null，删除之后链表为空。被删除的节点由于再也没有其它部分的引用而被丢弃在内存中，等待垃圾回收器来清除。

indexOf()方法，查找并返回给定元素在链表中的索引位置

        ????indexOf(element){
????????let?current?=?this.head;
????????for(let?i=0;?i<this.length;?i++){
????????????if(current.element?===?element)
????????????????return?i;
????????????current?=?current.next;
????????}
????????return?-1;?//?找不到
????}

remove()方法，删除并返回链表中对应的元素

        ????remove(element){?
????????let?index?=?this.indexOf(element);
????????return?this.removeAt(index);
????}

isEmpty()方法，判断链表是否为空

        ????isEmpty(){
????????return?this.length?===?0; // 也可用head===null
????}

clear()方法，清空链表

        ????clear(){
????????this.head?=?null;
????????this.length?=?0;
????}

一些测试用例

        ????????let?linkedList?=?new?LinkedList();
????????//?测试用例1
????????linkedList.append(10);
????????linkedList.append(15);
????????linkedList.append(20);
????????console.log(linkedList.toString());
????????//?测试用例2
????????linkedList.insert(0,?9);
????????linkedList.insert(2,?11);
????????linkedList.insert(5,?25);
????????console.log(linkedList.toString());
????????//?测试用例3
????????console.log(linkedList.removeAt(0));
????????console.log(linkedList.removeAt(1));
????????console.log(linkedList.removeAt(3));
????????console.log(linkedList.toString());
????????//?测试用例4
????????console.log(linkedList.indexOf(20));
????????//?测试用例5
????????linkedList.remove(20);
????????//?测试用例6
????????console.log(linkedList.toString());
????????//?测试用例7
????????linkedList.clear();
????????console.log(linkedList.size());

双向链表具体实现
单向链表中每一个元素只有一个next指针，用来指向下一个节点，我们只能从链表的头部开始遍历整个链表，任何一个节点只能找到它的下一个节点，而不能找到它的上一个节点。
双向链表中的每一个元素拥有两个指针，一个用来指向下一个节点，一个用来指向上一个节点。在双向链表中，除了可以像单向链表一样从头部开始遍历之外，还可以从尾部进行遍历。下面是双向链表的数据结构示意图：
技术分享图片

由于双向链表具有单向链表的所有特性，因此我们的双向链表类可以继承自前面的单向链表类，不过辅助类Node需要添加一个prev属性，用来指向前一个节点。

        class?Node?{
????constructor(element)?{
????????this.element?=?element;?//?属性1:保存节点值
????????this.next?=?null;?//?属性2:next指针,指向后一个节点
????????this.prev?=?null;?//?属性3:prev指针,指向前一个节点
????}
}

双向链表类的基本骨架
继承了LinkedList类，其中的一些方法需要重定义

        class?DoubleLinkedList?extends?LinkedList{
????constructor(){
????????super();
????????this.tail?=?null;
????}
    getTail(){}
}

append()方法

        ????append(element){
????????let?node?=?new?Node(element);
????????//?如果链表为空,则将head和tail都指向当前添加的节点
????????if?(this.head?===?null){
????????????this.head?=?node;
????????????this.tail?=?node;
????????}else{
????????????//?否则将当前节点添加到链表的尾部
????????????this.tail.next?=?node;
????????????node.prev?=?this.tail;
????????????this.tail?=?node;
????????}
????????this.length++;
????}

getElementAt()方法，如果要查找的元素的索引号大于链表长度的一半,则从链表的尾部开始遍历

        ????getElementAt(position){?//?如果要查找的元素的索引号大于链表长度的一半,则从链表的尾部开始遍历
????????if?(position?<?0?||?position?>=?this.length)
????????????return?null;
????????if?(position?>?Math.floor(this.length?/2)){
????????????let?current?=?this.tail;
????????????for(let?i=this.length-1;?i>position;?i--){
????????????????current?=?current.prev;
????????????}
????????????return?current;
????????}else{
????????????return?super.getElementAt(position);
????????}
????}

insert()方法

        ????insert(position,?element){
????????if?(position?<?0?||?position?>?this.length)
????????????return?false;
????????if(position?===?this.length){
????????????this.append(element);
????????}else{
????????????let?node?=?new?Node(element);
????????????//?插到头部
????????????if(position?===?0){
????????????????if(this.head?===?null){
????????????????????this.head?=?node;
????????????????????this.tail?=?node;
????????????????}else{
????????????????????node.next?=?this.head;
????????????????????this.head.prev?=?node;
????????????????????this.head?=?node;
????????????????}
????????????}else{
????????????????//?插到中间
????????????????let?current?=?this.getElementAt(position);
????????????????let?previous?=?current.prev;
????????????????node.next?=?current;
????????????????node.prev?=?previous;
????????????????previous.next?=?node;
????????????????current.prev?=?node;
????????????}
????????}
????????this.length++;
????????return?true;
????}

removeA()方法

        ????removeAt(position){
????????if?(position?<?0?||?position?>?this.length)
????????????return?null;
????????let?current?=?this.head;
????????let?previous;
????????//?移除头部元素
????????if(position?===?0){
????????????this.head?=?current.next;
????????????this.head.prev?=?null;
????????????if?(this.length?===1)
????????????????this.tail?=?null;
????????}else?if(position?===?this.length?-1){
????????????//?移除尾部元素
????????????current?=?this.tail;
????????????this.tail?=?current.prev;
????????????this.tail.next?=?null;
????????}else{
????????????//?移除中间元素
????????????current?=?this.getElementAt(position);
????????????previous?=?current.prev;
????????????previous.next?=?current.next;
????????????current.next.prev?=?previous;
????????}
????????this.length--;
????????return?current.element;
????}

循环链表
循环链表的尾部指向它自己的头部。循环链表可以有单向循环链表，也可以有双向循环链表。下面是单向循环链表和双向循环链表的数据结构示意图：
技术分享图片

原文：https://www.cnblogs.com/chri330dj/p/12423741.html

内容总结

以上是互联网集市为您收集整理的用JavaScript实现链表全部内容，希望文章能够帮你解决用JavaScript实现链表所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1247975.html

来源：【匿名】

【上一篇】java 之抽象工厂模式（大话设计模式）【下一篇】JAVA/JSP学习系列之五

更多 ►

【用JavaScript实现链表】教程文章相关的互联网学习教程文章

什么是链表链表是一种动态的数据结构，用来存储一系列有序的元素。每个元素由一个存储元素本身的节点和一个指向下一个元素的指针构成。与数组的区别在于链表分配内存空间灵活，并非保存在连续的存储空间中。且链表不提供利用特定索引进行访问。因此，如果需要链表表中的第三个元素，则必须遍历第一个和第二个节点才能到得到它。当要移动或删除元素时，只需要修改相应元素上的指针就可以了。对链表元素的操作要比对数组元素的操作效...

java数据结构-普通链表实现【代码】

package com.node;/** * @auther 付强 * @date 2020/2/14 - 9:20 *///一个节点 //普通链表public class Node { //节点内容 int data; //下一个节点 Node next; public Node(int data){ this.data=data; } //为节点追加节点 public Node append(Node node){ //当前节点 Node currentNode=this; //循环向后找 while (true){ //取出下一个节点 ...

【LeetCode-面试算法经典-Java实现】【024-Swap Nodes in Pairs（成对交换单链表的结点）】【代码】【图】

【024-Swap Nodes in Pairs（成对交换单链表的结点）】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题　　Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should return the list as 2->1->4->3. Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed. 题目大意　　给定一...

用java实现单链表的问题汇总【代码】

单链表的每个结点都包含有值，还包含链接下一结点的引用字段。链表将所有结点按顺序链接组织起来。以上为链表的基本定义，最近写了单链表的一些实现，也进行了一些思考，当然我的思考可能有所遗漏或者不对，写出来的代码健壮性可能不太好，如果有错误或更好的方法欢迎大家指正。先总结一下单链表，之后找个时间再总结一下双链表。首先链表定义如下：1publicclass Node { 23 Node next = null; 4int val; 5public Node(int x) {...

java实现单链表【代码】

早上清早起来，第一件事就是打开博客园随便的翻看下博客，看到有篇文章提到的算法数据结构，实现一个单链表的操作。作者是使用c#编写的，那么我这里通过java也来弄弄。首先定义一个Node类publicclass Node {protected Node next; //指针域 publicint data;//数据域 public Node( int data) { this. data = data; } //显示此节点 publicvoid display() { System. out.print( data + " "); } }接下来定义一个单链表，并实...

【LeetCode-面试算法经典-Java实现】【114-Flatten Binary Tree to Linked List（二叉树转单链表）】【代码】【图】

【114-Flatten Binary Tree to Linked List（二叉树转单链表）】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】原题　　Given a binary tree, flatten it to a linked list in-place. For example, Given 1/ 2 5/ \ 3 4 6　　The flattened tree should look like: 1 2 3 4 5 6题目大意　　给定一棵二叉树，将它转成单链表，使用原地算法。解题思...

Java双链表【代码】【图】

一、概述二、英雄类　 1class HeroNode {2//值域 3publicint id;4public String name;5public String nickName;6//指针域 7public HeroNode next;8public HeroNode prev;910 HeroNode(int id, String name, String nickName) { 11this.id = id; 12this.name = name; 13this.nickName = nickName; 14 } 15 }三、主方法1 @Test 2publicvoid test() { 3//创建头结点4 HeroNode head = new HeroNode(-1, null, null); 5...

重读《学习JavaScript数据结构与算法-第三版》- 第6章链表（一）【代码】【图】

定场诗伤情最是晚凉天，憔悴厮人不堪言；邀酒摧肠三杯醉.寻香惊梦五更寒。钗头凤斜卿有泪，荼蘼花了我无缘；小楼寂寞新雨月.也难如钩也难圆。前言本章为重读《学习JavaScript数据结构与算法》的系列文章，该章节主要讲述数据结构-链表，以及实现链表的过程和原理。链表链表，为什么要有这种数据结构呢？当然，事出必有因！数组-最常用、最方便的数据结构，But，当我们从数组的起点或中间插入或移动项的成本很高，因为我们需要移...

LeetCode 147. Insertion Sort List 链表插入排序 C++/Java【代码】【图】

Sort a linked list using insertion sort.A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list.With each iteration one element (red) is removed from the input data and inserted in-place into the sorted listAlgorithm of Insertion Sort:1Insertion sort iterates, consuming one input element each repetition, and growing a sorted outp...

算法(第四版)学习笔记之java实现栈和队列(链表实现)

下压堆栈(链表实现)：import java.util.Iterator;public class LinkedStack<Item> implements Iterable<Item> {public class Node{Item item;Node next;}private Node frist;private int N = 0;public boolean isEmpty(){return N == 0;}public int size(){return N;}public void push(Item item){Node oldFrist = frist;frist = new Node();frist.next = oldFrist;frist.item = item;N++;}public Item pop(){Item item = frist.it...

十二、双向链表的java实现【图】

原理图：运行结果： Node代码：public class Node { int data; Node next; Node previous; //前向指针 public Node(int value) { // TODO Auto-generated constructor stub this.data = value; } public void display() { System.out.print(data+ " "); }} doubleLinklist:public class doubleLinklist { private Node first; private Node last; //尾结点 public doubleLinklist(...

大话数据结构（八）Java程序——双向链表的实现【代码】

线性链表——双向链表双向链表定义：双向链表（double linked list): 是在单表单的每个结点中，再设置一个指向前驱结点的指针域。因此，在双向链表中的结点都有两个指针域，一个指向前驱，一个指向后继。双向链表的存储结构typedef struts DulNode{Element data;Struct DulNode *prior;前驱指针Struct DulNode *next;后继指针}DulDouble, *DulLinkList;双向链表的插入与删除双向链表的插入：假设结点为s,要将结点插入到结点p和p->n...

JavaScript 链表定义【代码】

Java记录 -48- Java数据结构-链表【代码】【图】

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。650) this.width=650;" src="/upload/getfiles/default/2022/11/13/20221113033539468.jpg" title="QQ图片20151101081241.png" />单向节点Node实例：public class NodeTest { public static void main(String[] args){ Node no...

JavaScript算法系列之-----------------链表反转（JS实现）【代码】

题目：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。之前一直对JS实现链表理解不了，被算法大牛指点了一下豁然开朗。function ListNode(x){this.val = x;this.next = null; } 在JS中，this.val代表当前节点的值，this.next指向下一个节点，若this.next为null(对象)，则说明该节点为链表的最后一个节点。PS：把下一个节点赋值给当前对象的next属性，通过这样的方式连接。通过代码：function printListFromTailToHead(h...

首页 / JAVA / 用JavaScript实现链表