链表

发表于

leetCode中Merge Two Sorted Lists，由此引发温习链表结构在JavaScript中的存储表示

链表

物理上非连续，非顺序的存储结构，数据元素以结点的指针链接次序实现的。生活中例子：自行车的链条
结点： data:存储数据元素的数据域，next是存储下一个结点地址的指针域
┌───┬───┐
│data │next │
└───┴───┘

优点：

  • 克服数组链表需要预先知道数据大小的缺点

缺点：

  • 无法随机读取
  • 增加空间开销，增加了指针开销

单链表

以“结点的序列”表示线性表称作线性链表

单链表

尾节点指针为null

1
2
3
4
function ListNode(value){
    this.data = value
    this.next = null
}

双链表

针对单链表的优化，增加一个前地址，提高查找效率。这样的设计会比单链表更加复杂，用空间换时间

双链表

1
2
3
4
5
function ListNode(value){
    this.data = value
    this.next = null
    this.prev = null
}

循环链表

循环链表:由于单链表的只会往后方传递，所以到达尾部的时候，要回溯到首部会非常麻烦，所以把尾部节的链与头连接起来形成循环

尾节点地点指针指向头部地址

循环双链表

和双链表的区别：
尾节点地点next指针指向头部地址
头结点的prev指向尾结点

ES6实现单链表

方法：
● append(data):向链表尾部添加一个新的元素；
● insert(position,data):向链表特定位置插入元素；
● remove(node):从链表移除一项；
● indexOf(node):返回链表中某元素的索引，如果没有返回-1；
● removeAt(position):从特定位置移除一项；
● isEmpty():判断链表是否为空，如果为空返回true,否则返回false;
● size():返回链表包含的元素个数；

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
class Node {
    constructor(data) {
        this.data = data
        this.next = null
    }
}
class ListNode {
    constructor() {
        this.length = new WeakMap() 
        this.head = new WeakMap() 
        this.length.set(this, 0)
        this.head.set(this, null)
    }
    //向链表尾部添加一个新的元素
    append(data) {
        let node = new Node(data)
        let current = this.getHead()
        if (current == null) {
            this.head.set(this, node)
        } else {
            while (current.next) {
                current = current.next
            }
            current.next = node
        }
        let l = this.size()
        l++
        this.length.set(this, l)
    }
    //向链表特定位置插入元素
    insert(position, data) {
        if (position >= 0 && position <= this.size()) {
            let node = new Node(data)
            let current = this.head.get(this)
            if (position === 0) {
                node.next = current
                this.head.set(this, node)
            } else {
                let index = 0
                let previous
                while (index < position) {
                    current = current.next
                    previous = current
                    index++
                }
                node.next = current
                previous.next = node
            }
            let l = this.size()
            l++
            this.length.set(this, l)
            return true
        }
        return false
    }
    isEmpty() {
        return this.size() === 0
    }
    getHead() {
        return this.head.get(this)
    }
    size() {
        return this.length.get(this)
    }
    // 返回链表中某元素的索引，如果没有返回-1
    indexOf(node) {
        let current = this.head.get(this)
        let index = 0
        if (current === node) {
            return index
        }
        while (current !== node && index < this.size()) {
            current = current.next
            index++
        }
        return current && current === node ? index : -1
    }
    //从链表移除一项
    remove(node) {
        let index = this.indexOf(node)
        return this.removeAt(index)
    }
    //返回链表中某元素的索引，如果没有返回-1
    removeAt(position) {
        if (position < 0 || position > length.size) {
            return null
        }
        let current = this.head.get(this)
        let index = -1
        let previous
        while (index < position) {
            current = current.next
            previous = current
            index++
        }
        previous.next = current.next
        let l = this.size()
        l--
        this.length.set(this, l)
        return current
    }
}

使用场景

暂时没有遇到需要使用该结构的场景。如遇到再补充

参考