数组缺点:(大多数语言中)数组的大小是固定的,从数组的起点或者中间插入或者一处项的成本太高,因为需要移动元素(js中的array类可以帮我们做这些事情,但背后的情况同样是这样的)
链表:1.存储有序的的元素集合,不同于数组,链表中的元素在内存中不是连续放置的。每个元素有一个存储元素本身的节点和一个指向下一个元素的引用(指针或链接)2.添加或移除元素不需要移动其他元素 3.遍历的时候需要从头开始迭代
//代码实现
function LinkedList(){
let head = null;
let length = 0;
let Node = function(val){
this.val = val;
this.next = null;
}
this.append = function(val){
let node = new Node(val),current;
if(length === 0){
head = node;
}else{
current = head;
while(current.next){
current = current.next;
}
current.next = node;
}
length++;
}
this.remove = function(index){
if(index < -1 || index >= length){
return;
}else{
let current = head,previous = null;
if(index === 0){
head = current.next
}else{
for(let i = 0; i < index;i++){
previous = current;
current = current.next;
}
//当前移除的元素会被丢弃在计算机内存中,等着被垃圾回收器清除
previous.next = current.next;
}
length--;
return current.val
}
}
this.insert = function(index,val){
if(index < -1 || index >= length ){
return;
}else{
let current = head,previous = null;
let node = new Node(val)
if(index === 0){
node.next = current;
head = node;
}else{
for(let i = 0; i < index; i++){
previous = current;
current = current.next;
}
node.next = current;
previous.next = node;
}
length++;
}
}
this.isEmpty = function(){
return length === 0
}
this.toString = function(){
let current = head,str = "";
while(current){
str += current.val+",";
// console.log(current.val)
current = current.next;
}
return str
}
this.getHead = function(){
return head;
}
}
let link = new LinkedList();
link.append(1)
link.append(4)
link.append(5)
link.append(6)
console.log(link.remove(0))
link.insert(0,1)
link.insert(1,2)
console.log(link.toString())
//将文件导出
module.exports = {
LinkedList:LinkedList
}
双向链表优点:解决单向链表中获取当前节点前驱需要从头遍历的问题
网友评论