链表结构

​ –单向链表–

  • 封装链表类：

    • function LinkedList() {
    //内部的类：节点类
    function Node(data) {
      this.data = data
      this.next = null
    }

    //属性
    this.head = null
    this.length = 0
<!--hexoPostRenderEscape:<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">* 链表 方法：</span><br><span class="line"></span><br><span class="line">* &#96;&#96;&#96;javascript</span><br><span class="line">  &#x2F;&#x2F;1.追加方法</span><br><span class="line">      LinkedList.prototype.append &#x3D; function (data) &#123;</span><br><span class="line">        &#x2F;&#x2F;1.创建新的节点</span><br><span class="line">        let newNode &#x3D; new Node(data)</span><br><span class="line">        &#x2F;&#x2F;2.判断是否添加到是第一个节点</span><br><span class="line">        if (this.length &#x3D;&#x3D; 0) &#123; &#x2F;&#x2F;2.1是第一个节点</span><br><span class="line">          this.head &#x3D; newNode</span><br><span class="line">        &#125; else &#123;             &#x2F;&#x2F;2.2不是第一个节点</span><br><span class="line">          let newNoad &#x3D; new Node(data)</span><br><span class="line">          let current &#x3D; this.head</span><br><span class="line">          while (current.next) &#123;</span><br><span class="line">            current &#x3D; current.next</span><br><span class="line">          &#125;</span><br><span class="line">          &#x2F;&#x2F;最后节点的next指向新的节点</span><br><span class="line">          current.next &#x3D; newNoad</span><br><span class="line">        &#125;</span><br><span class="line">        &#x2F;&#x2F;3.length+1</span><br><span class="line">        this.length +&#x3D; 1</span><br><span class="line">      &#125;</span><br></pre></td></tr></table></figure>:hexoPostRenderEscape-->

    • toString方法

    •  //2.toString方法
    LinkedList.prototype.toString = function () {
      //1.定义变量
      let current = this.head
      let listString = " "

      //2.循环获取一个个的节点
      while (current) {
        listString += current.data + " "
        current = current.next
      }
      return listString
    }
<!--hexoPostRenderEscape:<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">* insert方法</span><br><span class="line"></span><br><span class="line">* &#96;&#96;&#96;javascript</span><br><span class="line">  LinkedList.prototype.insert &#x3D; function (position, data) &#123;</span><br><span class="line">        &#x2F;&#x2F;1).对position进行越界判断</span><br><span class="line">        &#x2F;&#x2F;假如只有四个元素，传入position为100的话return false</span><br><span class="line">        if (position &lt; 0 || position &gt; this.length) return false</span><br><span class="line">        &#x2F;&#x2F;2).根据data 创建newNode</span><br><span class="line">        let newNode &#x3D; new Node(data)</span><br><span class="line">        &#x2F;&#x2F;3).判断插入的位置是否是第一个</span><br><span class="line">        if (position &#x3D;&#x3D;&#x3D; 0) &#123;</span><br><span class="line">          newNode.next &#x3D; this.head</span><br><span class="line">          this.head &#x3D; newNode</span><br><span class="line">        &#125; else &#123;</span><br><span class="line">          let index &#x3D; 0</span><br><span class="line">          let current &#x3D; this.head</span><br><span class="line">          let previous &#x3D; null</span><br><span class="line">          while (index++ &lt; position) &#123;</span><br><span class="line">            previous &#x3D; current</span><br><span class="line">            current &#x3D; current.next</span><br><span class="line">          &#125;</span><br><span class="line">          newNode.next &#x3D; current</span><br><span class="line">          previous.next &#x3D; newNode</span><br><span class="line">        &#125;</span><br><span class="line">        &#x2F;&#x2F;4).length+1</span><br><span class="line">        this.length +&#x3D; 1</span><br><span class="line">        return true</span><br><span class="line">      &#125;</span><br></pre></td></tr></table></figure>:hexoPostRenderEscape-->

    • get方法

    • LinkedList.prototype.get = function (position) {
      //越界判断
      if (position < 0 || position >= this.length) return null
      //获取对应的信息data
      let current = this.head
      let index = 0
      while (index++ < position) {
        current = current.next
      }
      return current.data
    }
<!--hexoPostRenderEscape:<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">* indexOf方法</span><br><span class="line"></span><br><span class="line">* &#96;&#96;&#96;</span><br><span class="line">  LinkedList.prototype.indexOf &#x3D; function (data) &#123;</span><br><span class="line">        &#x2F;&#x2F;5.1变量定义</span><br><span class="line">        let current &#x3D; this.head</span><br><span class="line">        let index &#x3D; 0</span><br><span class="line">        &#x2F;&#x2F;5.2开始</span><br><span class="line">        while (current) &#123;</span><br><span class="line">          if (current.data &#x3D;&#x3D;&#x3D; data) &#123;</span><br><span class="line">            return index</span><br><span class="line">          &#125;</span><br><span class="line">          current &#x3D; current.next</span><br><span class="line">          index++</span><br><span class="line">        &#125;</span><br><span class="line">        return -1</span><br><span class="line">      &#125;</span><br></pre></td></tr></table></figure>:hexoPostRenderEscape-->

    • update

    •   //6.update方法
    LinkedList.prototype.update = function (position, newData) {
      //1.越界判断
      if (position < 0 || position >= this.length) return false
      //2.查找正确的节点
      let current = this.head
      let index = 0
      while (index++ < position) {
        current = current.next
      }
      current.data = newData
      return true
    }
<!--hexoPostRenderEscape:<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">* removeAt方法</span><br><span class="line"></span><br><span class="line">* &#96;&#96;&#96;javascript</span><br><span class="line">   LinkedList.prototype.removeAt &#x3D; function (position) &#123;</span><br><span class="line">        &#x2F;&#x2F;1).越界判断</span><br><span class="line">        if (position &lt; 0 || position &gt;&#x3D; this.length) return null</span><br><span class="line">  </span><br><span class="line">        &#x2F;&#x2F;2).判断是否在第一个节点删除</span><br><span class="line">        let current &#x3D; this.head</span><br><span class="line">        if (position &#x3D;&#x3D; 0) &#123;</span><br><span class="line">          this.head &#x3D; this.head.next</span><br><span class="line">        &#125; else &#123;</span><br><span class="line">          let index &#x3D; 0</span><br><span class="line">          let previous &#x3D; null</span><br><span class="line">          while (index++ &lt; position) &#123;</span><br><span class="line">            previous &#x3D; current</span><br><span class="line">            current &#x3D; current.next</span><br><span class="line">          &#125;</span><br><span class="line">          previous.next &#x3D; current.next</span><br><span class="line">        &#125;</span><br><span class="line">        &#x2F;&#x2F;3)长度减少了一</span><br><span class="line">        this.length -&#x3D; 1</span><br><span class="line">  </span><br><span class="line">        return current.data</span><br><span class="line">      &#125;</span><br></pre></td></tr></table></figure>:hexoPostRenderEscape-->

    • remove方法

    •  LinkedList.prototype.remove=function (data) {
    //1）.获取data在列表中的位置
    let position=this.indexOf(data)
    //2).根据位置信息删除节点
    return this.removeAt(position)
    }
<!--hexoPostRenderEscape:<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">  其他：</span><br><span class="line"></span><br><span class="line">* &#96;&#96;&#96;javascript</span><br><span class="line">   &#x2F;&#x2F;9.isEmpty方法</span><br><span class="line">      LinkedList.prototype.isEmpty&#x3D;function () &#123;</span><br><span class="line">      return this.length&#x3D;&#x3D;0</span><br><span class="line">      &#125;</span><br><span class="line">      &#x2F;&#x2F;10.size</span><br><span class="line">      LinkedList.prototype.size&#x3D;function () &#123;</span><br><span class="line">      return this.length</span><br><span class="line">      &#125;</span><br></pre></td></tr></table></figure>:hexoPostRenderEscape-->

双向链表

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
//封装双向链表
 function DoublyLinkedList() {
   //内部类 ： 节点类
   function Node(data) {
     this.data = data
     this.prev = null
     this.next = null
   }

   //属性
   this.head = null
   this.tail = null
   this.length = 0

   //常见的操作方法
   //1.append方法
   DoublyLinkedList.prototype.append = function (data) {
     //1)创建一个节点
     let newNode = new Node(data)
     //2)判断是否为空
     if (this.length == 0) {
       this.head = newNode
       this.tail = newNode
     } else {
       this.tail.next = newNode
       newNode.prev = this.tail
       this.tail = newNode
     }
     //3)长度加1
     this.length += 1
   }
   //2.链表转成字符串形式
   //2.1toString方法
   DoublyLinkedList.prototype.toString = function () {
     return this.backwardString()
   }
   //2.2forwardString方法
   DoublyLinkedList.prototype.forwardString = function () {
     //1.定义变量
     let current = this.tail
     let resultString = ""
     //2.向前遍历
     while (current) {
       resultString += current.data + " "
       current = current.prev
     }
     return resultString
   }
   //2.3backwardString方法
   DoublyLinkedList.prototype.backwardString = function () {
     //1.定义变量
     let current = this.head
     let resultString = ""
     //2.向后遍历 获取每一个节点
     while (current) {
       resultString += current.data + " "
       current = current.next
     }
     return resultString
   }
   //3.insert插入方法
   DoublyLinkedList.prototype.insert = function (position, data) {
     //1.越界判断
     if (position < 0 || position > this.length) return false
     //2.根据data创建新的节点
     let newNode = new Node(data)
     //3.判断是否为空
     if (this.length === 0) {
       this.head = newNode
       this.tail = newNode
     } else {
       if (position === 0) {    //3.1判断position是否为0
         this.head.prev = newNode        //this.head原来的第一个节点
         newNode.next = this.head
         this.head = newNode
       } else if (position === this.length) {    //在结尾插入
         this.tail.next = newNode
         newNode.prev = this.tail
         this.tail = newNode
       } else {               //在中间
         let current = this.head
         let index = 0
         while (index++ < position) {
           current = current.next
         }
         //修改指针 四个指向
         newNode.next = current
         newNode.prev = current.prev
         current.prev.next = newNode
         current.prev = newNode
       }
       //length+1
       this.length += 1
       return true
     }
   }
   //4.get方法
   DoublyLinkedList.prototype.get = function (position) {
     //1）.判断越界
     if (position < 0 || position >= this.length) return null
     //this.length / 2>position 从前往后
     //this.length / 2<position 从后向前
     //2）获取元素
     let current = null
     let index = 0
     if (this.length / 2 > position) {
       current = this.head
       while (index++ < position) {
         current = current.next
       }
     } else {
       current = this.tail
       index = this.length - 1
       while (index-- > position) {
         current = current.prev
       }
     }
     return current.data
   }
   //5.indexOf方法
   DoublyLinkedList.prototype.indexOf = function (data) {
     //1.定义变量
     let index = 0
     let current = this.head
     //2.查找与data相同的节点
     while (current) {
       if (current.data === data) {
         return index
       }
       current = current.next
       index += 1
     }
     return -1
   }
   //6.update方法
   DoublyLinkedList.prototype.update = function (position, newData) {
     //越界判断
     if (position < 0 || position >= this.length) return false
     //寻找正确节点
     let current = this.head
     let index = 0
     if (this.length / 2 > position) {
       while (index++ < position) {
         current = current.next
       }
     } else {
       index = this.length - 1
       current = this.tail
       while (index-- > position) {
         current = current.prev
       }
     }
     //修改寻找到的节点
     current.data = newData
     return true
   }
   //7.removeAt方法
   DoublyLinkedList.prototype.removeAt = function (position) {
     //越界判断
     if (position < 0 || position >= this.length) return null
     //判断是否只有一个节点
     let current = this.head  //放到这里 为了能拿到current.data
     if (this.length === 1) {
       this.head = null
       this.tail = null
     } else {
       if (position === 0) {          //判断是否删除的是第一个节点
         this.head.next.pre = null
         this.head = this.head.next
       } else if (position === this.length - 1) {//判断是否是最后一个节点
         current = this.tail //为了return

         this.tail.prev.next = null
         this.tail = this.tail.prev
       } else {
         let index = 0
         while (index++ < position) {
           current = current.next
         }
         current.prev.next = current.next
         current.next.prev = current.prev
       }
     }
     //长度减一
     this.length -= 1
     return current.data
   }
   //8.remove方法
   DoublyLinkedList.prototype.remove = function (data) {
     //根据data获取下标值
     let index = this.indexOf(data)
     //根据index删除对应位置的节点
     return this.removeAt(index)
   }
   //9.isEmpty
   DoublyLinkedList.prototype.isEmpty = function () {
     return this.length === 0
   }
   //10.size
   DoublyLinkedList.prototype.size = function () {
     return this.length
   }
   //11.获取链表的第一个元素
   DoublyLinkedList.prototype.getHead = function () {
     return this.head.data
   }
   //12.获取链表最后一个元素
   DoublyLinkedList.prototype.getTail = function () {
     return this.tail.data
   }

 }