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

資訊專欄INFORMATION COLUMN

實戰(zhàn)PHP數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之雙鏈表

Michael_Lin / 3187人閱讀

摘要：什么是雙鏈表上一篇實戰(zhàn)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之單鏈表說到單鏈表由一個一個的作為節(jié)點的對象構(gòu)成的，每一個節(jié)點都有指向下一個節(jié)點的指針，最后一個節(jié)點的指針域指向空。

什么是雙鏈表？

上一篇實戰(zhàn)PHP數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之單鏈表說到

單鏈表由一個一個的作為節(jié)點的對象構(gòu)成的，每一個節(jié)點都有指向下一個節(jié)點的指針，最后一個節(jié)點的指針域指向空。每個節(jié)點可以存儲任何數(shù)據(jù)類型。

而雙鏈表每個節(jié)點有兩個指針域，分別指向前驅(qū)和后繼節(jié)點。單鏈表是單向的，而雙鏈表是雙向的。

常見操作

對雙鏈表我們常見的操作有如下：

insert

insertBefore

insertAfter

insertAtFirst

insertAtLast

deleteFirst

deleteLast

delete

reverse

getNthNode

...

PHP語言實現(xiàn)

首先我們根據(jù)定義實現(xiàn)一個雙鏈表的ListNode類。

class ListNode
{
    public $data = null;
    public $next = null;
    public $prev = null;

    public function __construct(string $data)
    {
        $this->data = $data;
    }
}

再來看鏈表類，首先需要3個私有屬性，分別是頭節(jié)點、尾巴節(jié)點和長度。

class DoubleLinkedList
{
    private $head = null;
    private $last = null;
    private $length = 0;
}

接下來還是老規(guī)矩，直接看如何實現(xiàn)第一個即常用的插入，這是是一個平均時間復雜度為O(n)的操作。

/**
 * 插入一個節(jié)點
 * @param string|null $data
 * @return bool
 * complexity O(n)
 */
public function insert(string $data = null)
{
    $newNode = new ListNode($data);
    if ($this->head) {
        $currentNode = $this->head;
        while ($currentNode) {
            if ($currentNode->next === null) {
                $currentNode->next = $newNode;
                $newNode->prev = $currentNode;
                $this->last = $newNode;
                $this->length++;
                return true;
            }

            $currentNode = $currentNode->next;
        }
    } else {
        $this->head = &$newNode;
        $this->last = $newNode;
        $this->length++;
        return true;
    }

}

再來看如何刪除節(jié)點。

/**
 * 刪除一個節(jié)點
 * @param string $data
 * @return bool|ListNode
 * complexity O(n)
 */
public function delete(string $query = null)
{
if ($this->head) {
    $currentNode = $this->head;
    $prevNode = null;

    while ($currentNode) {
        if ($currentNode->data === $query) {
            if ($nextNode = $currentNode->next) {
                if ($prevNode) {
                    $prevNode->next = $nextNode;
                    $nextNode->prev = $prevNode;
                } else {
                    $this->head = $nextNode;
                    $nextNode->prev = null;
                }

                unset($currentNode);
            } else {
                if ($prevNode) {
                    $this->last = $prevNode;
                    $prevNode->next = null;
                    unset($currentNode);
                } else {
                    $this->head = null;
                    $this->last = null;
                }
            }

            $this->length--;
            return true;
        }

        $prevNode = $currentNode;
        $currentNode = $currentNode->next;
    }
}

    return false;
}

反轉(zhuǎn)雙鏈表也不是很復雜。

public function reverse()
{
    if ($this->head !== null) {

        if ($this->head->next !== null) {
            $reversedList = null;
            $currentNode = $this->head;

            while ($currentNode !== null) {
                $next = $currentNode->next;
                $currentNode->next = $reversedList;
                $currentNode->prev = $next;

                $reversedList = $currentNode;
                $currentNode = $next;

            }

            $this->last = $this->head;
            $this->head = $reversedList;
        }
    }
}

