摘要:什么是單向鏈表鏈表是以鏈式存儲數據的結構,其不需要連續的存儲空間,鏈表中的數據以節點來表示,每個節點由元素存儲數據和指針指向后繼節點組成。單向鏈表也叫單鏈表是鏈表中最簡單的一種形式,每個節點只包含一個元素和一個指針。
什么是單向鏈表
鏈表是以鏈式存儲數據的結構,其不需要連續的存儲空間,鏈表中的數據以節點來表示,每個節點由元素(存儲數據)和指針(指向后繼節點)組成。
單向鏈表(也叫單鏈表)是鏈表中最簡單的一種形式,每個節點只包含一個元素和一個指針。
它有一個表頭,并且除了最后一個節點外,所有節點都有其后繼節點。
它的存儲結構如下圖所示
代碼實現
定義節點
class Node { public $data; /** * @var null | Node */ public $next; public function __construct($data) { $this->data = $data; $this->next = null; } }
單鏈表實現
/** * Class SingleLinkList * 單鏈接的實現示例,實現簡單的填加,插入,刪除, 查詢,長度,遍歷這幾個簡單操作 */ class SingleLinkList { /** * 鏈表頭結點,頭節點必須存在, * @var Node */ public $header; private $size = 0; /** * 構造函數,默認填加一個哨兵節點,該節點元素為空 * SingleLinkList constructor. */ public function __construct() { $this->header = new Node(null); } /** * 在鏈表末尾添加節點 * @param Node $node * @return int */ public function addNode(Node $node) { $current = $this->header; while ($current->next != null) { $current = $current->next; } $current->next = $node; return ++$this->size; } /** * 在指定位置插入節點 * @param int $index 節點位置,從1開始計數 * @param Node $node * @return int * @throws Exception */ public function insertNodeByIndex($index, Node $node) { if ($index < 1 || $index > ($this->size + 1)) { throw new Exception(sprintf("你要插入的位置,超過了鏈表的長度 %d", $this->size)); } $current = $this->header; $tempIndex = 1; do { if ($index == $tempIndex++) { $node->next = $current->next; $current->next = $node; break; } } while ($current->next != null && ($current = $current->next)); return ++$this->size; } /** * 刪除節點 * @param int $index 節點位置,從1開始計數 * @return int * @throws Exception */ public function deleteNodeByIndex($index) { if ($index < 1 || $index > ($this->size + 1)) { throw new Exception("你刪除的節點不存在"); } $current = $this->header; $tempIndex = 1; do { if ($index == $tempIndex++) { $current->next = $current->next->next; break; } } while ($current->next != null && ($current = $current->next)); return --$this->size; } /** * 查詢節點 * @param int $index 節點位置,從1開始計數 * @return Node|null * @throws Exception */ public function searchNodeByIndex($index) { if ($index < 1 || $index > ($this->size + 1)) { throw new Exception("你查詢的節點不存在"); } $current = $this->header; $tempIndex = 1; do { if ($index == $tempIndex++) { return $current->next; } } while ($current->next != null && ($current = $current->next)); } /** * 獲取節點長度 * @return int */ public function getLength() { return $this->size; } /** * 遍歷列表 */ public function showNode() { $current = $this->header; $index = 1; while ($current->next != null) { $current = $current->next; echo "index --- " . $index++ . " --- "; echo var_export($current->data); echo PHP_EOL; } } }
示例
$link = new SingleLinkList(); $link->addNode(new Node(1)); $link->addNode(new Node(2)); $link->insertNodeByIndex(3, new Node(3)); $link->addNode(new Node(4)); $link->addNode(new Node(5)); echo $link->getLength(), PHP_EOL; $link->showNode(); echo "-----------", PHP_EOL; var_dump($link->searchNodeByIndex(3)); echo "-----------", PHP_EOL; $link->deleteNodeByIndex(3); $link->showNode();
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/29873.html
摘要:一鏈表鏈表是一種常見的基礎數據結構,是一種線性表,但是并不會按線性的順序存儲數據,而是在每一個節點里存到下一個節點的指針。指向整個列表的指針可以被稱作訪問指針。 你好,是我琉憶,PHP程序員面試筆試系列圖書的作者。 本周(2019.3.18至3.22)的一三五更新的文章如下: 周一:PHP面試常考之數據結構——鏈表的概念周三:PHP面試常考之數據結構——棧和隊列周五:PHP面試常考之...
摘要:下面來看一下,有哪些數據結構屬于線性表吧棧特性先進后出只有唯一的一個出入口介紹棧又名堆棧,它是一種運算受限的線性表。 原文是在我自己博客中,小伙伴也可以點閱讀原文進行跳轉查看,還有好聽的背景音樂噢背景音樂已取消~ 2333333 線性表 什么是線性表?就是一種連續或間斷存儲的數組,這里的連續和間斷是針對物理內存空間中線性表元素之間是否連續,其中連續數組對應內置數組的實現方式,間斷數組對...
摘要:實現移除給定的元素要移除的元素返回值表示移除成功方法說明移除單向鏈表中某個位置的元素。的前端樂園原文鏈接寒假前端學習學習數據結構與算法二鏈表 本系列的第一篇文章: 學習JavaScript數據結構與算法(一),棧與隊列第二篇文章:學習JavaScript數據結構與算法(二):鏈表第三篇文章:學習JavaScript數據結構與算法(三):集合第四篇文章:學習JavaScript數據結構與...
摘要:鏈表鏈表存儲有序的元素集合,但不同于數組,鏈表中的元素在內存中并不是連續放置的。相對于傳統的數組,鏈表的一個好處在于,添加或者刪除元素的時候不需要移動其他元素。 鏈表 鏈表存儲有序的元素集合,但不同于數組,鏈表中的元素在內存中并不是連續放置的。每個元素由一個存儲元素本事的節點和一個指向下一個元素的引用組成。相對于傳統的數組,鏈表的一個好處在于,添加或者刪除元素的時候不需要移動其他元素。...
閱讀 2964·2023-04-26 02:04
閱讀 1278·2021-11-04 16:07
閱讀 3699·2021-09-22 15:09
閱讀 678·2019-08-30 15:54
閱讀 1899·2019-08-29 14:11
閱讀 2525·2019-08-26 12:19
閱讀 2255·2019-08-26 12:00
閱讀 752·2019-08-26 10:27