在 PHP 中實現連結串列

1. 使用 SplDoublyLinkedList 類在 PHP 中實現連結串列
2. 使用 push() 方法在連結串列中插入值
3. 使用 add() 方法在連結串列中插入值
4. 使用 pop() 方法刪除連結串列中的元素
5. 從連結列表中查詢頂部和底部值

本文將介紹 PHP 中連結串列的實現。

使用 SplDoublyLinkedList 類在 PHP 中實現連結串列

連結串列是在許多程式語言中實現的常見資料結構。它是線性的，包含相互連結的節點。

每個節點都包含資料和到相鄰節點的連結。因此，連結串列形成了一個節點鏈。連結串列有不同的變體。

1. 單連結串列：單向。它只在向前的方向上移動。
2. 雙連結串列：是雙向的。它向前和向後兩個方向遍歷。
3. 迴圈連結串列：單向迴圈。
4. 迴圈雙向連結串列：雙向迴圈。

我們可以在連結串列中進行各種操作。基本操作如下：

• 遍歷
• 插入
• 刪除
• 更新
• 搜尋

PHP 提供了一個類 SplDoublyLinkedList 用於實現連結串列。它是一個雙向連結串列。

使用 push() 方法在連結串列中插入值

push() 方法接受要推送的引數並允許在列表中附加值。該元素將被推到連結串列的末尾。

例如，建立類 SplDoublyLinkedList 的例項並將其分配給 $list 變數。呼叫 push() 方法並插入元素。

示例程式碼：

$list = new SplDoublyLinkedList;

$list->push(10);
$list->push(20);
$list->push(30);
$list->push(40);
$list->push(40);

在下面的示例中，我們在一個空連結串列中附加了元素 10、20、30、40 和 40。請注意，元素 40 被附加了兩次。

我們可以使用下面的函式來顯示列表的元素。

function displayList($list){
  for ($list->rewind(); $list->valid(); $list->next()) {
    echo $list->current()."<br>";
  }
}

rewind() 方法從連結串列的開頭回退迭代器。例如，迭代器將移動到列表的第一個元素。

valid() 方法檢查連結串列是否包含更多節點，next() 方法移動到連結串列的下一項。因此，我們可以在 for 迴圈中使用上述示例中的這些方法來遍歷連結串列的元素。

在迴圈內部，current() 方法表示當前元素。因此，將列印當前元素。

當我們需要列印列表元素時，我們可以呼叫這個函式 displayList()。我們將在文章中多次使用此功能。

以下是我們以 $list 作為引數呼叫 displayList() 函式時的輸出。

輸出：

10
20
30
40
40

使用 add() 方法在連結串列中插入值

我們可以使用 add() 方法通過指定位置在連結串列中插入元素。該方法有兩個引數。

第一個引數是要插入專案的索引，第二個引數是要插入的專案。例如，以 4 和 50 為引數呼叫 add() 方法並呼叫 displayList() 方法。

示例程式碼：

$list->add(4,50);
displayList($list);

上面的程式碼在我們建立的連結串列的第四個索引中新增了元素 50。

輸出：

10
20
30
40
50
40

結果，元素 50 出現在第四個索引中。之前在第四個索引中的元素 40 被移動到連結串列的末尾。

使用 pop() 方法刪除連結串列中的元素

我們可以使用 pop() 方法從連結串列中刪除最後一個元素。該方法不接受任何引數。

從上面的最後一個輸出開始，該列表包含以下元素。

10
20
30
40
50
40

pop() 方法將從連結串列中刪除最後一個元素（40）。

示例程式碼：

$list->pop();
displayList($list);

輸出：

10
20
30
40
50

從連結列表中查詢頂部和底部值

我們可以使用 top() 方法找到連結串列的頂部值，對於底部值，我們可以使用 bottom() 方法。下面的例子也是上面例子的延續。

該列表包含以下專案。

10
20
30
40
50

我們可以使用 $list 物件呼叫 top() 和 bottom() 函式，並使用 echo 函式列印它們。

示例程式碼：

displayList($list);
echo "the top value: ".$list->top()."<br>";
echo "the bottom value: ".$list->bottom()."<br>";

結果，最上面的專案顯示為 50，最底部的專案顯示為 10。

輸出：

10
20
30
40
50
the top value: 50
the bottom value: 10