本文目錄一覽：
js數組和鏈表的區別
首先從邏輯結構上說，兩者都是數據結構的一種，但存在區別，數組是申請的一塊連續的內存空間，並且是在編譯階段就要確定空間大小的，同時在運行階段是不允許改變的，所以它不能夠隨着需要的改變而增加或減少空間大小，所以當數據量大的時候，有可能超出了已申請好的數組上限，產生數據越界，或者是數據量很小，對於沒有使用的數組空間，造成內存浪費。鏈表則是動態申請的內存空間，並不像數組一樣需要事先申請好大小，鏈表是現用現申請就OK，根據需求動態的申請或刪除內存空間，對於的是增加或刪除數據，所以比數組要靈活。再從物理存儲即內存分配上分析，數組是連續的內存，對於訪問數據，可以通過下標直接讀取，時間複雜度為O(1)，而添加刪除數據就比較麻煩，需要移動操作數所在位置後的所有數據，時間複雜度為O（N）。鏈表是物理上非連續的內存空間，對於訪問數據，需要從頭便利整個鏈表直到找到要訪問的數據，沒有數組有效，但是在添加和刪除數據方面，只需要知道操作位置的指針，很方便可以實現增刪，教數組比較靈活有效率。所以綜合以上，對於快速訪問數據，不經常有添加刪除操作的時候選擇數組實現，而對於經常添加刪除數據，對於訪問沒有很高要求的時候選擇鏈表。
【JS算法】 刪除鏈表中某個節點
先來了解一個基礎知識
b=a，但改變 b，並不會影響 a
y=x , 但改變y，會影響x，因為class有原型鏈
1=2=3，鏈表是由一組節點組成的集合。每個節點都使用一個對象的引用指向它的後繼，指向另一個節點的引用叫做鏈
給你一個鏈表的頭節點 head 和一個整數 val ，請你刪除鏈表中所有滿足 Node.val == val 的節點，並返回 新的頭節點 。
輸入：head = [1,2,6,3,4,5,6] val = 6
輸出：[1,2,3,4,5]
JS中 數組與鏈表
常規數組： 數組元素內容是一種類型的元素，如const arr = [1,2,3,4]，在存儲空間是連續內存的
JS數組： 數組元素內容不是同一種類型的元素，如const arr = [‘haha’, 1, {a:1}]，則在存儲上是一段非連續空間。此時，JS 數組不再具有數組的特徵，其底層其實是由鏈表來實現的
總結
鏈表的插入/刪除效率較高，而訪問效率較低；
數組的訪問效率較高，而插入效率較低
js鏈表怎麼去輸入啊
//Node表示要加入列表的項
var Node=function(element){
this.element=element;
this.next=null;
};
var length=0;//存儲列表項的數量
var head=null;//head存儲的是第一個節點的引用
//向鏈表尾部追加元素
this.append=function(element){
var node=new Node(element),
current;
if(head===null){
head=node;
}else{
current=node;
while(current.next){
current=current.next;
}
current.next=node;
}
length++;
};
//在鏈表的任意位置插入元素
this.insert=function(position,element){
if(position=0position=length){
var node=new Node(element),
current=head,
previous,
index=0;
if(position===0){
node.next=current;
head=node;
}else{
while(indexposition){
previous=current;
previous.next=node;
index++;
}
node.next=current;
previous.next=node;
}
length++;
return true;
}else{
return false;
}
};
//從鏈表中移除元素
this.removeAt=function(position){
if(position-1 positionlength){
var current=head,
previous,
index=0;
if(position===0){
head=current.next;
}else{
while(indexposition){
previous=current;
current=current.next;
index++;
}
previous.next=current.next;
}
length–;
return current.element;
}else{
return null;
}
};
//返回元素在鏈表中的位置
this.indexOf=function(element){
var current=head,
index=-1;
while(current){
if(element===current.element){
return index;
}
index++;
current=current.next;
}
return -1;
};
//移除某個元素
this.remove=function(element){
var index=this.indexOf(element);
return this.removeAt(index);
};
//判斷鏈表是否為空
this.isEmpty=function(){
return length===0;
};
//返回鏈表的長度
this.size=function(){
return length;
};
//把LinkedList對象轉換成一個字符串
this.toString=function(){
var current=head,
string=””;
while(current){
string=current.element;
current=current.next;
}
return string;
};
};
var list=new LinkedList();
list.append(15);
list.append(10);
list.insert(1,11);
list.removeAt(2)
console.log(list.size());
鏈表（帶頭結點）基本操作實驗
單鏈表的刪除操作是指刪除第i個結點，返回被刪除結點的值。刪除操作也需要從頭引用開始遍歷單鏈表，直到找到第i個位置的結點。如果i為1，則要刪除第一個結點，則需要把該結點的直接後繼結點的地址賦給頭引用。對於其它結點，由於要刪除結點，所以在遍歷過程中需要保存被遍歷到的結點的直接前驅，找到第i個結點後，把該結點的直接後繼作為該結點的直接前驅的直接後繼。刪除操作如圖
單鏈表的刪除操作示意圖
刪除操作的算法實現如下：
public T Delete(int i)
{
if (IsEmpty()|| i 0)
{
Console.WriteLine(“Link is empty or Position is error!”);
return default(T);
}
Node q = new Node();
if (i == 1)
{
q = head;
head = head.Next;
return q.Data;
}
Node p = head;
int j = 1;
while (p.Next != null j i)
{
++j;
q = p;
p = p.Next;
}
if (j == i)
{
q.Next = p.Next;
return p.Data;
}
else
{
Console.WriteLine(“The ith node is not exist!”);
return default(T);
}
}
算法的時間複雜度分析：單鏈表上的刪除操作與插入操作一樣，時間主要消耗在結點的遍歷上。如果表為空則不進行遍歷。當表非空時，刪除第i個位置的結點， i等於1遍歷的結點數最少（1個），i等於n遍歷的結點數最多（n個，n為單鏈表的長度），平均遍歷的結點數為n/2。所以，刪除操作的時間複雜度為O（n）。
js 刪除鏈表中重複的節點
題目描述：
給定一個排序的鏈接列表，刪除所有具有重複數字的節點，從原始列表中只留下不同的數字。
例如， 給定1- 2- 3- 3- 4- 4- 5，返回1- 2- 5。
給定1- 1- 1- 2- 3，返回2- 3。
JavaScript 版數據結構與算法（三）鏈表
可以看出JavaScript中的鏈表是通過不斷 new 出來節點，並在節點的next屬性上繼續 new 創建出來的
結構大概長這樣：
參考資料：
原創文章，作者：RAHEU，如若轉載，請註明出處：https://www.506064.com/zh-hant/n/324536.html
微信掃一掃 
支付寶掃一掃 