javascript数据结构-链表

本文最后更新于：8 个月前

本博客参考于洛伊安妮·格罗纳编著的javascript数据结构与算法第三版及codeWay老师视频或其他博客资料，在此对此表示感谢!
github仓库：https://github.com/hzx17/

认识链表

链表和数组

链表和数组一样，可以用于存储一系列的元素，但是链表和数组的实现机制完全不同。

数组

  • 存储多个元素，数组（或列表）可能是最常用的数据结构。

  • 几乎每一种编程语言都有默认实现数组结构，提供了一个便利的 [] 语法来访问数组元素。

  • 数组缺点：

    数组的创建需要申请一段连续的内存空间(一整块内存)，并且大小是固定的，当前数组不能满足容量需求时，需要扩容。 (一般情况下是申请一个更大的数组，比如 2 倍，然后将原数组中的元素复制过去)

    在数组开头或中间位置插入数据的成本很高，需要进行大量元素的位移。

链表

  • 存储多个元素，另外一个选择就是使用链表。

  • 不同于数组，链表中的元素在内存中不必是连续的空间。

  • 链表的每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(有些语言称为指针)组成。

  • 链表优点：

    内存空间不必是连续的，可以充分利用计算机的内存，实现灵活的内存动态管理。

    链表不必在创建时就确定大小，并且大小可以无限延伸下去。

    链表在插入和删除数据时，时间复杂度可以达到 O(1)，相对数组效率高很多。

  • 链表缺点：

    访问任何一个位置的元素时，需要从头开始访问。(无法跳过第一个元素访问任何一个元素)

    无法通过下标值直接访问元素，需要从头开始一个个访问，直到找到对应的元素。

    虽然可以轻松地到达下一个节点，但是回到前一个节点是很难的。

单向链表

单向链表的概念

单向链表类似于火车，有一个火车头，火车头会连接一个节点，节点上有乘客，并且这个节点会连接下一个节点，以此类推。

  • 链表的火车结构

    链表的火车结构

  • 链表的数据结构

    head 属性指向链表的第一个节点。
    链表中的最后一个节点指向 null。
    当链表中一个节点也没有的时候，head 直接指向 null。

    链表的数据结构

  • 给火车加上数据后的结构

    给火车加上数据后的结构

链表中的常见操作

  • append(element) 向链表尾部添加一个新的项。
  • insert(position, element) 向链表的特定位置插入一个新的项。
  • get(position) 获取对应位置的元素。
  • indexOf(element) 返回元素在链表中的索引。如果链表中没有该元素就返回-1。
  • update(position, element) 修改某个位置的元素。
  • removeAt(position) 从链表的特定位置移除一项。
  • remove(element) 从链表中移除一项。
  • isEmpty() 如果链表中不包含任何元素，返回 trun，如果链表长度大于 0 则返回 false。
  • size() 返回链表包含的元素个数，与数组的 length 属性类似。
  • toString() 由于链表项使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值。

单向链表的封装

  • 先创建单向链表类 LinkedList，添加基本属性，再逐步实现单向链表的常用方法。
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
function LinkedList(){
    //内部类：节点类
    function Node(data){
        this.data=data;
        this.next=null;
    }
    //属性
    this.head=null;
    this.length=0;

    //追加方法
    LinkedList.prototype.append=function(data){
        //创建一个新的节点
        let newNode=new Node(data);
       //判断 是否为第一个节点
        if(this.length==0){
            this.head=newNode;
        }else{
            //创建一个临时变量，使头部节点指向一个新的临时节点
            let current=this.head
            //判断current的next是否为空，如果不为空，将current的next指向current
            while(current.next){
                current=current.next;
            }
            current.next=newNode;
        }
        this.length+=1;
    }
    //tostring方法
    LinkedList.prototype.toString=function(){
        //定义一个临时变量
        let current=this.head;
        let result="";
        while(current){
           result+=current.data+"";
           current=current.next
        }
        return result;
    }
    //指定位置插入节点
    LinkedList.prototype.insert=function(data,position){
        //节点数判断是否小于index
        if(this.length < position || position < 0){
            return console.log('你插入的位置大于链表的长度')
        }
        //创建NOde实例
        const newNode = new Node(data)
        if(position === 0) {
          // 使原来的头部指向新节点的next，然后再将data指向this.head
          newNode.next = this.head
          this.head = newNode
        }else { // 插入位置大于0，即不是头节点
          let index = 0  // 定义一个初始变量
          var current = this.head
          var previous = null // 当前节点的前一个
          while (index++ < position) {
            previous = current
            current = current.next
          }    
          newNode.next = current
          previous.next = newNode
        }
        this.length +=1
    }
    // get方法
    LinkedList.prototype.get = function(position){
      if( position >= this.length || position < 0){
        return null
      }
      // 获取相应的data
      let current =this.head
      let index = 0
      while(index++ < position){
        current = current.next
      }
      return current.data
    }
    // 返回元素所在索引，如果不存在则返回-1
    LinkedList.prototype.indexOf = function(data){
      let current = this.head
      let index = 0
      while(current){
        if(current.data === data){
          return index
        }
        current = current.next
        index +=1
      }
      // 没有找到，返回-1
      return -1
    }
    // 更改元素
    LinkedList.prototype.update = function(newData,position) {
      // 越界判断
      if( position >= this.length || position < 0){
        return console.log('更改位置不正确')
      }
      let current = this.head 
      let index =0
      while(index++ < position) {
        current = current.next
      }
      // 将获取到的节点，更新
      current.data = newData
      return true
    }
    // 移出列表中特定位置一项，传入位置索引即可
    LinkedList.prototype.removeAt = function(position) {
      // 越界判断
      if( position >= this.length || position < 0){
        return console.log('移出位置不正确')
      }
      let current = this.head
      let index = 0
      let previous = null
      if(position === 0) {
        current =current.next
        this.head =current
      }else{
        while(index++ <position) {
          previous = current
          current = current.next
        }
        previous.next = current.next
      }
      this.length -=1
    }
    // 移出指定元素的一项，传入元素
    LinkedList.prototype.remove = function (element) {
      let current = this.head
      let previous = null
      while(current) {
        if(current===this.head && current.data === element) {
          this.head = current.next
          this.length -=1
          return true
        }
        else if(current.data === element) {
          previous.next = current.next
          this.length -=1
          return true
        }
        previous = current
        current = current.next
      }
      return console.log('未找到要删除的元素')
    }
    // 是否为空,为空返回true，有其他元素返回false
    LinkedList.prototype.isEmpty = function () {
      return (this.length ==0)
    }
    // 判断链表的个数，即返回链表的长度
    LinkedList.prototype.size = function () {
      return this.length
    }
}

