不同的数据结构适合不同的业务需求,有时候数组不能满足我们的性能要求,比如数组的塌陷问题,在工作过程中就有可能需要用到链表,今天我们一起实现一个(单向)链表。
?需要有基本的增删改查的功能:add、remove、set、get、revert
// 链表的节点类
class Node{
constructor(ele,next){
this.element = ele;
this.next = next;
}
}
class LinkedList{
constructor(){
this.head = null;
this.size = 0;
}
// 私有属性、获取下标为index的节点
_node(index){
let cur = this.head;
for(let i=0;i<index;i++){
cur = cur.next;
}
return cur;
}
add(index,ele){ // 增
if(typeof ele == 'undefined'){
ele = index;
index = this.size;
}
if(this.size === 0){
let node = new Node(ele,null);
this.head = node;
}else{
let preNode = this._node(index-1); // 前一位的值
let node = new Node(ele,preNode.next);
preNode.next = node;
}
this.size++;
}
remove(index){ // 删
let removeNode;
if(index == 0){
removeNode = this.head;
this.head = this.head.next;
}else{
let pre = this._node(index-1);
removeNode = pre.next;
pre.next = pre.next.next;
}
this.size--;
return removeNode;
}
set(index,ele){ // 改
let node = this._node(index);
node.element = ele;
return node;
}
get(index){ // 查
return this._node(index);
}
revert(){
function reverse(head){
if(head == null || head.next == null){
return head;
}
let newHead= reverse(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
this.head = reverse(this.head);
return this.head;
}
}
let linkedList = new LinkedList();
linkedList.add(0);
linkedList.add(2);
linkedList.add(1,1);
linkedList.add(3);
linkedList.add(4);
linkedList.add(5);
console.dir(linkedList,{depth:1000});
linkedList.remove(2);
console.dir(linkedList,{depth:1000});
linkedList.add(2,2);
console.dir(linkedList,{depth:1000});
linkedList.set(0,99);
console.dir(linkedList,{depth:1000});
module.exports = LinkedList;
反转的结果:
不队列的特点:先进先出
?只有入队和出队的功能:add、offer
const LinkedList = require('./Linkedlist');
class Queue{
constructor(){
this.linkedList = new LinkedList();
}
add(ele){
this.linkedList.add(ele);
}
offer(){
this.linkedList.remove(0);
}
}
let queue = new Queue();
queue.add(1);
queue.add(2);
queue.add(3);
console.dir(queue,{depth:1000})
queue.offer();
console.dir(queue,{depth:1000})
逆水行舟,不进则退!