链表是什么及链表相对于数组的优缺点
跟数组比起来优点,插入跟删除的性能高很多,因为不会改变其它node;缺点是查找复杂很多,不能根据下标直接查找,需要从头到尾查找,
方法有:append;toString;insert(向列表的特定位置插入一个新的项);update(简单没写);get(简单没写);indexOf(简单没写);removeAt;remove(简单没写);
链表是什么:如图
代码如下:
class Node {
constructor(element) {
this.element = element
// this.prev = previous
this.next = null
}
}
class DoublyLinkedList {
constructor() {
this.length = 0
this.head=null;//链表的第一个节点
};
append(element) {
let newNode = new Node(element)
if(this.length == 0){
this.head = newNode
}else{
//找到节点的next指向null的node,将此node的next只想newNode;
let current = this.head
while(current.next){
current = current.next
}
current.next = newNode
}
this.length+=1
};
toString(){//链表扁平化
let current = this.head
let listString = ''
while(current){
listString+=current.element+" "
current = current.next
}
return listString
};
insert(position,element){//在特定位置加入node
// 1:检测越界问题
if(position<0||position>this.length)return false
let newNode = new Node(element)
var current = this.head
var pervious = null
let index = 0
//两种情况,position为0或者不为0
if(position == 0){//插入的节点的next指向this.head;然后this.head等于当前节点;相当于把this.head挤到第二位
newNode.next = this.head;//newNode.next本来为null
this.head = newNode
}else{//当前情况,插入的节点的next指向原先position位置的node;原先position位置的node的next指向插入的节点
//找到position位置的node
while(index++<position){
pervious = current
current = current.next
}
newNode.next = current
pervious.next = newNode
}
this.length+=1
return true
};
removeAt(position){
if(position<0||position>this.length)return false
// 也是两种情况
let [current,previous,index] = [this.head,null,0]
if(position == 0){
this.head = current.next
}else{//找到position位置;previous.next指向position位置的node的next;
while(index++ <position){
previous = current
current = current.next
}
previous.next = current.next
}
this.length-=1
return current.element
}
}
let doublyLinkedList = new DoublyLinkedList()
doublyLinkedList.append("aaa")
doublyLinkedList.append("bbb")
doublyLinkedList.append("ccc")
doublyLinkedList.append("ddd")
doublyLinkedList.append("eee")
doublyLinkedList.insert(2,"insert")
doublyLinkedList.insert(2,"insertB")
doublyLinkedList.removeAt(5)//ddd
doublyLinkedList.removeAt(3)//insert
console.log(doublyLinkedList.toString())
console.log(doublyLinkedList)