代码测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* 链表测试 */
let linklist=new LinkedList();
linklist.append(12);
linklist.append(13);
linklist.append(14);
linklist.append(14);
// linklist.insert("我是插入的",3)
// linklist.update("我修改了第一个",0)
// linklist.removeAt(0)
linklist.remove(12)
console.log(linklist)
console.log( linklist.indexOf(15))
console.log(linklist.get(1))
console.log(linklist.toString())

双向链表

单向链表和双向链表区别

单向链表

  • 只能从头遍历到尾或者从尾遍历到头（一般从头到尾）。
  • 链表相连的过程是单向的，实现原理是上一个节点中有指向下一个节点的引用。
  • 单向链表有一个比较明显的缺点：可以轻松到达下一个节点，但回到前一个节点很难，在实际开发中, 经常会遇到需要回到上一个节点的情况。

双向链表

  • 既可以从头遍历到尾，也可以从尾遍历到头。
  • 链表相连的过程是双向的。实现原理是一个节点既有向前连接的引用，也有一个向后连接的引用。
  • 双向链表可以有效的解决单向链表存在的问题。
  • 双向链表缺点：
    • 每次在插入或删除某个节点时，都需要处理四个引用，而不是两个，实现起来会困难些。
    • 相对于单向链表，所占内存空间更大一些。
    • 但是，相对于双向链表的便利性而言，这些缺点微不足道。

双向链表结构

双向链表

  • 双向链表不仅有 head 指针指向第一个节点，而且有 tail 指针指向最后一个节点。
  • 每一个节点由三部分组成：item 储存数据、prev 指向前一个节点、next 指向后一个节点。
  • 双向链表的第一个节点的 prev 指向 null。
  • 双向链表的最后一个节点的 next 指向 null。

双向链表常见的操作

  • append(element) 向链表尾部追加一个新元素。
  • insert(position, element) 向链表的指定位置插入一个新元素。
  • getElement(position) 获取指定位置的元素。
  • indexOf(element) 返回元素在链表中的索引。如果链表中没有该元素就返回 -1。
  • update(position, element) 修改指定位置上的元素。
  • removeAt(position) 从链表中的删除指定位置的元素。
  • remove(element) 从链表删除指定的元素。
  • isEmpty() 如果链表中不包含任何元素，返回 trun，如果链表长度大于 0 则返回 false。
  • size() 返回链表包含的元素个数，与数组的 length 属性类似。
  • toString() 由于链表项使用了 Node 类，就需要重写继承自 JavaScript 对象默认的 toString 方法，让其只输出元素的值。
  • forwardString() 返回正向遍历节点字符串形式。
  • backwordString() 返回反向遍历的节点的字符串形式。