雙鏈表其他操作的詳細實現(xiàn)可以參考 這里。

雙鏈表是鏈表這種鏈式存取數(shù)據(jù)結(jié)構(gòu)中相對于單鏈表比較特殊的部分，同樣屬于鏈表結(jié)構(gòu)的還有單鏈表，環(huán)形鏈表和多鏈表。

專題系列

PHP基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)專題系列目錄地址：https://github.com/... 主要使用PHP語法總結(jié)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法。還有我們?nèi)粘HP開發(fā)中容易忽略的基礎(chǔ)知識和現(xiàn)代PHP開發(fā)中關(guān)于規(guī)范、部署、優(yōu)化的一些實戰(zhàn)性建議，同時還有對Javascript語言特點的深入研究。

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

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

相關(guān)文章

  • PHPer也刷《劍指Offer》之鏈表

    摘要：劍指中鏈表相關(guān)題目俗話說光說不練假把式，既然學習了鏈表的基礎(chǔ)概念和基本操作那我們一定要找些題目鞏固下，下面來看劍指中的相關(guān)題目。題目分析合并兩個排序的鏈表，需要分別比較兩個鏈表的每個值，然后改變指針。 溫故知新 鏈表由一個一個的作為節(jié)點的對象構(gòu)成的，每一個節(jié)點都有指向下一個節(jié)點的指針，最后一個節(jié)點的指針域指向空。每個節(jié)點可以存儲任何數(shù)據(jù)類型。 根據(jù)類型可以分為單鏈表、雙鏈表、環(huán)形鏈表、...

    daydream 評論0 收藏0

  • 實戰(zhàn)PHP數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之單鏈表

    摘要：常見操作對單鏈表我們常見的操作有如下語言實現(xiàn)首先我們根據(jù)定義實現(xiàn)一個類。單鏈表是鏈表這種鏈式存取數(shù)據(jù)結(jié)構(gòu)中基礎(chǔ)的部分，同樣屬于鏈表結(jié)構(gòu)的還有雙鏈表，環(huán)形鏈表和多鏈表。專題系列基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)專題系列目錄地址主要使用語法總結(jié)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法。 什么是鏈表？ 鏈表由一個一個的作為節(jié)點的對象構(gòu)成的，每一個節(jié)點都有指向下一個節(jié)點的指針，最后一個節(jié)點的指針域指向空。每個節(jié)點可以存儲任何數(shù)據(jù)類型。...

    xumenger 評論0 收藏0

  • 實戰(zhàn)PHP數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之棧

    摘要：棧和隊列棧和隊列和之前講到的實戰(zhàn)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之雙鏈表一樣都是線性結(jié)構(gòu)。來看基于數(shù)組的棧實現(xiàn)得益于強大的結(jié)構(gòu)，我們輕而易舉的寫出來了棧的基本操作方法。專題系列基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)專題系列目錄地址主要使用語法總結(jié)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法。 棧和隊列 棧和隊列和之前講到的實戰(zhàn)PHP數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)之雙鏈表 一樣都是線性結(jié)構(gòu)。 棧有什么特點 棧遵循后進先出的原則(LIFO)。這意味著棧只有一個出口用來壓入元素...

    banana_pi 評論0 收藏0

  • [個人心得]數(shù)據(jù)結(jié)構(gòu)之雙鏈表

    摘要：一般我們都構(gòu)造雙向循環(huán)鏈表。循環(huán)鏈表的操作和單鏈表的操作基本一致，差別僅僅在于算法中的循環(huán)條件有所不同。單向循環(huán)鏈表雙向循環(huán)鏈表單向循環(huán)鏈表是在單鏈表基礎(chǔ)上，將最后一個節(jié)點的指針指向鏈表頭。 維基百科 雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點開始，都可以很方便地訪問它的前驅(qū)結(jié)點和后繼結(jié)點。一般我們都構(gòu)...

    jokester 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<