参阅基础

  • 学习 JavaScript 数据结构与算法（第六章-链表）

定义

链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。

LinkedList 类

第一步：创建 LinkedList.js

职责:

  • push(element):向链表尾部添加一个新元素。
  • removeAt(position): 从链表的特定位置移出一个元素。
  • insert(element,postion): 向链表的特定位置插入一个新元素。
  • size(): 返回链表包含的元素个数。
  • isEmpty(): 如果链表中不包含任何元素，返回 true，如果链表长度大于 0 则返回 false。
  • getElementAt(index): 返回链表中特定位置的元素。如果链表中不存在这样的元素，则返回 undefined。
  • indexOf(element): 返回元素在链表中的索引。如果链表中没有该元素则返回-1。
  • remove(element): 从链表中删除一个元素。
  • toString(): 返回表示整个链表的字符串。由于列表项使用了 Node 类，就需要重新继承 JavaScript 对象默认的 toString 方法，让其只输出一个元素的值。

实现:

  • LinkedList.prototype.size()
  • LinkedList.prototype.isEmpty()
  • LinkedList.prototype.push(element)
  • LinkedList.prototype.removeAt(position)
  • LinkedList.prototype.insert(element,postion)
  • LinkedList.prototype.getElementAt(index)
  • LinkedList.prototype.indexOf(element)
  • LinkedList.prototype.remove(element)
  • LinkedList.prototype.toString()
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
function defaultEquals(a, b) {
    return a === b;
}

class Node {
    constructor(element) {
        this.element = element;
        this.next = undefined;
    }
}

export default class LinkedList {
    constructor(equalsFn = defaultEquals) {
        this.count = 0;
        this.head = undefined;
        this.equalsFn = equalsFn;
    }

    size() {
        return this.count;
    }

    isEmpty() {
        return this.count > 0 ? true : false;
    }

    // push(element):向链表尾部添加一个新元素
    push(element) {
        // 创建指针
        let current;
        const node = new Node(element);
        if (this.head == null) {
            this.head = node;
        } else {
            current = this.head;
            while (current.next != null) {
                current = current.next;
            }
            //  将其next赋为新元素，建立连接
            current.next = node;
        }
        this.count++;
    }

    // removeAt(position): 从链表的特定位置移出一个元素
    removeAt(position) {
        // 处理越界值
        if (position >= 0 && position <= this.size()) {
            let current = this.head;
            // position == 0
            if (position === 0) {
                this.head = current.next;
            }
            // position == this.size(),position == 元素中间
            else {
                let previous;
                for (let i = 0; i < position; i++) {
                    previous = current;
                    current = current.next;
                }
                previous.next = current.next;
            }
            this.count--;
            return current.element;
        }
        return undefined;
    }

    // insert(element,postion): 向链表的特定位置插入一个新元素
    insert(element, position) {
        if (position >= 0 && position <= this.size()) {
            let current = this.head;
            const node = new Node(element);
            // position == 0
            if (position == 0) {
                if (this.size() === 0) {
                    this.head = node;
                } else {
                    node.next = current;
                    this.head = node;
                }
            }
            // position == this.size(),position == 元素中间
            else {
                const previous = this.getElementAt(position - 1);
                current = previous.next;
                previous.next = node;
                node.next = current;
            }
            this.count++;
            return true;
        }
        return false;
    }

    // getElementAt(index): 返回链表中特定位置的元素。如果链表中不存在这样的元素，则返回undefined
    getElementAt(index) {
        if (index >= 0 && index <= this.size()) {
            let current = this.head;
            for (let i = 0; i < index && current != null; i++) {
                current = current.next;
            }
            return current;
        } else {
            return undefined;
        }
    }

    // indexOf(element): 用户输入元素后在链表中进行匹配，找到了就返回索引，否则返回-1
    // 使用默认算法无法比对对象类型，只能对原始类型有效
    indexOf(element) {
        let current = this.head;
        for (let i = 0; i < this.size(); i++) {
            if (this.equalsFn(current.element, element)) {
                return i;
            }
            current = current.next;
        }
        return -1;
    }

    // remove(element): 通过元素来检索并删除某一个元素
    remove(element) {
        const index = this.indexOf(element);
        return this.removeAt(index);
    }

    // getHead(): 返回头元素
    getHead() {
        return this.head;
    }

    // toString() 将链表元素字串化输出
    toString() {
        if (this.head == null) {
            return '';
        }

        let objString = `${this.head.element}`;
        let current = this.head.next;
        for (let i = 1; i < this.size() && current.element != null; i++) {
            objString = `${objString},${current.element}`;
            current = current.next;
        }

        return objString;
    }
}

使用实例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
<!DOCTYPE html>
<html lang="en">
    <head>
        <meta charset="UTF-8" />
        <meta http-equiv="X-UA-Compatible" content="IE=edge" />
        <meta name="viewport" content="width=device-width, initial-scale=1.0" />
        <title>Document</title>
    </head>
    <body>
        <script type="module">
            import LinkList from './LinkedList.js';
            const linkList = new LinkList();
            linkList.push(2);
            linkList.insert(3, linkList.size());
            linkList.insert(4, 1);
            console.log(linkList.indexOf(3));
            console.log(linkList.toString());

            // linkList.removeAt(0);

            console.log(linkList);
        </script>
    </body>
</html>