前面已經(jīng)介紹了很多關(guān)于數(shù)組的內(nèi)容.下面我們來(lái)討論一下鏈表.在多數(shù)語(yǔ)言中,數(shù)組是定長(zhǎng)的結(jié)構(gòu),當(dāng)然就不能動(dòng)態(tài)增長(zhǎng),縮減和移除.出于這些原因,大多數(shù)開(kāi)發(fā)者都偏向于使用鏈表來(lái)代替數(shù)組.考慮到PHP數(shù)組中有額外的字節(jié)消耗,而鏈表的對(duì)內(nèi)存使用的效率很高.下面將介紹PHP中不同類型的鏈表以及實(shí)現(xiàn).
鏈表是什么?
鏈表是節(jié)點(diǎn)的集合.每一個(gè)節(jié)點(diǎn)通過(guò)鏈表相互連接.節(jié)點(diǎn)可以存儲(chǔ)任何數(shù)據(jù)結(jié)構(gòu)和內(nèi)容.
鏈表有以下操作:
- 鏈表是否為空
- 遍歷所有節(jié)點(diǎn)
- 搜索某一節(jié)點(diǎn)
- 求鏈表長(zhǎng)度
- 插入新節(jié)點(diǎn)
- 移除節(jié)點(diǎn)
- 鏈表的反轉(zhuǎn)
下面描述一種簡(jiǎn)單的節(jié)點(diǎn),包含節(jié)點(diǎn)數(shù)據(jù)和下一個(gè)節(jié)點(diǎn)的地址
next:
class ListNode {
public $data = NULL;
public $next = NULL;
public function __construct(string $data = NULL) {
$this->data = $data;
}
}
下面看一個(gè) 鏈表 LinkedList 的實(shí)現(xiàn) ,包含insert和display操作
class LinkedList {
private $_firstNode = NULL;
private $_totalNodes = 0;
public function insert(string $data = NULL) {
$newNode = new ListNode($data);
if ($this->_firstNode === NULL) {
$this->_firstNode = &$newNode;
} else {
$currentNode = $this->_firstNode;
while ($currentNode->next !== NULL) {
$currentNode = $currentNode->next;
}
$currentNode->next = $newNode;
}
$this->_totalNode++;
return TRUE;
}
public function display() {
echo "Total book titles: ".$this->_totalNode."\n";
$currentNode = $this->_firstNode;
while ($currentNode !== NULL) {
echo $currentNode->data . "\n";
$currentNode = $currentNode->next;
}
}
}
$linked_list = new LinkedList();
$linked_list->insert(1);
$linked_list->insert(2);
$linked_list->insert(3);
$linked_list->insert(4);
$linked_list->display();
返回結(jié)果:
Total book titles: 4
1 2 3 4
不同類型的鏈表
到此我們已經(jīng)實(shí)現(xiàn)了一種最簡(jiǎn)單的單向鏈表類 LinkedList 這里還有其他幾中鏈表
- 雙向鏈表
- 環(huán)向列表
- 多鏈表
雙向列表
環(huán)向列表
多鏈表
鏈表的插入,刪除,查找
前面了解了鏈表的插入和遍歷操作,下面來(lái)看一下鏈表的其他操作
- 在第一個(gè)節(jié)點(diǎn)處插入
- 節(jié)點(diǎn)的搜索
- 在特殊節(jié)點(diǎn)前插入
- 在特殊節(jié)點(diǎn)后插入
- 刪除第一個(gè)節(jié)點(diǎn)
- 刪除最后一個(gè)節(jié)點(diǎn)
- 搜索和刪除一個(gè)節(jié)點(diǎn)
- 鏈表的反轉(zhuǎn)
- 獲取第N個(gè)位置的元素
下面依次討論
在第一個(gè)節(jié)點(diǎn)處插入
節(jié)點(diǎn)搜索
public function insertAtFirst(string $data = NULL) {
$newNode = new ListNode($data);
if ($this->_firstNode === NULL) {
$this->_firstNode = &$newNode;
} else {
$currentFirstNode = $this->_firstNode;
$this->_firstNode = &$newNode;
$newNode->next = $currentFirstNode;
}
$this->_totalNode++;
return TRUE;
}
在特殊節(jié)點(diǎn)前插入
public function insertBefore(string $data = NULL, string $query =NULL)
{
$newNode = new ListNode($data);
if ($this->_firstNode && $this->_firstNode->data = $query) {
$newNode->next = $this->_firstNode;
$this->_firstNode-> &$newNode;
}
if ($this->_firstNode !== NULL) {
$previous = NULL;
$currentNode = $this->_firstNode;
while ($currentNode !== NULL) {
if ($currentNode->data === $query) {
$previous->next = &$newNode;
$newNode->next = $currentNode;
$this->_totalNode++;
break;
}
$previous = $currentNode;
$currentNode = $currentNode->next;
}
}
}
在特定節(jié)點(diǎn)后插入
public function insertAfter(string $data = NULL, string $query =NULL)
{
$newNode = new ListNode($data);
if ($this->_firstNode !== NULL) {
$currentNode = $this->_firstNode;
while ($currentNode !== NULL) {
if ($currentNode->data === $query) {
$newNode->next = $currentNode->next;
$currentNode->next = &$newNode;
$this->_totalNode++;
break;
}
$currentNode = $currentNode->next;
}
}
}
鏈表的反轉(zhuǎn)
public function reverse() {
if ($this->_firstNode !== NULL) {
if ($this->_firstNode->next !== NULL) {
$reversedList = NULL;
$next = NULL;
$currentNode = $this->_firstNode;
while ($currentNode !== NULL) {
$next = $currentNode->next;
$currentNode->next = $reversedList;
$reversedList = $currentNode;
$currentNode = $next;
}
$this->_firstNode = $reversedList;
}
}
}
獲取第N個(gè)位置的元素
public function getNthNode(int $n = 0)
{
$count = 1;
if ($this->_firstNode !== NULL) {
$currentNode = $this->_firstNode;
while ($currentNode !== NULL) {
if ($count === $n) {
return $currentNode;
}
$count++;
$currentNode = $currentNode->next;
}
}
}
理解鏈表的算法復(fù)雜度
| 操作 | 時(shí)間復(fù)雜度:最差 | 事件復(fù)雜度:平均 |
|---|---|---|
| 在首,尾插入 | O(1) | O(1) |
| 在首尾刪除 | O(1) | O(1) |
| 搜索 | O(n) | O(n) |
| 訪問(wèn) | O(n) | O(n) |
使鏈表可迭代
上面我們使用 while 遍歷鏈表的每一個(gè)節(jié)點(diǎn).那我們可以通過(guò)鏈表本身進(jìn)行迭代嗎?PHP 有非常直觀的 Iterator（迭代器） 接口
- Current
- Next
- Key
- Rewind
- Valid
上面的方法可以通過(guò) php 手冊(cè)查詢,不再贅述.下面我們將通過(guò)類 LinkedList 來(lái)實(shí)現(xiàn)上述接口來(lái)實(shí)現(xiàn)直接進(jìn)行節(jié)點(diǎn)的迭代.為了在迭代的過(guò)程中追蹤當(dāng)前節(jié)點(diǎn)和當(dāng)前的位置,類 LinkedList 需要額外的兩個(gè)屬性
private $_currentNode = NULL; // 當(dāng)前節(jié)點(diǎn)
private $_currentPosition = 0; // 當(dāng)前位置
下面實(shí)現(xiàn) Iterator（迭代器）的5個(gè)方法
#pragram make implements Iterator
public function current()
{
return $this->_currentNode->data;
}
public function next()
{
$this->_currentPosition++;
$this->_currentNode = $this->_currentNode->next;
}
public function key() {
return $this->_currentPosition;
}
public function rewind() {
$this->_currentPosition = 0;
$this->_currentNode = $this->_firstNode;
}
public function valid() {
return $this->_currentNode !== NULL;
}
哈哈,現(xiàn)在我們有了列表的迭代方法了,意味著我們可以使用 foreach 或者其他過(guò)程函數(shù)來(lái)進(jìn)行迭代:例如下面:
foreach ($BookTitles as $title) {
echo $title . "\n";
}
for ($BookTitles->rewind(); $BookTitles->valid(); $BookTitles->next()) {
echo $BookTitles->current() . "\n";
}
雙向列表
后面雙向列表和多向列表的內(nèi)容和算法我覺(jué)得不需要在贅述了,有空在寫(xiě)吧
使用 PHP SplDoublyLinkedList
如果我們使用內(nèi)置的類,我們不需要去實(shí)現(xiàn)雙向列表.官方手冊(cè)中清楚的列出了雙向列表的接口,這里也不再介紹了,下面就舉個(gè)例子:
