在 PHP 中實現連結串列

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

本文將介紹 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);

在下面的示例中,我們在一個空連結串列中附加了元素 1020304040。請注意,元素 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() 方法通過指定位置在連結串列中插入元素。該方法有兩個引數。

第一個引數是要插入專案的索引,第二個引數是要插入的專案。例如,以 450 為引數呼叫 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
作者: Subodh Poudel
Subodh Poudel avatar Subodh Poudel avatar

Subodh is a proactive software engineer, specialized in fintech industry and a writer who loves to express his software development learnings and set of skills through blogs and articles.

LinkedIn