PHP資料結構基礎之雙鍊錶

這篇文章主要介紹了關於PHP資料結構基礎之雙鍊錶，有著一定的參考價值，現在分享給大家，有需要的朋友可以參考一下

什麼是雙鍊錶？

上一篇實戰PHP資料結構基礎之單鍊錶說到

單鍊錶由一個一個的作為節點的物件構成的，每一個節點都有指向下一個節點的指針，最後一個節點的指標域指向空。每個節點可以儲存任何資料類型。

而雙鍊錶每個節點有兩個指標域，分別指向前驅和後繼節點。單鍊錶是單向的，而雙鍊錶是雙向的。

常見運算

對雙鍊錶我們常見的操作有如下：

• #insert

• ##insertBefore

• insertAfter

• insertAtFirst

• insertAtLast

• # #deleteFirst

• deleteLast

• #delete

• ##reverse

getNthNode

...

#PHP語言實作

首先我們根據定義實作一個雙鍊錶的ListNode類。

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

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

再來看鍊錶類，首先需要3個私有屬性，分別是頭節點、尾巴節點和長度。

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

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

/**
 * 插入一个节点
 * @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;
    }

}

再來看如何刪除節點。

/**
 * 删除一个节点
 * @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;
}

反轉雙鍊錶也不是很複雜。

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;
        }
    }
}

雙鍊錶其他操作的詳細實作可以參考 這裡。

雙鍊錶是鍊錶這種鍊式存取資料結構中相對於單鍊錶比較特殊的部分，同樣屬於鍊錶結構的還有單鍊錶，環形鍊錶和多鍊錶。

專題系列
PHP基礎資料結構專題系列目錄位址：https://github.com/... 主要使用PHP語法總結基礎的資料結構與演算法。還有我們日常PHP開發中容易忽略的基礎知識和現代PHP開發中關於規格、部署、最佳化的一些實戰性建議，同時還有對Javascript語言特徵的深入研究。

###以上就是本文的全部內容，希望對大家的學習有所幫助，更多相關內容請關注PHP中文網！ ######相關推薦：#########PHP資料結構基礎之棧################php7 的php-fpm參數配置的注意事項# ########

以上是PHP資料結構基礎之雙鍊錶的詳細內容。更多資訊請關注PHP中文網其他相關文章！