學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)(二)——鏈表

Karrdy 發(fā)布于2019-08-20 12:16 / 3003人閱讀

摘要：就那么回事后記說(shuō)到現(xiàn)在一直都是線(xiàn)性表，就是順序數(shù)據(jù)結(jié)構(gòu)，他們都是有順序的，數(shù)據(jù)都是一條繩子上的螞蚱。那么，如果數(shù)據(jù)是沒(méi)有順序的呢那又該使用哪種數(shù)據(jù)結(jié)構(gòu)呢這個(gè)放到學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)三集合中學(xué)習(xí)。

前言

人生總是直向前行走，從不留下什么。

原文地址：學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)(二)——鏈表

博主博客地址：Damonare的個(gè)人博客

正文 鏈表簡(jiǎn)介

????上一篇博客-學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)(一)——棧和隊(duì)列說(shuō)了棧和隊(duì)列在javascript中的實(shí)現(xiàn),我們運(yùn)用javascript提供的API很容易的實(shí)現(xiàn)了棧和隊(duì)列，但這種數(shù)據(jù)結(jié)構(gòu)有一個(gè)很明顯的缺點(diǎn)，因?yàn)閿?shù)組大小是固定的所以我們?cè)谝瞥蚴翘砑右豁?xiàng)數(shù)據(jù)的時(shí)候成本很高，基本都需要吧數(shù)據(jù)重排一次。(javascript的Array類(lèi)方法雖然很方便但背后的原理同樣是這樣的)

????相比數(shù)組我們今天主角——鏈表就要來(lái)的隨性的多，簡(jiǎn)單的理解可以是這樣：在內(nèi)存中，棧和隊(duì)列（數(shù)組）的存在就是一個(gè)整體，如果想要對(duì)她內(nèi)部某一個(gè)元素進(jìn)行移除或是添加一個(gè)新元素就要?jiǎng)铀齼?nèi)部所有的元素，所謂牽一發(fā)而動(dòng)全身；而鏈表則不一樣，每一個(gè)元素都是由元素本身數(shù)據(jù)和指向下一個(gè)元素的指針構(gòu)成，所以添加或是移除某一個(gè)元素不需要對(duì)鏈表整體進(jìn)行操作，只需要改變相關(guān)元素的指針指向就可以了。

????鏈表在實(shí)際生活中的例子也有很多，比如自行車(chē)的鏈條，環(huán)環(huán)相扣，但添加或是移除某一個(gè)環(huán)節(jié)只需要對(duì)癥下藥，對(duì)相關(guān)環(huán)節(jié)進(jìn)行操作就OK。再比如：火車(chē)，火車(chē)就是一個(gè)鏈表，每一節(jié)車(chē)廂就是元素，想要移除或是添加某一節(jié)車(chē)廂，只需要把連接車(chē)廂的鏈條改變一下就好了。那么，在javascript中又該怎么去實(shí)現(xiàn)鏈表結(jié)構(gòu)呢？

鏈表的創(chuàng)建

首先我們要?jiǎng)?chuàng)建一個(gè)鏈表類(lèi)：

function LinkedList(){
    //各種屬性和方法的聲明
}

然后我們需要一種數(shù)據(jù)結(jié)構(gòu)來(lái)保存鏈表里面的數(shù)據(jù)：

var Node=function(element){
    this.element=element;
    this.next=null;
}
//Node類(lèi)表示要添加的元素，他有兩個(gè)屬性，一個(gè)是element，表示添加到鏈表中的具體的值；另一個(gè)是next,表示要指向鏈表中下一個(gè)元素的指針。

接下來(lái)，我們需要給鏈表聲明一些方法：

append(element):向鏈表尾部添加一個(gè)新的元素；

insert(position,element):向鏈表特定位置插入元素；

remove(element):從鏈表移除一項(xiàng)；

indexOf(element):返回鏈表中某元素的索引，如果沒(méi)有返回-1；

removeAt(position):從特定位置移除一項(xiàng)；

isEmpty():判斷鏈表是否為空，如果為空返回true,否則返回false;

size():返回鏈表包含的元素個(gè)數(shù)；

toString():重寫(xiě)繼承自O(shè)bject類(lèi)的toString()方法，因?yàn)槲覀兪褂昧薔ode類(lèi)；

