這篇文章主要為大家展示了“JS中鏈表Linked-list有什么用”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“JS中鏈表Linked-list有什么用”這篇文章吧。
前面我們討論了如何使用棧、隊(duì)列進(jìn)行存數(shù)數(shù)據(jù)，他們其實(shí)都是列表的一種，底層存儲(chǔ)的數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)都是數(shù)組。
但是數(shù)組不總是最佳的數(shù)據(jù)結(jié)構(gòu)，因?yàn)?，在很多編程語(yǔ)言中，數(shù)組的長(zhǎng)度都是固定的，如果數(shù)組已被數(shù)據(jù)填滿，再要加入新的元素是非常困難的。而且，對(duì)于數(shù)組的刪除和添加操作，通常需要將數(shù)組中的其他元素向前或者向后平移，這些操作也是十分繁瑣的。
然而，JS中數(shù)組卻不存在上述問(wèn)題，主要是因?yàn)樗麄儽粚?shí)現(xiàn)了成了對(duì)象，但是與其他語(yǔ)言相比（比如C或Java），那么它的效率會(huì)低很多。
這時(shí)候，我們可以考慮使用鏈表(Linked-list) 來(lái)替代它，除了對(duì)數(shù)據(jù)的隨機(jī)訪問(wèn)，鏈表幾乎可以在任何可以使用一維數(shù)組的情況中。如果你正巧在使用C或者Java等高級(jí)語(yǔ)言，你會(huì)發(fā)現(xiàn)鏈表的表現(xiàn)要優(yōu)于數(shù)組很多。
鏈表其實(shí)有許多的種類：?jiǎn)蜗蜴湵?、雙向鏈表、單向循環(huán)鏈表和雙向循環(huán)鏈表，接下來(lái)，我們基于對(duì)象來(lái)實(shí)現(xiàn)一個(gè)單向鏈表，因?yàn)樗氖褂米顬閺V泛。
首先，要實(shí)現(xiàn)鏈表，我們先搞懂一些鏈表的基本東西，因?yàn)檫@很重要！
鏈表是一組節(jié)點(diǎn)組成的集合，每個(gè)節(jié)點(diǎn)都使用一個(gè)對(duì)象的引用來(lái)指向它的后一個(gè)節(jié)點(diǎn)。指向另一節(jié)點(diǎn)的引用講做鏈。下面我畫(huà)了一個(gè)簡(jiǎn)單的鏈接結(jié)構(gòu)圖，方便大家理解。
鏈表結(jié)構(gòu)圖
其中，data中保存著數(shù)據(jù)，next保存著下一個(gè)鏈表的引用。上圖中，我們說(shuō) data2 跟在 data1 后面，而不是說(shuō) data2 是鏈表中的第二個(gè)元素。上圖，值得注意的是，我們將鏈表的尾元素指向了 null 節(jié)點(diǎn)，表示鏈接結(jié)束的位置。
由于鏈表的起始點(diǎn)的確定比較麻煩，因此很多鏈表的實(shí)現(xiàn)都會(huì)在鏈表的最前面添加一個(gè)特殊的節(jié)點(diǎn)，稱為 頭節(jié)點(diǎn)，表示鏈表的頭部。進(jìn)過(guò)改造，鏈表就成了如下的樣子：
有頭節(jié)點(diǎn)的鏈表
向鏈表中插入一個(gè)節(jié)點(diǎn)的效率很高，需要修改它前面的節(jié)點(diǎn)(前驅(qū))，使其指向新加入的節(jié)點(diǎn)，而將新節(jié)點(diǎn)指向原來(lái)前驅(qū)節(jié)點(diǎn)指向的節(jié)點(diǎn)即可。下面我將用圖片演示如何在 data2 節(jié)點(diǎn) 后面插入 data4 節(jié)點(diǎn)。
插入節(jié)點(diǎn)
同樣，從鏈表中刪除一個(gè)節(jié)點(diǎn)，也很簡(jiǎn)單。只需將待刪節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)指向待刪節(jié)點(diǎn)的，同時(shí)將待刪節(jié)點(diǎn)指向null，那么節(jié)點(diǎn)就刪除成功了。下面我們用圖片演示如何從鏈表中刪除 data4 節(jié)點(diǎn)。
刪除節(jié)點(diǎn)
我們?cè)O(shè)計(jì)鏈表包含兩個(gè)類，一個(gè)是 Node 類用來(lái)表示節(jié)點(diǎn)，另一個(gè)事 LinkedList 類提供插入節(jié)點(diǎn)、刪除節(jié)點(diǎn)等一些操作。
Node類
Node類包含連個(gè)屬性： element 用來(lái)保存節(jié)點(diǎn)上的數(shù)據(jù)，next 用來(lái)保存指向下一個(gè)節(jié)點(diǎn)的鏈接，具體實(shí)現(xiàn)如下：
重慶分公司
重慶分公司
//節(jié)點(diǎn)
function Node(element) {
this.element = element; //當(dāng)前節(jié)點(diǎn)的元素
this.next = null; //下一個(gè)節(jié)點(diǎn)鏈接
}LinkedList類
LinkedList類提供了對(duì)鏈表進(jìn)行操作的方法，包括插入刪除節(jié)點(diǎn)，查找給定的值等。值得注意的是，它只有一個(gè)屬性，那就是使用一個(gè) Node 對(duì)象來(lái)保存該鏈表的頭節(jié)點(diǎn)。
它的構(gòu)造函數(shù)的實(shí)現(xiàn)如下：
//鏈表類
function LList () {
this.head = new Node( 'head' ); //頭節(jié)點(diǎn)
this.find = find; //查找節(jié)點(diǎn)
this.insert = insert; //插入節(jié)點(diǎn)
this.remove = remove; //刪除節(jié)點(diǎn)
this.findPrev = findPrev; //查找前一個(gè)節(jié)點(diǎn)
this.display = display; //顯示鏈表
}head節(jié)點(diǎn)的next屬性初始化為 null ，當(dāng)有新元素插入時(shí)，next會(huì)指向新的元素。
接下來(lái)，我們來(lái)看看具體方法的實(shí)現(xiàn)。
insert：向鏈表插入一個(gè)節(jié)點(diǎn)
我們先分析分析insert方法，想要插入一個(gè)節(jié)點(diǎn)，我們必須明確要在哪個(gè)節(jié)點(diǎn)的前面或后面插入。我們先來(lái)看看，如何在一個(gè)已知節(jié)點(diǎn)的后面插入一個(gè)節(jié)點(diǎn)。
在一個(gè)已知節(jié)點(diǎn)后插入新節(jié)點(diǎn)，我們首先得找到該節(jié)點(diǎn)，為此，我們需要一個(gè) find 方法用來(lái)遍歷鏈表，查找給定的數(shù)據(jù)。如果找到，該方法就返回保存該數(shù)據(jù)的節(jié)點(diǎn)。那么，我們先實(shí)現(xiàn) find 方法。
find：查找給定節(jié)點(diǎn)
//查找給定節(jié)點(diǎn)
function find ( item ) {
var currNode = this.head;
while ( currNode.element != item ){
currNode = currNode.next;
}
return currNode;
}find 方法同時(shí)展示了如何在鏈表上移動(dòng)。首先，創(chuàng)建一個(gè)新節(jié)點(diǎn)，將鏈表的頭節(jié)點(diǎn)賦給這個(gè)新創(chuàng)建的節(jié)點(diǎn)，然后在鏈表上循環(huán)，如果當(dāng)前節(jié)點(diǎn)的 element 屬性和我們要找的信息不符，就將當(dāng)前節(jié)點(diǎn)移動(dòng)到下一個(gè)節(jié)點(diǎn)，如果查找成功，該方法返回包含該數(shù)據(jù)的節(jié)點(diǎn)；否則，就會(huì)返回null。
一旦找到了節(jié)點(diǎn)，我們就可以將新的節(jié)點(diǎn)插入到鏈表中了，將新節(jié)點(diǎn)的 next 屬性設(shè)置為后面節(jié)點(diǎn)的 next 屬性對(duì)應(yīng)的值，然后設(shè)置后面節(jié)點(diǎn)的 next 屬性指向新的節(jié)點(diǎn)，具體實(shí)現(xiàn)如下：
//插入節(jié)點(diǎn)
function insert ( newElement , item ) {
var newNode = new Node( newElement );
var currNode = this.find( item );
newNode.next = currNode.next;
currNode.next = newNode;
}現(xiàn)在我們可以測(cè)試我們的鏈表了。等等，我們先來(lái)定義一個(gè) display 方法顯示鏈表的元素，不然我們?cè)趺粗缹?duì)不對(duì)呢？
display：顯示鏈表
//顯示鏈表元素
function display () {
var currNode = this.head;
while ( !(currNode.next == null) ){
console.log( currNode.next.element );
currNode = currNode.next;
}
}實(shí)現(xiàn)原理同上，將頭節(jié)點(diǎn)賦給一個(gè)新的變量，然后循環(huán)鏈表，直到當(dāng)前節(jié)點(diǎn)的 next 屬性為 null 時(shí)停止循環(huán)，我們循環(huán)過(guò)程中將每個(gè)節(jié)點(diǎn)的數(shù)據(jù)打印出來(lái)就好了。
var fruits = new LList();
fruits.insert('Apple' , 'head');
fruits.insert('Banana' , 'Apple');
fruits.insert('Pear' , 'Banana');
console.log(fruits.display()); // Apple
// Banana
// Pearremove：從鏈表中刪除一個(gè)節(jié)點(diǎn)
從鏈表中刪除節(jié)點(diǎn)時(shí)，我們先要找個(gè)待刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，找到后，我們修改它的 next 屬性，使其不在指向待刪除的節(jié)點(diǎn)，而是待刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。那么，我們就得需要定義一個(gè) findPrevious 方法遍歷鏈表，檢查每一個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)是否存儲(chǔ)待刪除的數(shù)據(jù)。如果找到，返回該節(jié)點(diǎn)，這樣就可以修改它的 next 屬性了。 findPrevious 的實(shí)現(xiàn)如下：
//查找?guī)h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
function findPrev( item ) {
var currNode = this.head;
while ( !( currNode.next == null) && ( currNode.next.element != item )){
currNode = currNode.next;
}
return currNode;
}這樣，remove 方法的實(shí)現(xiàn)也就迎刃而解了
//刪除節(jié)點(diǎn)
function remove ( item ) {
var prevNode = this.findPrev( item );
if( !( prevNode.next == null ) ){
prevNode.next = prevNode.next.next;
}
}我們接著寫(xiě)一段測(cè)試程序，測(cè)試一下 remove 方法：
// 接著上面的代碼，我們?cè)偬砑右粋€(gè)水果
fruits.insert('Grape' , 'Pear');
console.log(fruits.display()); // Apple
// Banana
// Pear
// Grape
// 我們把香蕉吃掉
fruits.remove('Banana');
console.log(fruits.display()); // Apple
// Pear
// GrapeGreat！成功了，現(xiàn)在你已經(jīng)可以實(shí)現(xiàn)一個(gè)基本的單向鏈表了。
盡管從鏈表的頭節(jié)點(diǎn)遍歷鏈表很簡(jiǎn)單，但是反過(guò)來(lái)，從后向前遍歷卻不容易。我們可以通過(guò)給Node類增加一個(gè)previous屬性，讓其指向前驅(qū)節(jié)點(diǎn)的鏈接，這樣就形成了雙向鏈表，如下圖：
雙向鏈表
此時(shí)，向鏈表插入一個(gè)節(jié)點(diǎn)就要更改節(jié)點(diǎn)的前驅(qū)和后繼了，但是刪除節(jié)點(diǎn)的效率提高了，不再需要尋找待刪除節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)了。
要實(shí)現(xiàn)雙向鏈表，首先需要給 Node 類增加一個(gè) previous 屬性：
//節(jié)點(diǎn)類
function Node(element) {
this.element = element; //當(dāng)前節(jié)點(diǎn)的元素
this.next = null; //下一個(gè)節(jié)點(diǎn)鏈接
this.previous = null; //上一個(gè)節(jié)點(diǎn)鏈接
}雙向鏈表的 insert 方法與單鏈表相似，但需要設(shè)置新節(jié)點(diǎn)的 previous 屬性，使其指向該節(jié)點(diǎn)的前驅(qū)，定義如下：
//插入節(jié)點(diǎn)
function insert ( newElement , item ) {
var newNode = new Node( newElement );
var currNode = this.find( item );
newNode.next = currNode.next;
newNode.previous = currNode;
currNode.next = newNode;
}雙向鏈表的刪除 remove 方法比單鏈表效率高，不需要查找前驅(qū)節(jié)點(diǎn)，只要找出待刪除節(jié)點(diǎn)，然后將該節(jié)點(diǎn)的前驅(qū) next 屬性指向待刪除節(jié)點(diǎn)的后繼，設(shè)置該節(jié)點(diǎn)后繼 previous 屬性，指向待刪除節(jié)點(diǎn)的前驅(qū)即可。定義如下：
//刪除節(jié)點(diǎn)
function remove ( item ) {
var currNode = this.find ( item );
if( !( currNode.next == null ) ){
currNode.previous.next = currNode.next;
currNode.next.previous = currNode.previous;
currNode.next = null;
currNode.previous = null;
}
}還有一些反向顯示鏈表 dispReverse，查找鏈表最后一個(gè)元素 findLast 等方法，相信你已經(jīng)有了思路，這里我給出一個(gè)基本雙向鏈表的完成代碼，供大家參考。
//節(jié)點(diǎn)
function Node(element) {
this.element = element; //當(dāng)前節(jié)點(diǎn)的元素
this.next = null; //下一個(gè)節(jié)點(diǎn)鏈接
this.previous = null; //上一個(gè)節(jié)點(diǎn)鏈接
}
//鏈表類
function LList () {
this.head = new Node( 'head' );
this.find = find;
this.findLast = findLast;
this.insert = insert;
this.remove = remove;
this.display = display;
this.dispReverse = dispReverse;
}
//查找元素
function find ( item ) {
var currNode = this.head;
while ( currNode.element != item ){
currNode = currNode.next;
}
return currNode;
}
//查找鏈表中的最后一個(gè)元素
function findLast () {
var currNode = this.head;
while ( !( currNode.next == null )){
currNode = currNode.next;
}
return currNode;
}
//插入節(jié)點(diǎn)
function insert ( newElement , item ) {
var newNode = new Node( newElement );
var currNode = this.find( item );
newNode.next = currNode.next;
newNode.previous = currNode;
currNode.next = newNode;
}
//顯示鏈表元素
function display () {
var currNode = this.head;
while ( !(currNode.next == null) ){
console.debug( currNode.next.element );
currNode = currNode.next;
}
}
//反向顯示鏈表元素
function dispReverse () {
var currNode = this.findLast();
while ( !( currNode.previous == null )){
console.log( currNode.element );
currNode = currNode.previous;
}
}
//刪除節(jié)點(diǎn)
function remove ( item ) {
var currNode = this.find ( item );
if( !( currNode.next == null ) ){
currNode.previous.next = currNode.next;
currNode.next.previous = currNode.previous;
currNode.next = null;
currNode.previous = null;
}
}
var fruits = new LList();
fruits.insert('Apple' , 'head');
fruits.insert('Banana' , 'Apple');
fruits.insert('Pear' , 'Banana');
fruits.insert('Grape' , 'Pear');
console.log( fruits.display() ); // Apple
// Banana
// Pear
// Grape
console.log( fruits.dispReverse() ); // Grape
// Pear
// Banana
// Apple循環(huán)鏈表和單鏈表相似，節(jié)點(diǎn)類型都是一樣，唯一的區(qū)別是，在創(chuàng)建循環(huán)鏈表的時(shí)候，讓其頭節(jié)點(diǎn)的 next 屬性執(zhí)行它本身，即
head.next = head;
這種行為會(huì)導(dǎo)致鏈表中每個(gè)節(jié)點(diǎn)的 next 屬性都指向鏈表的頭節(jié)點(diǎn)，換句話說(shuō)，也就是鏈表的尾節(jié)點(diǎn)指向了頭節(jié)點(diǎn)，形成了一個(gè)循環(huán)鏈表，如下圖所示：
循環(huán)鏈表
原理相信你已經(jīng)懂了，循環(huán)鏈表這里就不貼代碼了，相信你自己能獨(dú)立完成！
以上是“JS中鏈表Linked-list有什么用”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)成都網(wǎng)站設(shè)計(jì)公司行業(yè)資訊頻道！
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。
