手机AV在线,舔女人逼视频,九热精品2

如需轉(zhuǎn)載, 請咨詢作者, 并且注明出處.
有任何問題, 可以關(guān)注我的微博: coderwhy, 或者添加我的微信: 372623326

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

這一章中, 我們就來學(xué)習(xí)一下另外一種非常常見的用于存儲數(shù)據(jù)的線性結(jié)構(gòu): 鏈表.

一. 認(rèn)識鏈表

我們先來認(rèn)識一下鏈表, 看一下它大概的機(jī)制和原理, 以及和數(shù)組的對比.

鏈表和數(shù)組

數(shù)組:
- 要存儲多個元素，數(shù)組（或列表）可能是最常用的數(shù)據(jù)結(jié)構(gòu)。
- 我們之前說過, 幾乎每一種編程語言都有默認(rèn)實(shí)現(xiàn)數(shù)組結(jié)構(gòu), 這種數(shù)據(jù)結(jié)構(gòu)非常方便，提供了一個便利的[]語法來訪問它的元素。
- 但是數(shù)組也有很多缺點(diǎn):
  - 數(shù)組的創(chuàng)建通常需要申請一段連續(xù)的內(nèi)存空間(一整塊的內(nèi)存), 并且大小是固定的(大多數(shù)編程語言數(shù)組都是固定的), 所以當(dāng)當(dāng)前數(shù)組不能滿足容量需求時, 需要擴(kuò)容. (一般情況下是申請一個更大的數(shù)組, 比如2倍. 然后將原數(shù)組中的元素復(fù)制過去)
  - 而且在數(shù)組開頭或中間位置插入數(shù)據(jù)的成本很高, 需要進(jìn)行大量元素的位移.（盡管我們已經(jīng)學(xué)過的JavaScript的Array類方法可以幫我們做這些事，但背后的原理依然是這樣）。
鏈表
- 要存儲多個元素, 另外一個選擇就是使用鏈表.
- 但不同于數(shù)組, 鏈表中的元素在內(nèi)存中不必是連續(xù)的空間.
- 鏈表的每個元素由一個存儲元素本身的節(jié)點(diǎn)和一個指向下一個元素的引用(有些語言稱為指針或者鏈接)組成.
- 相對于數(shù)組, 鏈表有一些優(yōu)點(diǎn):
  - 內(nèi)存空間不是比是連續(xù)的. 可以充分利用計算機(jī)的內(nèi)存. 實(shí)現(xiàn)靈活的內(nèi)存動態(tài)管理.
  - 鏈表不必在創(chuàng)建時就確定大小, 并且大小可以無限的延伸下去.
  - 鏈表在插入和刪除數(shù)據(jù)時, 時間復(fù)雜度可以達(dá)到O(1). 相對數(shù)組效率高很多.
- 相對于數(shù)組, 鏈表有一些缺點(diǎn):
  - 鏈表訪問任何一個位置的元素時, 都需要從頭開始訪問.(無法跳過第一個元素訪問任何一個元素).
  - 無法通過下標(biāo)直接訪問元素, 需要從頭一個個訪問, 直到找到對應(yīng)的問題.

什么是鏈表?

什么是鏈表呢?
- 其實(shí)上面我們已經(jīng)簡單的提過了鏈表的結(jié)構(gòu), 我們這里更加詳細(xì)的分析一下.
- 鏈表類似于火車: 有一個火車頭, 火車頭會連接一個節(jié)點(diǎn), 節(jié)點(diǎn)上有乘客, 并且這個節(jié)點(diǎn)會連接下一個節(jié)點(diǎn), 以此類推.
- 鏈表的火車結(jié)構(gòu):
  
  img
- 鏈表的數(shù)據(jù)結(jié)構(gòu)
  
  img
- 給火車加上數(shù)據(jù)后的結(jié)構(gòu)
  
  img

二. 鏈表封裝

前面我們已經(jīng)認(rèn)識了鏈表結(jié)構(gòu), 現(xiàn)在通過代碼來封裝自己的鏈表吧.

創(chuàng)建鏈表類

我們先來創(chuàng)建一個鏈表類

// 封裝鏈表的構(gòu)造函數(shù)
function LinkedList() {
    // 封裝一個Node類, 用于保存每個節(jié)點(diǎn)信息
    function Node(element) {
        this.element = element
        this.next = null
    }

    // 鏈表中的屬性
    this.length = 0  // 鏈表的長度
    this.head = null // 鏈表的第一個節(jié)點(diǎn)
    
    // 鏈表中的方法
}

