5.單向鏈表

　　鏈表以及數(shù)組的缺點(diǎn)

　　　　鏈表和數(shù)組一樣，可以用于存儲(chǔ)一系列的元素，但是鏈表和數(shù)組的實(shí)現(xiàn)機(jī)制完全不同。

　　　　這一章中，我們就來(lái)學(xué)習(xí)一下另外一種非常常見的用于存儲(chǔ)數(shù)據(jù)的線性結(jié)構(gòu)：鏈表。

　　數(shù)組：

　　　　要存儲(chǔ)多個(gè)元素，數(shù)組（或稱為列表）可能是最常用的數(shù)據(jù)結(jié)構(gòu)。

　　　　我們之前說(shuō)過，幾乎每一種編程語(yǔ)言都有默認(rèn)實(shí)現(xiàn)數(shù)組結(jié)構(gòu)。

　　　　但是數(shù)組也有很多缺點(diǎn)：

　　　　　　數(shù)組的創(chuàng)建同城需要申請(qǐng)一段連續(xù)的內(nèi)存空間（一整塊的內(nèi)容），并且大小是固定的（大多數(shù)編程語(yǔ)言數(shù)組都是固定的），所以當(dāng)當(dāng)前數(shù)組不能滿足容量需求時(shí)，需要擴(kuò)容。

　　　　　　（一般情況下是申請(qǐng)一個(gè)更大的數(shù)組，比如2倍。然后將原數(shù)組中的元素賦值過去）

　　　　　　而且在數(shù)組開頭或中間位置插入數(shù)據(jù)的成本很高，需要進(jìn)行大量元素的位移。

　　　　　　盡管我們已經(jīng)學(xué)過的JavaScript的Array類方法可以幫我們做這些事，但背后的原理依然是這樣。

　　鏈表的優(yōu)勢(shì)

　　　　要存儲(chǔ)多個(gè)元素，另外一個(gè)選擇就是鏈表。

　　　　但不用于數(shù)組，鏈表中的元素在內(nèi)存中不必事連續(xù)的空間。

　　　　鏈表的每個(gè)元素有一個(gè)存儲(chǔ)元素本身的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用（有些語(yǔ)言稱為指針或者連接）組成。

　　　　相對(duì)于數(shù)組，鏈表有一些優(yōu)點(diǎn)：

　　　　　　內(nèi)存空間不是必須連續(xù)的，可以充分利用計(jì)算機(jī)的內(nèi)存，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。

　　　　　　鏈表不必再創(chuàng)建時(shí)就確定大小，并且大小可以無(wú)限的延伸下去。

　　　　　　鏈表在插入和刪除數(shù)據(jù)時(shí)，時(shí)間復(fù)雜度可以達(dá)到O(1).相對(duì)數(shù)組效率高很多。

　　　　相對(duì)于數(shù)組，鏈表有一些缺點(diǎn)：

　　　　　　鏈表訪問任何一個(gè)位置的元素時(shí)，都需要從頭開始訪問。（無(wú)法跳過第一個(gè)元素訪問任何一個(gè)元素）。

　　　　　　無(wú)法通過下標(biāo)直接訪問元素，需要從頭一個(gè)個(gè)訪問，知道找到對(duì)應(yīng)的元素。

　　　　鏈表到底是什么？

　　　　　　什么是鏈表呢？

　　　　　　　　其實(shí)上面我們已經(jīng)簡(jiǎn)單的提過了鏈表的結(jié)構(gòu)，我們這里更加詳細(xì)的分析一下。

　　　　　　　　鏈表類似于火車：有一個(gè)火車頭，火車頭會(huì)鏈接一個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)上有乘客（類似于數(shù)據(jù)），并且這個(gè)節(jié)點(diǎn)會(huì)連接下一個(gè)節(jié)點(diǎn)，以此類推。

　　　　鏈表的火車結(jié)構(gòu)：

　　鏈表結(jié)構(gòu)的封裝

　　　　我們先來(lái)創(chuàng)建一個(gè)鏈表類

