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

xumenger 發(fā)布于2019-07-01 10:06 / 2864人閱讀

摘要：常見操作對(duì)單鏈表我們常見的操作有如下語(yǔ)言實(shí)現(xiàn)首先我們根據(jù)定義實(shí)現(xiàn)一個(gè)類。單鏈表是鏈表這種鏈?zhǔn)酱嫒?shù)據(jù)結(jié)構(gòu)中基礎(chǔ)的部分，同樣屬于鏈表結(jié)構(gòu)的還有雙鏈表，環(huán)形鏈表和多鏈表。專題系列基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)專題系列目錄地址主要使用語(yǔ)法總結(jié)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法。

什么是鏈表？

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

常見操作

對(duì)單鏈表我們常見的操作有如下：

insert

insertBefore

insertAfter

insertAtFirst

deleteFirst

deleteLast

delete

reverse

getNthNode

...

PHP語(yǔ)言實(shí)現(xiàn)

首先我們根據(jù)定義實(shí)現(xiàn)一個(gè)ListNode類。

class ListNode
{
    private $data;
    private $next;

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

    public function __get($var)
    {
        return $this->$var;
    }

    public function __set($var, $val)
    {
        return $this->$var = $val;
    }
}

再來(lái)看鏈表類，首先需要2個(gè)私有屬性，分別是頭節(jié)點(diǎn)和長(zhǎng)度。

class LinkedList
{
    private $head;
    private $length;
}

下面我們長(zhǎng)話短說(shuō)，直接看如何實(shí)現(xiàn)第一個(gè)即常用的插入，這是是一個(gè)平均時(shí)間復(fù)雜度為O(n)的操作。

/**
 * 插入一個(gè)節(jié)點(diǎn)
 * @param string|null $data
 * @return bool
 * complexity O(n)
 */
public function insert(string $data = null)
{
    $newNode = new ListNode($data);

    if ($this->head === null) {
        $this->head = &$newNode;
    } else {
        $currentNode = $this->head;
        while ($currentNode->next !== null) {
            $currentNode = $currentNode->next;
        }

        $currentNode->next = $newNode;
    }

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

再來(lái)看搜索，同樣是一個(gè)平均時(shí)間復(fù)雜度為O(n)的操作。

/**
 * 搜索一個(gè)節(jié)點(diǎn)
 * @param string $data
 * @return bool|ListNode
 * complexity O(n)
 */
public function search(string $data)
{
    if ($this->length > 0) {
        $currentNode = $this->head;
        while ($currentNode !== null) {
            if ($currentNode->data === $data) {
                return $currentNode;
            }

            $currentNode = $currentNode->next;
        }
    }

    return false;
}

反轉(zhuǎn)單鏈表

public function reverse()
{
    if ($this->head !== null) {
        if ($this->head->next !== null) {
            $reveredList = null;
            $next = null;
            $currentNode = $this->head;

            while ($currentNode !== null) {
                $next = $currentNode->next;
                $currentNode->next = $reveredList;
                $reveredList = $currentNode;
                $currentNode = $next;
            }

            $this->head = $reveredList;
        }
    }

}

單鏈表其他操作的詳細(xì)實(shí)現(xiàn)可以參考這里。

單鏈表是鏈表這種鏈?zhǔn)酱嫒?shù)據(jù)結(jié)構(gòu)中基礎(chǔ)的部分，同樣屬于鏈表結(jié)構(gòu)的還有雙鏈表，環(huán)形鏈表和多鏈表。

專題系列

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