双向链表的封装

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
function DoublyLinkedList () {
  /* 内部类 */ 
  function Node(data) {
    this.prev = null
    this.next = null
    this.data = data
  }
  this.head = null
  this.tail = null
  this.length = 0
  //追加方法
  DoublyLinkedList.prototype.append = function(element) {
    // 1、创建双向链表节点
    const newNode = new Node(element);
    // 2、追加元素
    if (this.head === null) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      // ！！跟单向链表不同，不用通过循环找到最后一个节点
      // 巧妙之处
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.length++;
  }
  // 向指定位置插入一个新的一项
  DoublyLinkedList.prototype.insert =function(element,position) {
    //越界判断
    if(position<0 || position> this.length) {
      return console.log('插入位置不正确')
    }
    //创建新节点
    const newNode = new Node(element)
    if(this.length === 0) {
      this.head =newNode
      this.tail = newNode
    }else{
      if(position === 0) {     //当position===0时
        newNode.next = this.head  //新节点的下一指针指向原来的头节点
        this.head.prev = newNode  //原来头节点的上一指针指向新节点，这样才形成双向链表
        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
        }
        current.prev.next = newNode
        newNode.prev = current.prev
        current.prev = newNode
        newNode.next = current
      }
    }
    this.length +=1
  }
  // get方法，获取某个位置的数据
  DoublyLinkedList.prototype.get = function(position) {
    // 越界判断
    if(position>=this.length || position <0){
      return console.log('获取位置有误')
    }
 
    if(this.length / 2 < position) {
      let current = this.tail
      let index = this.length -1
      while(index-- > position) {
        current = current.prev
      }
      return current.data
    }else{
      let current = this.head
      let index = 0
      while(index++ < position) {
        current = current.next
      }
      return current.data
    }
  }
  // indexOf,参数为元素，如果存在返回元素所在位置，不存在返回-1
  DoublyLinkedList.prototype.indexOf = function(element) {
    let current =this.head
    let index = 0
    while(current) {
      if(current.data === element ) {
        return index
      }
      current = current.next
      index +=1
    }
    return -1
  }
  // 双向链表更新方法的实现,传入两个参数，元素与位置
  DoublyLinkedList.prototype.update = function(element,positon) {
    //越界判断
    if(positon >=this.length || positon < 0) {
      return console.log('你更改的位置有误')
    }
    let current = this.head
    let index = 0
    while(index++ < positon) {
      current = current.next
    }
    current.data = element
  }
  // 根据传入的位置信息，删除指定元素
  DoublyLinkedList.prototype.removeAt = function(position) {
    // 越界判断 
    if(position >=this.length || position < 0) {
      return console.log('你更改的位置有误')
    }
    if(this.length === 1){
      this.head = null
    }else if(position === 0) {
       this.head.next.prev = null
       this.head = this.head.next
    }else if (position == this.length-1) {
      this.tail.prev.next = null
      this.tail = this.tail.prev
    }else {
      let current = this.head
      let index = 0 
      while (index++ < position) {
        current = current.next
      }
       current.prev.next = current.next
       current.next.prev = current.prev
    }
    this.length -=1
  }
  // 根据传入的元素，删除指定元素
  DoublyLinkedList.prototype.remove = function(element) {
    // let current = this.head 
    // while(current) {
    //  if(current ==this.head &&current.data === element){
    //     this.head.next.prev = null
    //     this.head = this.head.next
    //     this.length -=1
    //     return true
    //   }else if(current == this.tail && current.data === element){
    //     this.tail.prev.next = null
    //     this.tail = this.tail.prev
    //     this.length -=1
    //     return true
    //   }else if(current.data === element){
    //     current.next.prev = current.prev
    //     current.prev.next = current.next
    //     this.length -=1
    //     return true
    //    }
    //   current = current.next
    // }
    // return console.log('未找到元素')
    let index =this.indexOf(element)
    this.removeAt(index)
  }
  //转换成字符串形式
  DoublyLinkedList.prototype.toString = function() {
    return this.backwardString()
  }
  // 向前遍历
  DoublyLinkedList.prototype.forwardString =function () {
    let current = this.tail
    let resultString = ""
    // 依次向前遍历
    while(current) {
      resultString += current.data + " "
      current = current.prev
    }
    return resultString
  }
  // 向后遍历backwardString
  DoublyLinkedList.prototype.backwardString = function () {
    let current = this.head
    let resultString = ""
    // 依次向后遍历
    while(current) {
      resultString += current.data + ' '
      current = current.next
    }
    return resultString
  }
  // size方法，获取链表长度
  DoublyLinkedList.prototype.size = function () {
    return this.length
  }
  //是否为空
  DoublyLinkedList.prototype.isEmpty = function () {
    return (this.length===0)
  }
}

测试双向链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* 测试双向链表 */
const list = new DoublyLinkedList()
list.append(1)
list.append(2)
list.append(3)
list.insert(4,0)
list.update(0,0)
list.remove(3)
// list.removeAt(0)
// console.log(list.indexOf(0))
// console.log(list.get(0))
// console.log(list.isEmpty())
console.log(list.backwardString())
console.log(list.forwardString())
console.log(list)