　　　　鏈表結(jié)構(gòu)封裝代碼

    <script>
        // 封裝鏈表類
        function LinkedList() {
            // 內(nèi)部的類：節(jié)點(diǎn)類
            function Node(data) {
                this.data = data;
                this.data = null;
            }
            // 屬性
            this.head = null;
            this.length = 0;

        }
    </script>

　鏈表常見操作：

　　　　我們先來(lái)認(rèn)識(shí)一下，鏈表中應(yīng)該有哪些常見的操作

　　　　　　append(element)：向列表尾部添加一個(gè)新的項(xiàng)

　　　　　　insert(position,element)：向列表的特定位置插入一個(gè)新的項(xiàng)。

　　　　　　get(position)：獲取對(duì)應(yīng)位置的元素

　　　　　　indexOf(element)：返回元素在列表中的索引。如果列表中沒有該元素則返回-1.

　　　　　　update(position)：修改某個(gè)位置的元素

　　　　　　removeAt(position)：從列表的特定位置移除一項(xiàng)。

　　　　　　remove(element)：從列表中移除一項(xiàng)。

　　　　　　isEmpty()：如果鏈表中不包含任何元素，返回true，如果鏈表長(zhǎng)度大于0則返回false。

　　　　　　size()：返回鏈表包含的元素個(gè)數(shù)。與數(shù)組的length屬性類似。

　　　　　　toString()：由于列表項(xiàng)使用了Node類，就需要重寫繼承自JavaScript對(duì)象默認(rèn)的toString方法，讓其只輸出元素的值。

　　　　整體你會(huì)發(fā)現(xiàn)操作方法和數(shù)組非常類似，因?yàn)殒湵肀旧砭褪且环N可以代替數(shù)組的結(jié)構(gòu)。

　　append方法

　　　　向鏈表尾部追加數(shù)組可能有兩種情況：

　　　　　　鏈表本身為空，新添加的數(shù)組時(shí)唯一的節(jié)點(diǎn)。

　　　　　　鏈表不為空，需要向其他節(jié)點(diǎn)后面追加節(jié)點(diǎn)。

　　append方法代碼

    <script>
        // 封裝鏈表類
        function LinkedList() {
            // 內(nèi)部的類：節(jié)點(diǎn)類
            function Node(data) {
                this.data = data;
                this.data = null;
            }
            // 屬性
            this.head = null;
            this.length = 0;
            // 追加方法
            LinkedList.prototype.append = function(data) {
                // 1.創(chuàng)建新的節(jié)點(diǎn)
                var newNode = new Node(data);
                // 判斷是否添加的是第一個(gè)節(jié)點(diǎn)
                if (this.length == 0) { // 是第一個(gè)節(jié)點(diǎn)
                    this.head = newNode;
                } else { // 不是第一個(gè)節(jié)點(diǎn)
                    // 找到最后一個(gè)節(jié)點(diǎn)
                    var current = this.head;
                    while (current.next) {
                        current = current.next;
                    }
                    // 最后節(jié)點(diǎn)的next指向新的節(jié)點(diǎn)
                    current.next = newNode;
                }
                // length+1
                this.length += 1;
            }
        }
    </script>

　　toString方法

　　　　我們先來(lái)實(shí)現(xiàn)一下鏈表的toString方法，這樣會(huì)方便測(cè)試上面的臺(tái)南佳代碼

　　　　　　該方法比較簡(jiǎn)單，主要是獲取每一個(gè)元素。

　　　　　　還是從head開頭，因?yàn)楂@取鏈表的任何元素都必須從第一個(gè)節(jié)點(diǎn)開頭。

　　　　　　循環(huán)遍歷每一個(gè)節(jié)點(diǎn)，并且取出其中的element，拼接成字符串。

　　　　　　將最終字符串返回

　　insert方法

　　　　接下來(lái)實(shí)現(xiàn)另外一個(gè)添加數(shù)據(jù)的方法：在任意位置插入數(shù)據(jù)。

　　　　添加到第一個(gè)位置：

　　　　　　添加到第一個(gè)位置，表示新添加的節(jié)點(diǎn)是頭，就需要將原來(lái)的頭節(jié)點(diǎn)，作為新節(jié)點(diǎn)的next

　　　　　　另外這個(gè)時(shí)候的head應(yīng)該指向新節(jié)點(diǎn)。

