js-学习链表

链表基础概念

链表和数组一样，可以用于存储一系列连续的元素。链表中的元素在内存中不必是连续的空间。链表的每一个元素有一个由一个存储元素本身的节点和一个指向下一个元素的引用组成(指针和连接)。

链表构成

数据+指针

链表优点

1.内存空间不是必须连续的，可以充分利用计算机的内存，实现灵活的内存动态管理；
2.链表不必在创建时就确定大小，并且大小可以无限的延伸下去；
3.链表在插入和删除数据时，时间复杂度可以达到O(1)，相对数组效率高很多.

js中的链表

1.属于自定义数据结构；
2.可以存数字、字符串等等任意结构的数据；
在这里插入图片描述

上图展示的为单链表。

代码实现链表

DOCTYPE html>
<html>
    <head>
        <meta charset="utf-8">
        <title>title>
    head>
    <body>
        <script>
        // 创建自定义对象
        // 1.声明类
        class LinkedList{
            // 2.创建构造函数
            constructor(){
                this.head=null;//头节点
                this.tail=null;//尾节点
                // 存放头尾，根据链表自身的特点，就相当于是存储了整个链表
            }
            //append追加节点(末尾添加)
            append(value){
                const newNode={value:value,next:null}
                if(this.tail){
                     this.tail.next=newNode;//新创建的节点和尾部节点进行数据关联
                }
                this.tail=newNode;//更新尾部值
                if(!this.head){
                    this.head=newNode;
                }
            }
            // 前置节点(头部添加)
            prepend(value){
                const newNode={value:value,next:this.head}; 
                this.head=newNode;
                if(!this.tail){
                    this.tail=newNode;
                }
            }
            // 删除节点 js垃圾回收
            delete(value){
                if(!this.head){
                    return;
                }
                    
                while(this.head&&this.head.value===value){
                    this.head=this.head.next;
                }
                let curNode=this.head;
                while(curNode.next){
                   if(curNode.next.value===value){
                       curNode.next=curNode.next.next;
                   }else{
                       curNode=curNode.next;
                   }
                }
                if(this.tail.value===value){
                    this.tail=curNode;
                }
            }
            // 查找节点
            find(value){
               if(!this.head){
                   console.log(null);
                   return null;
               } 
               let curNode=this.head;
               while(curNode){
                   if(curNode.value===value){
                       return curNode;
                   }
                       curNode=curNode.next;
               } 
               console.log(null);
               return null;
                   
            }
            // 插入节点,某个节点后边插入
            insertAfter(value,afterVaule){
                const existingNode=this.find(afterValue);
                if(existingNode){
                    const newNode={value:value,next:existingNode.next}
                    existingNode.next=newNode;
                }
            }
            
            //以数组方式输出节点
            toArray(){
                const elements=[];
                let curNode=this.head;
                while(curNode){
                    elements.push(curNode);
                    curNode=curNode.next;
                }
                return elements;
            }
        }
        // 创建对象，通过类里边声明的构造函数
        const linkedList1=new LinkedList();
        // 测试，能否执行节点添加
        linkedList1.append(1);
        linkedList1.append(1);
        linkedList1.append('aaa');
        linkedList1.append('aaa');
        linkedList1.append('reter');
        linkedList1.append('reter');
        linkedList1.append(2);
        linkedList1.append(true);
        linkedList1.prepend('one');
        console.log(linkedList1.toArray());
        // 删除元素
        linkedList1.delete('aaa');
        linkedList1.delete('reter');
        linkedList1.delete(1);
       // console.log(linkedList1);
       console.log(linkedList1.toArray());
       linkedList1.find(1);
       
        script>
    body>
html>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

相关阅读:
C. Non-coprime Split Codeforces Round 895 (Div. 3)
jQuery表单属性过滤器：过滤＜input＞标签、＜select＞标签
 JDK1.7和JDK1.8版本的新特性
 JXLS2同一个sheet多个表格循环覆盖下面表格数据问题
 区块链：一文了解区块链，在生活中的应用，代码实现，图导，区块链智能合约
 ISP屏幕和LCD屏幕的区别，以及AMOLED、Super AMOLED和OLED
Unity 制作KinematicCharacterController
Kubernetes 理解kubectl/调试
 Linux fdisk实战
 VirtualBox网络配置
原文地址：https://blog.csdn.net/dadati/article/details/127860031