鏈表的完整代碼：

function LinkedList() {
    //Node類(lèi)聲明
    let Node = function(element){
        this.element = element;
        this.next = null;
    };
    //初始化鏈表長(zhǎng)度
    let length = 0;
    //初始化第一個(gè)元素
    let head = null;
    this.append = function(element){
        //初始化添加的Node實(shí)例
        let node = new Node(element),
            current;
        if (head === null){
            //第一個(gè)Node實(shí)例進(jìn)入鏈表，之后在這個(gè)LinkedList實(shí)例中head就不再是null了
            head = node;
        } else {
            current = head;
            //循環(huán)鏈表知道找到最后一項(xiàng)，循環(huán)結(jié)束current指向鏈表最后一項(xiàng)元素
            while(current.next){
                current = current.next;
            }
            //找到最后一項(xiàng)元素后，將他的next屬性指向新元素node,j建立鏈接
            current.next = node;
        }
        //更新鏈表長(zhǎng)度
        length++;
    };
    this.insert = function(position, element){
        //檢查是否越界，超過(guò)鏈表長(zhǎng)度或是小于0肯定不符合邏輯的
        if (position >= 0 && position <= length){
            let node = new Node(element),
                current = head,
                previous,
                index = 0;
            if (position === 0){
                //在第一個(gè)位置添加
                node.next = current;
                head = node;
            } else {
                //循環(huán)鏈表，找到正確位置，循環(huán)完畢，previous，current分別是被添加元素的前一個(gè)和后一個(gè)元素
                while (index++ < position){
                    previous = current;
                    current = current.next;
                }
                node.next = current;
                previous.next = node;
            }
            //更新鏈表長(zhǎng)度
            length++;
            return true;
        } else {
            return false;
        }
    };
    this.removeAt = function(position){
        //檢查是否越界，超過(guò)鏈表長(zhǎng)度或是小于0肯定不符合邏輯的
        if (position > -1 && position < length){
            let current = head,
                previous,
                index = 0;
            //移除第一個(gè)元素
            if (position === 0){
                //移除第一項(xiàng)，相當(dāng)于head=null;
                head = current.next;
            } else {
                //循環(huán)鏈表，找到正確位置，循環(huán)完畢，previous，current分別是被添加元素的前一個(gè)和后一個(gè)元素
                while (index++ < position){
                    previous = current;
                    current = current.next;
                }
                //鏈接previous和current的下一個(gè)元素，也就是把current移除了
                previous.next = current.next;
            }
            length--;
            return current.element;
        } else {
            return null;
        }
    };
    this.indexOf = function(element){
        let current = head,
            index = 0;
        //循環(huán)鏈表找到元素位置
        while (current) {
            if (element === current.element) {
                return index;
            }
            index++;
            current = current.next;
        }
        return -1;
    };
    this.remove = function(element){
        //調(diào)用已經(jīng)聲明過(guò)的indexOf和removeAt方法
        let index = this.indexOf(element);
        return this.removeAt(index);
    };
    this.isEmpty = function() {
        return length === 0;
    };
    this.size = function() {
        return length;
    };
    this.getHead = function(){
        return head;
    };
    this.toString = function(){
        let current = head,
            string = "";
        while (current) {
            string += current.element + (current.next ? ", " : "");
            current = current.next;
        }
        return string;
    };
    this.print = function(){
        console.log(this.toString());
    };
}
//一個(gè)實(shí)例化后的鏈表，里面是添加的數(shù)個(gè)Node類(lèi)的實(shí)例

ES6版本:

let LinkedList2 = (function () {
    class Node {
        constructor(element){
            this.element = element;
            this.next = null;
        }
    }
    //這里我們使用WeakMap對(duì)象來(lái)記錄長(zhǎng)度狀態(tài)
    const length = new WeakMap();
    const head = new WeakMap();
    class LinkedList2 {
        constructor () {
            length.set(this, 0);
            head.set(this, null);
        }
        append(element) {
            let node = new Node(element),
                current;
            if (this.getHead() === null) {
                head.set(this, node);
            } else {
                current = this.getHead();
                while (current.next) {
                    current = current.next;
                }
                current.next = node;
            }
            let l = this.size();
            l++;
            length.set(this, l);
        }
        insert(position, element) {
            if (position >= 0 && position <= this.size()) {

                let node = new Node(element),
                    current = this.getHead(),
                    previous,
                    index = 0;
                if (position === 0) {
                    node.next = current;
                    head.set(this, node);
                } else {
                    while (index++ < position) {
                        previous = current;
                        current = current.next;
                    }
                    node.next = current;
                    previous.next = node;
                }
                let l = this.size();
                l++;
                length.set(this, l);
                return true;
            } else {
                return false;
            }
        }
        removeAt(position) {
            if (position > -1 && position < this.size()) {
                let current = this.getHead(),
                    previous,
                    index = 0;
                if (position === 0) {
                    head.set(this, current.next);
                } else {
                    while (index++ < position) {
                        previous = current;
                        current = current.next;
                    }
                    previous.next = current.next;
                }
                let l = this.size();
                l--;
                length.set(this, l);
                return current.element;
            } else {
                return null;
            }
        }
        remove(element) {
            let index = this.indexOf(element);
            return this.removeAt(index);
        }
        indexOf(element) {
            let current = this.getHead(),
                index = 0;
            while (current) {
                if (element === current.element) {
                    return index;
                }
                index++;
                current = current.next;
            }
            return -1;
        }
        isEmpty() {
            return this.size() === 0;
        }
        size() {
            return length.get(this);
        }
        getHead() {
            return head.get(this);
        }
        toString() {
            let current = this.getHead(),
                string = "";
            while (current) {
                string += current.element + (current.next ? ", " : "");
                current = current.next;
            }
            return string;

        }
        print() {
            console.log(this.toString());
        }
    }
    return LinkedList2;
})();

雙向鏈表

function DoublyLinkedList() {
    let Node = function(element){
        this.element = element;
        this.next = null;
        this.prev = null; //NEW
    };
    let length = 0;
    let head = null;
    let tail = null; //NEW
    this.append = function(element){
        let node = new Node(element),
            current;
        if (head === null){
            head = node;
            tail = node; //NEW
        } else {
            //NEW
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
        length++;
    };
    this.insert = function(position, element){
        if (position >= 0 && position <= length){
            let node = new Node(element),
                current = head,
                previous,
                index = 0;
            if (position === 0){
                if (!head){       //NEW
                    head = node;
                    tail = node;
                } else {
                    node.next = current;
                    current.prev = node; //NEW
                    head = node;
                }
            } else  if (position === length) { ////NEW
                current = tail;   
                current.next = node;
                node.prev = current;
                tail = node;
            } else {
                while (index++ < position){
                    previous = current;
                    current = current.next;
                }
                node.next = current;
                previous.next = node;
                current.prev = node; //NEW
                node.prev = previous; //NEW
            }
            length++;
            return true;
        } else {
            return false;
        }
    };
    this.removeAt = function(position){
        if (position > -1 && position < length){
            let current = head,
                previous,
                index = 0;
            if (position === 0){ //NEW
                if (length === 1){ //
                    tail = null;
                } else {
                    head.prev = null;
                }
            } else if (position === length-1){  //NEW
                current = tail;
                tail = current.prev;
                tail.next = null;
            } else {
                while (index++ < position){
                    previous = current;
                    current = current.next;
                }
                previous.next = current.next;
                current.next.prev = previous; //NEW
            }
            length--;
            return current.element;
        } else {
            return null;
        }
    };
    this.remove = function(element){
        let index = this.indexOf(element);
        return this.removeAt(index);
    };
    this.indexOf = function(element){
        let current = head,
            index = -1;
        if (element == current.element){
            return 0;
        }
        index++;
        while(current.next){
            if (element == current.element){
                return index;
            }
            current = current.next;
            index++;
        }
        //check last item
        if (element == current.element){
            return index;
        }
        return -1;
    };
    this.isEmpty = function() {
        return length === 0;
    };
    this. size = function() {
        return length;
    };
    this.toString = function(){
        let current = head,
            s = current ? current.element : "";
        while(current && current.next){
            current = current.next;
            s += ", " + current.element;
        }
        return s;
    };
    this.inverseToString = function() {
        let current = tail,
            s = current ? current.element : "";
        while(current && current.prev){
            current = current.prev;
            s += ", " + current.element;
        }
        return s;
    };
    this.print = function(){
        console.log(this.toString());
    };
    this.printInverse = function(){
        console.log(this.inverseToString());
    };
    this.getHead = function(){
        return head;
    };
    this.getTail = function(){
        return tail;
    }
}

????雙向鏈表和單項(xiàng)比起來(lái)就是Node類(lèi)多了一個(gè)prev屬性，也就是每一個(gè)node不僅僅有一個(gè)指向它后面元素的指針也有一個(gè)指向它前面的指針。

循環(huán)鏈表

????明白了前面的基礎(chǔ)鏈表和雙向鏈表之后這個(gè)肯定不在話(huà)下了，循環(huán)，其實(shí)就是整個(gè)鏈表實(shí)例變成了一個(gè)圈，在單項(xiàng)鏈表中最后一個(gè)元素的next屬性為null,現(xiàn)在讓它指向第一個(gè)元素也就是head，那么他就成了單向循環(huán)鏈表。在雙向鏈表中最后一個(gè)元素的next屬性為null,現(xiàn)在讓它指向第一個(gè)元素也就是head，那么他就成了雙向循環(huán)鏈表。就那么回事...

后記

說(shuō)到現(xiàn)在一直都是線(xiàn)性表，就是順序數(shù)據(jù)結(jié)構(gòu)，他們都是有順序的，數(shù)據(jù)都是一條繩子上的螞蚱。那么，如果數(shù)據(jù)是沒(méi)有順序的呢？那又該使用哪種數(shù)據(jù)結(jié)構(gòu)呢？這個(gè)放到[學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)(三)——集合]中學(xué)習(xí)。

