链表

技术
Word count: 1.9k   |   Reading time≈ 9 min

链表

链表存储有序的元素集合，但不同于数组，链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用（也称指针或链接）组成。相比于传统的数组，链表的一个好处在于，添加或删除元素的时候不需要移动其他元素。然而，链表需要使用指针，因此实现链表时需要额外注意。在数组中，我们可以直接访问任何位置的任何元素，而想要访问链表中间的一个元素，则需要从起点（表头）开始迭代链表直到找到所需的元素。

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
// 创建相等性比较函数
function defaultEquals(a, b) {
    return a === b;
}
// 创建Node（节点）类
class Node {
    // 构造函数
    constructor(element) {
        this.element = element;
        this.next = undefined;
    }
}
class LinkedList {
    // 构造函数
    constructor(equalsFn = defaultEquals) {
        this.count = 0;
        this.head = undefined;
        this.equalsFn = equalsFn;
    }
    // 向链表尾部添加元素
    push(element) {
        const node = new Node(element);
        let current;
        if (this.head == null) {
            this.head = node;
        } else {
            current = this.head;
            while (current.next != null) { // 获取最后一项
                current = current.next;
            }
            current.next = node; // 将其next赋为新元素，建立链接
        }
        this.count++;
    }
    // 循环迭代链表直到目标位置
    getElementAt(index) {
        if (index >= 0 && index <= this.count) {
            let node = this.head;
            for (let i = 0; i < index && node != null; i++) {
                node = node.next
            }
            return node;
        }
        return undefined;
    }
    // 从链表中移除元素
    removeAt(index) {
        // 检查越界值
        if (index >= 0 && index < this.count) {
            let current = this.head;
            // 移除第一项
            if (index === 0) {
                this.head = current.next;
            } else {
                // let previous;
                // for (let i = 0; i < index; i++) {
                //     previous = current;
                //     current = current.next;
                // }
                // previous.next = current.next;
                const previous = this.getElementAt(index - 1);
                current = previous.next;
                // 将previous与current的下一项链接起来：跳过current，从而移除它
                previous.next = current.next;
            }
            this.count--;
            return current.element;
        }
        return undefined;
    }
    // 在任意位置插入元素
    insert(element, index) {
        if (index >= 0 && index <= this.count) {
            const node = new Node(element);
            if (index === 0) { // 在第一个位置添加
                const current = this.head;
                node.next = current;
                this.head = node;
            } else {
                const previous = this.getElementAt(index - 1);
                const current = previous.next;
                node.next = current;
                previous.next = node;
            }
            this.count++; // 更新链表的长度
            return true;
        }
        return false;
    }
    // 返回一个元素的位置
    indexOf(element) {
        let current = this.head;
        for (let i = 0; i < this.count && current != null; i++) {
            if (this.equalsFn(element, current.element)) {
                return i;
            }
            current = current.next;
        }
        return -1;
    }
    // 从链表中移除元素
    remove(element) {
        const index = this.indexOf(element);
        return this.removeAt(index);
    }
    // 获取链表的大小
    size() {
        return this.count;
    }
    // 检查链表是否为空
    isEmpty() {
        return this.size() === 0;
    }
    // 获取链表头部
    getHead() {
        return this.head;
    }
    // 创建toString方法
    toString() {
        if (this.isEmpty()) {
            return "";
        }
        let objString = `${this.head.element}`;
        let current = this.head.next;
        for (let i = 1; i < this.size() && current != null; i++) {
            objString = `${objString}, ${current.element}`;
            current = current.next;
        }
        return objString;
    }
}

双向链表

双向链表和普通链表的区别在于，在链表中，一个节点只有链向下一个节点的链接；而在双向链表中，链接是双向的：一个链向下一个元素，另一个链向前一个元素。

DoublyLinkedList类的模拟实现

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
// 创建新的节点类
class DoublyNode extends Node {
    constructor(element, next, prev) {
        super(element, next);
        this.prev = prev;
    }
}
class DoublyLinkedList extends LinkedList {
    // 构造函数
    constructor(equalsFn = defaultEquals) {
        super(equalsFn);
        this.tail = undefined;
    }
    // 在任意位置插入新元素
    insert(element, index) {
        if (index >= 0 && index <= this.count) {
            const node = new DoublyNode(element);
            let current = this.head;
            if (index === 0) {
                if (this.head == null) {
                    this.head = node;
                    this.tail = node;
                } else {
                    node.next = this.head;
                    current.prev = node;
                    this.head = node;
                }
            } else if (index === this.count) { // 最后一项
                current = this.tail;
                current.next = node;
                node.prev = current;
                this.tail = node;
            } else {
                const previous = this.getElementAt(index - 1);
                current = previous.next;
                node.next = current;
                previous.next = node;
                current.prev = node;
                node.prev = previous;
            }
            this.count++;
            return true;
        }
        return false;
    }
    // 从任意位置移除元素
    removeAt(index) {
        if (index >= 0 && index < this.count) {
            let current = this.head;
            if (index === 0) {
                this.head = current.next;
                // 如果只有一项，更新tail
                if (this.count === 1) {
                    this.tail = undefined;
                } else {
                    this.head.prev = undefined;
                }
            } else if (index === this.count - 1) { // 最后一项
                current = this.tail;
                this.tail = current.prev;
                this.tail.next = undefined;
            } else {
                current = this.getElementAt(index);
                const previous = current.prev;
                // 将previous与current的下一项链接起来——跳过current
                previous.next = current.next;
                current.next.prev = previous;
            }
            this.count--;
            return current.element;
        }
        return undefined;
    }
}