代碼解析:
- 封裝LinkedList的類, 用于表示我們的鏈表結(jié)構(gòu). (和Java中的鏈表同名, 不同Java中的這個類是一個雙向鏈表, 后面我們會講解雙向鏈表)
- 在LinkedList類中有一個Node類, 用于封裝每一個節(jié)點(diǎn)上的信息.(和優(yōu)先級隊(duì)列的封裝一樣)
- 鏈表中我們保存兩個屬性, 一個是鏈表的長度, 一個是鏈表中第一個節(jié)點(diǎn).
- 當(dāng)然, 還有很多鏈表的操作方法. 我們放在下一節(jié)中學(xué)習(xí).

鏈表常見操作

我們先來認(rèn)識一下, 鏈表中應(yīng)該有哪些常見的操作
- append(element)：向列表尾部添加一個新的項(xiàng)
- insert(position, element)：向列表的特定位置插入一個新的項(xiàng)。
- remove(element)：從列表中移除一項(xiàng)。
- indexOf(element)：返回元素在列表中的索引。如果列表中沒有該元素則返回-1。
- removeAt(position)：從列表的特定位置移除一項(xiàng)。
- isEmpty()：如果鏈表中不包含任何元素，返回true，如果鏈表長度大于0則返回false。
- size()：返回鏈表包含的元素個數(shù)。與數(shù)組的length屬性類似。
- toString()：由于列表項(xiàng)使用了Node類，就需要重寫繼承自JavaScript對象默認(rèn)的toString方法，讓其只輸出元素的值。
方法解讀:
- 整體你會發(fā)現(xiàn)操作方法和數(shù)組非常類似, 因?yàn)殒湵肀旧砭褪且环N可以代替數(shù)組的結(jié)構(gòu).
- 但是某些方法實(shí)現(xiàn)起來有些麻煩, 所以我們一個個來慢慢實(shí)現(xiàn)它們.

三. 鏈表操作

尾部追加數(shù)據(jù)

向鏈表尾部追加數(shù)據(jù)可能有兩種情況:
- 鏈表本身為空, 新添加的數(shù)據(jù)時唯一的節(jié)點(diǎn).
- 鏈表不為空, 需要向其他節(jié)點(diǎn)后面追加節(jié)點(diǎn).

append方法實(shí)現(xiàn)

// 鏈表尾部追加元素方法
LinkedList.prototype.append = function (element) {
    // 1.根據(jù)新元素創(chuàng)建節(jié)點(diǎn)
    var newNode = new Node(element)

    // 2.判斷原來鏈表是否為空
    if (this.head === null) { // 鏈表尾空
        this.head = newNode
    } else { // 鏈表不為空
        // 2.1.定義變量, 保存當(dāng)前找到的節(jié)點(diǎn)
        var current = this.head
        while (current.next) {
            current = current.next
        }

        // 2.2.找到最后一項(xiàng), 將其next賦值為node
        current.next = newNode
    }

    // 3.鏈表長度增加1
    this.length++
}

代碼解讀:
- 首先需要做的是將element傳入方法, 并根據(jù)element創(chuàng)建一個Node節(jié)點(diǎn).
- 場景一: 鏈表本身是空的, 比如這種情況下我們插入了一個15作為元素.
  
  img
- 場景二: 鏈表中已經(jīng)有元素了, 需要向最后的節(jié)點(diǎn)的next中添加節(jié)點(diǎn).
  - 這個時候要向鏈表的尾部添加一個元素, 首先我們需要找到這個尾部元素.
  - 記住: 我們只有第一個元素的引用, 因此需要循環(huán)訪問鏈表, 直接找到最后一個項(xiàng).(見代碼2.1)
  - 找到最后一項(xiàng)后, 最后一項(xiàng)的next為null, 這個時候不讓其為null, 而是指向新創(chuàng)建的節(jié)點(diǎn)即可.
  img
- 最后, 一定不要忘記將鏈表的length+1.

toString方法

我們先來實(shí)現(xiàn)一下鏈表的toString方法, 這樣會方便測試上面的添加代碼

