数据结构 - 静态链表(JavaScript实现)
源码地址
静态链表(StaticLinkedList)
对于那些没有指针的语言,可以通过数组来描述链表,这种链表叫做静态链表
初始化
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
| class StaticLinkedList { constructor(size=10){ if(size < 3) return null this.list = [] for (let index = 0; index < size; index++) { let node = this.node('') node.next = index + 1 this.list[index] = node } this.list[size-1].next = 0 this.size = size this.expansionSize = size this.length = 0 } node(data) { return { next: 0, data, } } }
|
扩容操作
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| expansion(){ if(this.length >= this.size -2){ let expansionSize = this.size + this.expansionSize this.list[expansionSize - 1] = this.list[this.size-1] for (let index = this.size-1; index < expansionSize - 1; index++) { let node = this.node('') node.next = index + 1 this.list[index] = node } this.size = expansionSize } }
|
基本操作
插入
头部插入
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| prepend(data){ this.expansion() let front = this.list[0] let curr = front.next let head = this.list[this.size-1] let node = this.list[curr] node.data = data front.next = node.next node.next = head.next head.next = curr ++this.length return data }
|
尾部插入
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
| append(data){ this.expansion() let front = this.list[0] let curr = front.next let head = this.list[this.size-1] let node = this.list[curr] node.data = data front.next = node.next if(this.length == 0) { head.next = curr }else { let last = this.list[head.next] while(last.next != 0){ last = this.list[last.next] } last.next = curr } node.next = 0 ++this.length return data }
|
中间插入
从指定的某个值后插入
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
| add(value, data){ this.expansion() let front = this.list[0] let curr = front.next let node = this.list[curr] let currNode = this.contains(value) if(!currNode) return null let next = currNode.next node.data = data front.next = node.next node.next = next currNode.next = curr ++this.length return data }
|
删除
头部删除
从头节点开始删除节点
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
| removeHead(){ let rear = this.list[this.size-1] let headCur = rear.next let currNode = this.list[headCur] if(this.length == 0) return null let next = currNode.next let front = this.list[0] let empty = front.next let data = currNode.data rear.next = next currNode.next = empty currNode.data = '' front.next = headCur --this.length return data }
|
删除尾节点
从尾部删除节点
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
| removeRear(){ let curr = this.list[this.list[this.size-1].next] if(this.length == 0) return null while (curr != this.list[0]){ if(this.list[curr.next].next === 0) break curr = this.list[curr.next] } if(curr == this.list[0]) return this.removeHead() let next = curr.next let rear = this.list[next] let front = this.list[0] let data = rear.data let empty = front.next curr.next = 0 rear.next = empty rear.data = '' front.next = next --this.length return data }
|
删除指定节点
删除指定的节点
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
| remove(el){ let curr = this.list[this.list[this.size-1].next] if(this.length == 0) return null if(curr.data == el) return this.removeHead() while (curr != this.list[0]){ if(this.list[curr.next].data === el) break curr = this.list[curr.next] } let next = curr.next let node = this.list[next] let data = node.data if(data != el) return null let front = this.list[0] let empty = front.next curr.next = node.next front.next = next node.next = empty node.data = '' --this.length return data }
|
查找
- 定位到头节点
- 根据头节点的next往下遍历比对
- 找到就返回
1 2 3 4 5 6 7 8 9 10 11 12 13
| contains(data) { let curr = this.list[this.list[this.size-1].next] if(this.length == 0) return null while (curr != this.list[0]){ if(curr.data === data) break curr = this.list[curr.next] } if(curr == this.list[0]) return null return curr }
|
遍历
正向遍历
1 2 3 4 5 6 7 8 9 10 11 12 13 14
| traverse(callback=(item)=>item){ let res = [] let curr = this.list[this.list[this.size-1].next] if(this.length == 0) return [] while (curr != this.list[0]){ res.push(callback(curr.data)); curr = this.list[curr.next] } return res }
|
反向遍历
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
| reverseTraversal(callback=(item)=>item){ let res = [] let head = this.list[this.list[this.size-1].next] if(this.length == 0) return [] let curr = head while (curr.next != 0){ curr = this.list[curr.next] } while(curr != head){ let prev = head while(this.list[prev.next] != curr){ prev = this.list[prev.next] } res.push(callback(curr.data)) curr = prev } res.push(callback(curr.data)) return res }
|
反转
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
| reverse() { let cur = this.list[this.size-1].next let curr = this.list[cur] let front = this.list[0] let head = curr if(this.length === 0) return null let next = null let prev = null let temp = curr.next let lastCur = 0 prev = curr curr = this.list[temp] while(curr != front){ if(curr.next == 0) cur = next ? next : cur next = curr.next if(lastCur > 0){ let tempCur = lastCur lastCur = temp curr.next = tempCur }else{ curr.next = cur lastCur = prev.next if(next == 0) cur = temp } prev = curr curr = this.list[next] temp = next } head.next = 0 this.list[this.size-1].next = cur return this }
|