JavaScript-Data-Structures-and-Alo/LinkedList.html at master · cqA7/JavaScript-Data-Structures-and-Alo · GitHub

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
<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>linkedList</title>
</head>
<body>
<script>
    /*
    * 单链表
    * */
    function LinkedList() {

        let Nodes = function (element) {
            this.element = element;
            this.next = null;//存储第一个节点的引用
        };

        //内部私有变量
        let length = 0;
        let head = null;

        //append(element) 向列表的尾部添加一个新的项
        this.append = function (element) {
            let node = new Nodes(element),
                current;
            if (head === null) {
                head = node;
            } else {
                current = head;
                while (current.next) {
                    current = current.next;
                }
                current.next = node;
            }
            length++;
        };
        //insert(position,element)向列表项的特定位置插入一个新的项
        this.insert = function (position, element) {
            if (position >= 0 && position <= length) {
                let node = new Nodes(element),
                    current = head,
                    provious,
                    index = 0;
                if (position === 0) {
                    node.next = current;
                    head = node;
                } else {
                    while (index++ < position) {
                        provious = current;
                        current = current.next;
                    }
                    provious.next = node;
                    node.next = current;
                }
                length++;
            } else {
                return false;
            }
        };

        //remove(element) 从列表中移除一项
        /*this.remove = function (element) {
            let current = head,
                provious;
            if (current.element === element) {
                head = current.next;
            } else {
                while (current.next) {
                    provious = current;
                    current = current.next;
                    if (current.element === element) {
                        provious.next = current.next;
                        return current.element;
                    }
                }
                return null;
            }
        };*/
        this.remove = function (element) {
            let index = this.indexOf(element);
            return this.removeAt(index);
        };

        //indexOf(element) 返回元素在列表中的索引，如果列表中无此元素则返回-1
        this.indexOf = function (element) {
            let current = head,
                index = 0;
            while (current) {
                if (current.element === element) {
                    return index;
                }
                index++;
                current = current.next;
            }
            return -1;
        };

        //removeAt(position) 从列表的特定位置移除一项
        this.removeAt = function (position) {
            //检测越界
            if (position > -1 && position < length) {
                let current = head,
                    provious,
                    index = 0;
                if (position === 0) {
                    head = current.next;
                } else {
                    while (index++ < position) {
                        provious = current;
                        current = current.next;
                    }
                    provious.next = current.next;
                }
                length--;
                return current.element;
            } else {
                return null;
            }
        };

        //isEmpty() 如果链表中不包含任何元素，则返回true，否则返回false
        this.isEmpty = function () {
            return length === 0;
        };

        //size() 返回链表中包含的元素的个数。
        this.size = function () {
            return length;
        };

        //toString() 由于列表中使用了Node类,就需要重写继承自Javascript对象默认的toString方法，让其只输出元素的值
        this.toString = function () {
            let current = head,
                string = "";
            while (current) {
                string += "," + current.element;
                current = current.next;
            }
            return string.slice(1);
        };

        //getHead
        this.getHead = function () {
            return head;
        };

        //print 输出链表
        this.print = function () {
            console.log(this.toString());
        }
    }

    //test
    let list = new LinkedList();
    console.log(list.isEmpty());
    list.append("Jack");
    list.append("Tom");
    list.append("Sinla");
    list.insert(2, "Jhon");
    list.removeAt(2);
    console.log(list.indexOf("Tom"));
    console.log(list.isEmpty());
    console.log(list.size());
    console.log(list.getHead());
    list.print();
</script>
</body>
</html>