循环链表

循环链表可以像链表一样只有单向引用，也可以像双向链表一样有双向引用。循环链表的链表的唯一区别在于，最后一个元素指向下一个元素的指针（tail.next）不是引用undefined，而是指向第一个元素。双向循环链表有指向head元素的tail.next和指向tail元素的head.prev。

CircularLinkedList类的模拟实现

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
class CircularLinkedList extends LinkedList {
    // 构造函数
    constructor(equalsFn = defaultEquals) {
        super(equalsFn);
    }
    // 在任意位置插入新元素
    insert(element, index) {
        if (index >= 0 && index <= this.count) {
            const node = new Node(element);
            let current = this.head;
            if (index === 0) {
                if (this.head == null) {
                    this.head = node;
                    node.next = this.head;
                } else {
                    node.next = current;
                    current = this.getElementAt(this.size());
                    // 更新最后一个元素
                    this.head = node;
                    current.next = this.head;
                }
            } else {
                const previous = this.getElementAt(index - 1);
                node.next = previous.next;
                previous.next = node;
            }
            this.count--;
            return true;
        }
        return false;
    }
    // 从任意位置移除元素
    removeAt(index) {
        if (index >= 0 && index < this.count) {
            let current = this.head;
            if (index === 0) {
                if (this.size() === 1) {
                    this.head = undefined;
                } else {
                    const removed = this.head;
                    current = this.getElementAt(this.size());
                    this.head = this.head.next;
                    current.next = this.head;
                    current = removed;
                }
            } else {
                // 不需要修改循环链表最后一个元素
                const previous = this.getElementAt(index - 1);
                current = previous.next;
                previous.next = current.next;
            }
            this.count--;
            return current.element;
        }
        return undefined;
    }
    }

有序链表

有序链表是指保持有序的链表结构。除了使用排序算法之外，我们还可以将元素插入到正确的位置来保证链表的有序性。

SortedLinkedList类的模拟实现

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
// 声明Compare常量
const Compare = {
    LESS_THAN: -1,
    BIGGER_THAN: 1
};
// 创建相等性比较函数
function defaultCompare(a, b) {
    if (a === b) {
        return 0;
    }
    return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
class SortedLinkedList extends LinkedList {
    // 构造函数
    constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
        super(equalsFn);
        this.compareFn = compareFn;
    }
    // 有序插入元素
    insert(element, index = 0) {
        if (this.isEmpty()) {
            return super.insert(element, 0);
        }
        const pos = this.getIndexNextSortedElement(element);
        return super.insert(element, pos);
    }
    getIndexNextSortedElement(element) {
        let current = this.head;
        let i = 0;
        for (; i < this.size() && current; i++) {
            const comp = this.compareFn(element, current.element);
            if (comp === Compare.LESS_THAN) {
                return i;
            }
            current = current.next;
        }
        return i;
    }
}

利用链表创建栈

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
class StackLinkedList {
    // 构造函数
    constructor() {
        this.it
        ems = new DoublyLinkedList();
    }
    // 向栈添加元素
    push(element) {
        this.items.push(element);
    }
    // 从栈移除元素
    pop() {
        if (this.isEmpty()) {
            return undefined;
        }
        return this.items.removeAt(this.size() - 1);
    }
    // 查看栈顶元素
    peek() {
        if(this.isEmpty()) {
            return undefined;
        }
        return this.items.getElementAt(this.size() - 1).element;
    }
    // 检查栈是否为空
    isEmpty() {
        return this.items.isEmpty();
    }
    // 获取栈的大小
    size() {
        return this.items.size();
    }
    // 清空栈元素
    clear() {
        this.items.clear();
    }
    // 创建toString方法
    toString() {
        return this.items.toString();
    }
}

除了栈，我们还可以使用LinkedList类及其变种作为内部的数据结构来创建其他的数据结构，例如队列、双端队列等，这里就不再赘述，有兴趣的可以自己实现一下。这里也不再演示这些链表中方法的使用了，有兴趣的可以自己做个demo测试一下，如果有任何的问题，欢迎评论区留言。

Donate
  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.
  • Copyrights © 2020-2021 Sanmu
  • Visitors: | Views:

请我喝杯咖啡吧~

支付宝
微信