目的：ES6标准下的JS数据结构的一些实现代码。（作为记录和启发）

内容：链表和双向链表，循环链表，有序链表。（未完成，待继续）

所有源码在我的Github上（如果觉得不错记得给星鼓励我哦）：ES6的JavaScript数据结构实现之链表

一、基础数据结构

1、链表

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
class Node {
constructor(element, next) {
this.element = element;
this.next = next;
}
}

function defaultEquals(a, b) {
return a === b;
}

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

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;
}
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;
}

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);
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) {
this.head = current.next; 
}else {
const previous = this.getElementAt(index - 1);
current = previous.next;
previous.next = current;

}
this.count--;
return current.element;
}
return undefined;
}

remove(element) {
const index = this.indexOf(element);
return this.removeAt(index);
}

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;
}

isEmpty() {
return this.size() === 0;
}

size() {
return this.count;
}

getHead() {
return this.head;
}

clear() {
this.head = undefined;
this.count = 0;
}

toString() {
if (this.head == null) {
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;
}
}


const list = new LinkedList();

console.log(list);
list.push(15);
console.log(list);
list.push(10);
list.push(5);
console.log(list);
list.removeAt(1);
console.log(list);
list.insert(4,1);
console.log(list);
console.log(list.indexOf(15));
console.log(list.indexOf(1));
list.remove(15);
console.log(list);

LinkedList

LinkedList

2、双向链表

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
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; 
}
push(element) {
const node = new DoublyNode(element);
if (this.head == null) {
this.head = node;
this.tail = node; // NEW
} else {
// attach to the tail node // NEW
this.tail.next = node;
node.prev = this.tail;
this.tail = node;
}
this.count++;
}
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;
this.head.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 = this.head.next;
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.next = current.next;
current.next.prev = previous;
}
this.count--;
return current.element; 
}
return undefined;
}
indexOf(element) {
let current = this.head;
let index = 0;
while (current != null) {
if (this.equalsFn(element, current.element)) {
return index;
}
index++;
current = current.next;
}
return -1;
}
getHead() {
return this.head;
}
getTail() {
return this.tail;
}
clear() {
super.clear();
this.tail = undefined;
}
toString() {
if (this.head == null) {
return '';
}
let objString = `${this.head.element}`;
let current = this.head.next;
while (current != null) {
objString = `${objString},${current.element}`;
current = current.next;
}
return objString;
}
inverseToString() {
// if (this.tail == null) {
// return '';
// }
let objString = `${this.tail.element}`;
let previous = this.tail.prev;
while (previous != null) {
objString = `${objString},${previous.element}`;
previous = previous.prev;
}
return objString;
}
}


const list = new DoublyLinkedList();
list.push(20);
console.log(list);
list.push(19);
list.push(18);
console.log(list);
list.insert(15, 1);
console.log(list);
list.removeAt(1);
console.log(list);
console.log(list.toString());
console.log(list.inverseToString());

DoublyNode

3、循环链表（以扩展上述普通链表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
class CircularLinkedList extends LinkedList {
  constructor(equalsFn = defaultEquals) {
    super(equalsFn);
  }
  push(element) {
    const node = new Node(element);
    let current;
    if (this.head == null) {
      this.head = node;
    } else {
      current = this.getElementAt(this.size() - 1);
      current.next = node;
    }
    // set node.next to head - to have circular list
    node.next = this.head;
    this.count++;
  }
  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) {
          // if no node  in list
          this.head = node;
          node.next = this.head;
        } else {
          node.next = this.head;
          current = this.getElementAt(this.size());
          // update last element
          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() - 1);
          this.head = this.head.next;
          current.next = this.head;
          current = removed;
        }
      } else {
        // no need to update last element for circular list
        const previous = this.getElementAt(index - 1);
        current = previous.next;
        previous.next = current.next;
      }
      this.count--;
      return current.element;
    }
    return undefined;
  }
}


const list = new CircularLinkedList();

list.push(20);
console.log(list);
list.push(19);
list.push(18);
console.log(list);
list.insert(15, 0);
console.log(list);
list.removeAt(0);
console.log(list);

CircularLinkedList

4、有序链表

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
class Node {
  constructor(element, next) {
    this.element = element;
    this.next = next;
  }
}

function defaultEquals(a, b) {
  return a === b;
}

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};

function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}
class SortedLinkedList extends LinkedList {
  constructor(equalsFn = defaultEquals, compareFn = defaultCompare) {
    super(equalsFn);
    this.equalsFn = equalsFn;
    this.compareFn = compareFn;
  }
  push(element) {
    if (this.isEmpty()) {
      super.push(element);
    } else {
      const index = this.getIndexNextSortedElement(element);
      super.insert(element, index);
    }
  }
  insert(element, index = 0) {
    if (this.isEmpty()) {
      return super.insert(element, index === 0 ? index : 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;
  }
}

const list = new SortedLinkedList();
for (let i = 5; i > 0; i--) {
  list.push(i);
}
console.log(list);
list.insert(1);
console.log(list);

SortedLinkedList

​