// 鏈表的toString方法
LinkedList.prototype.toString = function () {
    // 1.定義兩個變量
    var current = this.head
    var listString = ""

    // 2.循環(huán)獲取鏈表中所有的元素
    while (current) {
        listString += "," + current.element
        current = current.next
    }

    // 3.返回最終結(jié)果
    return listString.slice(1)
}

方法解讀:
- 該方法比較簡單, 主要是獲取每一個元素
- 還是從head開頭, 因?yàn)楂@取鏈表的任何元素都必須從第一個節(jié)點(diǎn)開頭.
- 循環(huán)遍歷每一個節(jié)點(diǎn), 并且取出其中的element, 拼接成字符串.
- 將最終字符串返回.

測試append方法

// 測試鏈表
// 1.創(chuàng)建鏈表
var list = new LinkedList()

// 2.追加元素
list.append(15)
list.append(10)
list.append(20)

// 3.打印鏈表的結(jié)果
alert(list)

任意位置插入

接下來實(shí)現(xiàn)另外一個添加數(shù)據(jù)的方法: 在任意位置插入數(shù)據(jù).

// 根據(jù)下標(biāo)刪除元素
LinkedList.prototype.insert = function (position, element) {
    // 1.檢測越界問題: 越界插入失敗
    if (position < 0 || position > this.length) return false

    // 2.找到正確的位置, 并且插入數(shù)據(jù)
    var newNode = new Node(element)
    var current = this.head
    var previous = null
    index = 0

    // 3.判斷是否列表是否在第一個位置插入
    if (position == 0) {
        newNode.next = current
        this.head = newNode
    } else {
        while (index++ < position) {
            previous = current
            current = current.next
        }
        
        newNode.next = current
        previous.next = newNode
    }
    
    // 4.length+1
    this.length++
    
    return true
}

代碼解讀:
- 代碼1的位置, 我們處理了越界問題, 基本傳入位置信息時, 都需要進(jìn)行越界的判斷. 如果越界, 返回false, 表示數(shù)據(jù)添加失敗. (因?yàn)槲恢眯畔⑹清e誤的, 所以數(shù)據(jù)肯定是添加失敗的)
- 代碼2的位置, 我們定義了一些變量, 后續(xù)需要使用它們來保存信息.
- 代碼3的位置進(jìn)行了判斷, 這是因?yàn)樘砑拥降谝粋€位置和其他位置是不同的.
- 添加到第一個位置:
  - 添加到第一個位置, 表示新添加的節(jié)點(diǎn)是頭, 就需要將原來的頭節(jié)點(diǎn), 作為新節(jié)點(diǎn)的next
  - 另外這個時候的head應(yīng)該指向新節(jié)點(diǎn).
  img
- 添加到其他位置:
  - 如果是添加到其他位置, 就需要先找到這個節(jié)點(diǎn)位置了.
  - 我們通過while循環(huán), 一點(diǎn)點(diǎn)向下找. 并且在這個過程中保存上一個節(jié)點(diǎn)和下一個節(jié)點(diǎn).
  - 找到正確的位置后, 將新節(jié)點(diǎn)的next指向下一個節(jié)點(diǎn), 將上一個節(jié)點(diǎn)的next指向新的節(jié)點(diǎn).
  img
  
  img
- 最后, 不要忘記length+1
- 返回true, 表示元素插入成功了.

測試insert的方式插入數(shù)據(jù):

// 4.測試insert方法
list.insert(0, 100)
list.insert(4, 200)
list.insert(2, 300)
alert(list) // 100,15,300,10,20,200

位置移除數(shù)據(jù)

移除數(shù)據(jù)有兩種常見的方式:
- 根據(jù)位置移除對應(yīng)的數(shù)據(jù)
- 根據(jù)數(shù)據(jù), 先找到對應(yīng)的位置, 再移除數(shù)據(jù)

我們這里先完成根據(jù)位置移除數(shù)據(jù)的方式

// 根據(jù)位置移除節(jié)點(diǎn)
LinkedList.prototype.removeAt = function (position) {
    // 1.檢測越界問題: 越界移除失敗, 返回null
    if (position < 0 || position >= this.length) return null

    // 2.定義變量, 保存信息
    var current = this.head
    var previous = null
    var index = 0
    
    // 3.判斷是否是移除第一項(xiàng)
    if (position === 0) {
        this.head = current.next
    } else {
        while (index++ < position) {
            previous = current
            current = current.next
        }
        
        previous.next = current.next
    }
    
    // 4.length-1
    this.length--
    
    // 5.返回移除的數(shù)據(jù)
    return current.element
}

