實戰PHP數據結構基礎之單鏈表

xumenger 發布于2019-07-01 10:06 / 2847人閱讀

摘要：常見操作對單鏈表我們常見的操作有如下語言實現首先我們根據定義實現一個類。單鏈表是鏈表這種鏈式存取數據結構中基礎的部分，同樣屬于鏈表結構的還有雙鏈表，環形鏈表和多鏈表。專題系列基礎數據結構專題系列目錄地址主要使用語法總結基礎的數據結構和算法。

什么是鏈表？

鏈表由一個一個的作為節點的對象構成的，每一個節點都有指向下一個節點的指針，最后一個節點的指針域指向空。每個節點可以存儲任何數據類型。

常見操作

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

insert

insertBefore

insertAfter

insertAtFirst

deleteFirst

deleteLast

delete

reverse

getNthNode

...

PHP語言實現

首先我們根據定義實現一個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;
    }
}

再來看鏈表類，首先需要2個私有屬性，分別是頭節點和長度。

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

下面我們長話短說，直接看如何實現第一個即常用的插入，這是是一個平均時間復雜度為O(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;
}

再來看搜索，同樣是一個平均時間復雜度為O(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;
}

反轉單鏈表

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

}

單鏈表其他操作的詳細實現可以參考這里。

單鏈表是鏈表這種鏈式存取數據結構中基礎的部分，同樣屬于鏈表結構的還有雙鏈表，環形鏈表和多鏈表。

專題系列

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

云服務器 GPU云服務器單鏈表數據單鏈表存儲結構單鏈表數據結構 c++ 單鏈表鏈表

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/28795.html

實戰PHP數據結構基礎之雙鏈表

摘要：什么是雙鏈表上一篇實戰數據結構基礎之單鏈表說到單鏈表由一個一個的作為節點的對象構成的，每一個節點都有指向下一個節點的指針，最后一個節點的指針域指向空。什么是雙鏈表？上一篇實戰PHP數據結構基礎之單鏈表說到單鏈表由一個一個的作為節點的對象構成的，每一個節點都有指向下一個節點的指針，最后一個節點的指針域指向空。每個節點可以存儲任何數據類型。而雙鏈表每個節點有兩個指針域，分別指向前驅...

Michael_Lin 2019-07-01 10:07 評論0 收藏0
PHPer也刷《劍指Offer》之鏈表

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

daydream 2019-07-01 10:11 評論0 收藏0
[個人心得]數據結構之單鏈表

摘要：一個單向鏈表包含兩個值當前節點的值和一個指向下一個節點的鏈接。為退出循環即已到了最后一個節點那么它的為加入節點后，要把單鏈表長度加一。第個節點是運行結果個人源碼地址單鏈表就寫到這里咯，接下來還會寫其他的數據結構本人也在學習當中。維基百科鏈表是一種常見的基礎數據結構，是一種線性表，但是并不會按線性的順序存儲數據，而是在每一個節點里存到下一個節點的指針。鏈表中最簡單的一種是單向鏈...

bingchen 2019-08-21 17:53 評論0 收藏0
圖解幾種常見的線性表

摘要：下面來看一下，有哪些數據結構屬于線性表吧棧特性先進后出只有唯一的一個出入口介紹棧又名堆棧，它是一種運算受限的線性表。原文是在我自己博客中，小伙伴也可以點閱讀原文進行跳轉查看，還有好聽的背景音樂噢背景音樂已取消~ 2333333 線性表什么是線性表？就是一種連續或間斷存儲的數組，這里的連續和間斷是針對物理內存空間中線性表元素之間是否連續，其中連續數組對應內置數組的實現方式，間斷數組對...

wawor4827 2019-07-01 10:01 評論0 收藏0