　　　　添加到其他位置：

　　　　　　如果是添加到其他的位置，就需要先找到這個(gè)節(jié)點(diǎn)的位置。

　　　　　　我們通過while循環(huán)，一點(diǎn)點(diǎn)向下找。并且在這個(gè)過程中保存上一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)

　　　　　　找到正確的位置后，將新節(jié)點(diǎn)的next指向下一個(gè)節(jié)點(diǎn)，將上一個(gè)節(jié)點(diǎn)的next指向新的節(jié)點(diǎn)。

　　　　insert方法代碼：

                // inset方法
            LinkedList.prototype.insert = function(position, data) {
                // 對(duì)position進(jìn)行月結(jié)判斷
                if (position < 0 || position > this.length) return false
                    // 根據(jù)data創(chuàng)建newNode
                var newNode = new Node(data)
                    // 判斷插入的位置是否是第一個(gè)
                if (position == 0) {
                    newNode.next = this.head
                    this.head = newNode
                } else {
                    var index = 0
                    var previous = null
                    while (index++ < position) {
                        previous = current
                        current = current.next
                    }
                    newNode.next = current
                    previous.next = newNode
                }
                // length + 1
                this.length += 1
                return true
            }

　　get(position)：獲取對(duì)應(yīng)位置的元素

      // get方法
            LinkedList.prototype.get = function(position) {
                // 越界判斷
                if (position < 0 || position >= this.length) return null
                    // 獲取對(duì)應(yīng)的data
                var current = this.head
                var index = 0
                while (index++ < position) {
                    current = current.next
                }
                return current.data
            }

　　indexOf(element)：返回元素在列表中的索引。如果列表中沒有該元素則返回-1

 // indexOf方法
            LinkedList.prototype.indexOf = function(data) {
                // 定義變量
                var current = this.head
                var index = 0
                    // 開始查找
                while (current) {
                    if (current.data == data) {
                        return index
                    }
                    current = current.next
                    index += 1
                }
                // 找到最后沒有找到，返回-1
                return -1
            }

　　update(position)：修改某個(gè)位置的元素

 // updata方法
            LinkedList.prototype.update = function(position, newData) {
                // 判斷越界
                if (position < 0 || position >= this.length) return false
                    // 查找正確的節(jié)點(diǎn)
                var current = this.head
                var index = 0
                while (index++ < position) {
                    current = current.next
                }
                // 將position位置的node的data修改程newData
                current.data = newData
                return true
            }

　　removeAt(position)：從列表的特定位置移除一項(xiàng)。

                // removeAt方法
            LinkedList.prototype.removeAt = function(position) {
                // 判斷越界
                if (position < 0 || position >= this.length) return null
                    // 判斷是否刪除的是第一個(gè)節(jié)點(diǎn)
                var current = this.head
                if (position == 0) {
                    this.head = this.head.next
                } else {
                    var index = 0
                    var previous = null
                    while (index++ < position) {
                        previous = current
                        current = current.next
                    }
                    // 前一個(gè)節(jié)點(diǎn)的next指向，current的next即可
                    previous.next = current.next
                }
                // length -1
                this.length -= 1
                return current.data
            }

　　remobe(element)：從列表中移除一項(xiàng)。

  // remove方法
            LinkedList.prototype.remove = function(data) {
                // 獲取data在列表中的位置
                var position = this.indexOf(data)
                    // 根據(jù)位置信息，刪除節(jié)點(diǎn)
                return this.removeAt(position)
            }

　　isEmpty()：如果鏈表中不包含任何元素，返回true，如果鏈表長(zhǎng)度大于0則返回false

    // isEmpty方法
            LinkedList.prototype.isEmpty = function() {
                    return this.length == 0
                }

　　size()：返回鏈表包含的元素個(gè)數(shù)。與數(shù)組的length屬性類似

// size方法
            LinkedList.prototype.size = function() {
                return this.length
            }

posted @ 2022-04-04 11:27 風(fēng)太溫柔閱讀(58) 評(píng)論(0) 收藏舉報(bào)

刷新頁(yè)面返回頂部

g116

5.單向鏈表

公告