代碼解析:
- 代碼1部分, 還是越界的判斷. (注意: 這里越界判斷中的等于length也是越界的, 因?yàn)橄聵?biāo)值是從0開始的)
- 代碼2部分還是定義了一些變量, 用于保存臨時信息
- 代碼3部分進(jìn)行判斷, 因?yàn)橐瞥谝豁?xiàng)和其他項(xiàng)的方式是不同的
- 移除第一項(xiàng)的信息:
  - 移除第一項(xiàng)時, 直接讓head指向第二項(xiàng)信息就可以啦.
  - 那么第一項(xiàng)信息沒有引用指向, 就在鏈表中不再有效, 后面會被回收掉.
  img
- 移除其他項(xiàng)的信息:
  - 移除其他項(xiàng)的信息操作方式是相同的.
  - 首先, 我們需要通過while循環(huán), 找到正確的位置.
  - 找到正確位置后, 就可以直接將上一項(xiàng)的next指向current項(xiàng)的next, 這樣中間的項(xiàng)就沒有引用指向它, 也就不再存在于鏈表后, 會面會被回收掉.
  img
  
  img

測試removeAt方法

// 5.測試removeAt方法
list.removeAt(0)
list.removeAt(1)
list.removeAt(3)
alert(list) // 15, 10, 20

獲取元素位置

我們來完成另一個功能: 根據(jù)元素獲取它在鏈表中的位置

// 根據(jù)元素獲取鏈表中的位置
LinkedList.prototype.indexOf = function (element) {
    // 1.定義變量, 保存信息
    var current = this.head
    index = 0
    
    // 2.找到元素所在的位置
    while (current) {
        if (current.element === element) {
            return index
        }
        index++
        current = current.next
    }
    
    // 3.來到這個位置, 說明沒有找到, 則返回-1
    return -1
}

代碼解析:
- 代碼1的位置還是定義需要的變量.
- 代碼2的位置, 通過while循環(huán)獲取節(jié)點(diǎn)
- 通過節(jié)點(diǎn)獲取元素和element進(jìn)行對比, 如果和傳入element相同, 表示找到, 直接返回index即可.
- 如果沒有找到, index++, 并且指向下一個節(jié)點(diǎn).
- 到最后都沒有找到, 說明鏈表中沒有對應(yīng)的元素, 那么返回-1即可.

indexOf方法測試

// 6.測試indexOf方法
alert(list.indexOf(15)) // 0
alert(list.indexOf(10)) // 1
alert(list.indexOf(20)) // 2
alert(list.indexOf(100)) // -1

根據(jù)元素刪除

有了上面的indexOf方法, 我們可以非常方便實(shí)現(xiàn)根據(jù)元素來刪除信息

// 根據(jù)元素刪除信息
LinkedList.prototype.remove = function (element) {
    var index = this.indexOf(element)
    return this.removeAt(index)
}

代碼解析:
- 代碼簡單, 第一步獲取元素所在位置(已經(jīng)封裝好), 根據(jù)位置移除元素(已經(jīng)封裝好)

代碼測試:

// 7.測試remove方法
list.remove(15)
alert(list) // 10,20

其他方法實(shí)現(xiàn)

isEmpty方法

// 判斷鏈表是否為空
LinkedList.prototype.isEmpty = function () {
    return this.length == 0
}

size方法

// 獲取鏈表的長度
LinkedList.prototype.size = function () {
    return this.length
}

獲取第一個元素節(jié)點(diǎn): (單向鏈表比較方便的操作)

// 獲取第一個節(jié)點(diǎn)
LinkedList.prototype.getFirst = function () {
    return this.head.element
}

方法測試:

// 8.測試其他方法
alert(list.isEmpty()) // false
alert(list.size()) // 2
alert(list.getFirst()) // 10

四.完整代碼

我們給出一份完成的LinkedList代碼