GPU云服務(wù)器云服務(wù)器深度學(xué)習(xí)二鏈表數(shù)據(jù)結(jié)構(gòu)隊(duì)列 linux 數(shù)據(jù)結(jié)構(gòu) 鏈表 java鏈表數(shù)據(jù)結(jié)構(gòu)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/80886.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

Karrdy

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

服務(wù)器主機(jī)怎么用-如何使用服務(wù)器主機(jī)？

閱讀 2906·2021-09-22 15:54
Vue & Bootstrap 結(jié)合學(xué)習(xí)筆記（二）

閱讀 1899·2019-08-30 15:53
Slog27_支配vue框架初階項(xiàng)目之博客網(wǎng)站-樣式居中

閱讀 2252·2019-08-29 16:33
Angular2入門(mén)系列（一）————如何在A(yíng)ngular2中使用jQuery和基于jQuery的插

閱讀 1429·2019-08-29 12:29
C4:繼承

閱讀 1401·2019-08-26 11:41
javascript知識(shí)點(diǎn)

閱讀 2380·2019-08-26 11:34
React中禁止頁(yè)面滾動(dòng)

閱讀 2966·2019-08-23 16:12
requestAnimationFrame 實(shí)現(xiàn)1s

閱讀 1431·2019-08-23 15:56

成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)(二)——鏈表

相關(guān)文章

*學(xué)習(xí)JavaScript**數(shù)據(jù)結(jié)構(gòu)*與算法（二）：鏈表

CSS技巧

CSS技巧

數(shù)據(jù)結(jié)構(gòu)JavaScript描述（二）

*學(xué)習(xí)javascript**數(shù)據(jù)結(jié)構(gòu)*(四)——樹(shù)

發(fā)表評(píng)論

0條評(píng)論

Karrdy

男|高級(jí)講師

TA的文章

服務(wù)器主機(jī)怎么用-如何使用服務(wù)器主機(jī)？

Vue & Bootstrap 結(jié)合學(xué)習(xí)筆記（二）

Slog27_支配vue框架初階項(xiàng)目之博客網(wǎng)站-樣式居中

Angular2入門(mén)系列（一）————如何在A(yíng)ngular2中使用jQuery和基于jQuery的插

C4:繼承

javascript知識(shí)點(diǎn)

React中禁止頁(yè)面滾動(dòng)

requestAnimationFrame 實(shí)現(xiàn)1s

最新活動(dòng)

資訊專(zhuān)欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

學(xué)習(xí)javascript數(shù)據(jù)結(jié)構(gòu)(二)——鏈表

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！