// 封裝鏈表的構(gòu)造函數(shù)
function LinkedList() {
    // 封裝一個Node類, 用于保存每個節(jié)點(diǎn)信息
    function Node(element) {
        this.element = element
        this.next = null
    }

    // 鏈表中的屬性
    this.length = 0
    this.head = null

    // 鏈表尾部追加元素方法
    LinkedList.prototype.append = function (element) {
        // 1.根據(jù)新元素創(chuàng)建節(jié)點(diǎn)
        var newNode = new Node(element)

        // 2.判斷原來鏈表是否為空
        if (this.head === null) { // 鏈表尾空
            this.head = newNode
        } else { // 鏈表不為空
            // 2.1.定義變量, 保存當(dāng)前找到的節(jié)點(diǎn)
            var current = this.head
            while (current.next) {
                current = current.next
            }

            // 2.2.找到最后一項(xiàng), 將其next賦值為node
            current.next = newNode
        }

        // 3.鏈表長度增加1
        this.length++
    }

    // 鏈表的toString方法
    LinkedList.prototype.toString = function () {
        // 1.定義兩個變量
        var current = this.head
        var listString = ""

        // 2.循環(huán)獲取鏈表中所有的元素
        while (current) {
            listString += "," + current.element
            current = current.next
        }

        // 3.返回最終結(jié)果
        return listString.slice(1)
    }

    // 根據(jù)下標(biāo)刪除元素
    LinkedList.prototype.insert = function (position, element) {
        // 1.檢測越界問題: 越界插入失敗
        if (position < 0 || position > this.length) return false

        // 2.定義變量, 保存信息
        var newNode = new Node(element)
        var current = this.head
        var previous = null
        index = 0

        // 3.判斷是否列表是否在第一個位置插入
        if (position == 0) {
            newNode.next = current
            this.head = newNode
        } else {
            while (index++ < position) {
                previous = current
                current = current.next
            }

            newNode.next = current
            previous.next = newNode
        }

        // 4.length+1
        this.length++

        return true
    }

    // 根據(jù)位置移除節(jié)點(diǎn)
    LinkedList.prototype.removeAt = function (position) {
        // 1.檢測越界問題: 越界移除失敗, 返回null
        if (position < 0 || position >= this.length) return null

        // 2.定義變量, 保存信息
        var current = this.head
        var previous = null
        var index = 0

        // 3.判斷是否是移除第一項(xiàng)
        if (position === 0) {
            this.head = current.next
        } else {
            while (index++ < position) {
                previous = current
                current = current.next
            }

            previous.next = current.next
        }

        // 4.length-1
        this.length--

        // 5.返回移除的數(shù)據(jù)
        return current.element
    }

    // 根據(jù)元素獲取鏈表中的位置
    LinkedList.prototype.indexOf = function (element) {
        // 1.定義變量, 保存信息
        var current = this.head
        index = 0

        // 2.找到元素所在的位置
        while (current) {
            if (current.element === element) {
                return index
            }
            index++
            current = current.next
        }

        // 3.來到這個位置, 說明沒有找到, 則返回-1
        return -1
    }

    // 根據(jù)元素刪除信息
    LinkedList.prototype.remove = function (element) {
        var index = this.indexOf(element)
        return this.removeAt(index)
    }

    // 判斷鏈表是否為空
    LinkedList.prototype.isEmpty = function () {
        return this.length == 0
    }

    // 獲取鏈表的長度
    LinkedList.prototype.size = function () {
        return this.length
    }

    // 獲取第一個節(jié)點(diǎn)
    LinkedList.prototype.getFirst = function () {
        return this.head.element
    }
}

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

數(shù)據(jù)結(jié)構(gòu)(五)之鏈表結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)(五)之鏈表結(jié)構(gòu)

一. 認(rèn)識鏈表

鏈表和數(shù)組

什么是鏈表?

二. 鏈表封裝

創(chuàng)建鏈表類

鏈表常見操作

三. 鏈表操作

尾部追加數(shù)據(jù)

toString方法

任意位置插入

位置移除數(shù)據(jù)

獲取元素位置

根據(jù)元素刪除

其他方法實(shí)現(xiàn)

四.完整代碼

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

數(shù)據(jù)結(jié)構(gòu)(五)之鏈表結(jié)構(gòu)

一. 認(rèn)識鏈表

鏈表和數(shù)組

什么是鏈表?

二. 鏈表封裝

創(chuàng)建鏈表類

鏈表常見操作

三. 鏈表操作

尾部追加數(shù)據(jù)

toString方法

任意位置插入

位置移除數(shù)據(jù)

獲取元素位置

根據(jù)元素刪除

其他方法實(shí)現(xiàn)

四.完整代碼

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av