摘要：什么是單向鏈表鏈表是以鏈?zhǔn)酱鎯?chǔ)數(shù)據(jù)的結(jié)構(gòu)，其不需要連續(xù)的存儲(chǔ)空間，鏈表中的數(shù)據(jù)以節(jié)點(diǎn)來表示，每個(gè)節(jié)點(diǎn)由元素存儲(chǔ)數(shù)據(jù)和指針指向后繼節(jié)點(diǎn)組成。單向鏈表也叫單鏈表是鏈表中最簡單的一種形式，每個(gè)節(jié)點(diǎn)只包含一個(gè)元素和一個(gè)指針。

什么是單向鏈表

鏈表是以鏈?zhǔn)酱鎯?chǔ)數(shù)據(jù)的結(jié)構(gòu)，其不需要連續(xù)的存儲(chǔ)空間，鏈表中的數(shù)據(jù)以節(jié)點(diǎn)來表示，每個(gè)節(jié)點(diǎn)由元素(存儲(chǔ)數(shù)據(jù))和指針(指向后繼節(jié)點(diǎn))組成。

單向鏈表（也叫單鏈表）是鏈表中最簡單的一種形式，每個(gè)節(jié)點(diǎn)只包含一個(gè)元素和一個(gè)指針。
它有一個(gè)表頭，并且除了最后一個(gè)節(jié)點(diǎn)外，所有節(jié)點(diǎn)都有其后繼節(jié)點(diǎn)。
它的存儲(chǔ)結(jié)構(gòu)如下圖所示

代碼實(shí)現(xiàn)

定義節(jié)點(diǎn)

class Node
{
    public $data;

    /**
     * @var null | Node
     */
    public $next;

    public function __construct($data)
    {
        $this->data = $data;
        $this->next = null;
    }

}

單鏈表實(shí)現(xiàn)

/**
 * Class SingleLinkList
 * 單鏈接的實(shí)現(xiàn)示例，實(shí)現(xiàn)簡單的填加，插入，刪除, 查詢，長度，遍歷這幾個(gè)簡單操作
 */
class SingleLinkList
{
    /**
     * 鏈表頭結(jié)點(diǎn)，頭節(jié)點(diǎn)必須存在，
     * @var Node
     */
    public $header;

    private $size = 0;

    /**
     * 構(gòu)造函數(shù)，默認(rèn)填加一個(gè)哨兵節(jié)點(diǎn)，該節(jié)點(diǎn)元素為空
     * SingleLinkList constructor.
     */
    public function __construct()
    {
        $this->header = new Node(null);
    }

    /**
     * 在鏈表末尾添加節(jié)點(diǎn)
     * @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;
    }

    /**
     * 在指定位置插入節(jié)點(diǎn)
     * @param int $index 節(jié)點(diǎn)位置，從1開始計(jì)數(shù)
     * @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;
    }

    /**
     * 刪除節(jié)點(diǎn)
     * @param int $index 節(jié)點(diǎn)位置，從1開始計(jì)數(shù)
     * @return int
     * @throws Exception
     */
    public function deleteNodeByIndex($index)
    {
        if ($index < 1 || $index > ($this->size + 1)) {
            throw new Exception("你刪除的節(jié)點(diǎn)不存在");
        }

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

    /**
     * 查詢節(jié)點(diǎn)
     * @param int $index 節(jié)點(diǎn)位置，從1開始計(jì)數(shù)
     * @return Node|null
     * @throws Exception
     */
    public function searchNodeByIndex($index) {
        if ($index < 1 || $index > ($this->size + 1)) {
            throw new Exception("你查詢的節(jié)點(diǎn)不存在");
        }

        $current = $this->header;
        $tempIndex = 1;
        do {
            if ($index == $tempIndex++) {
                return $current->next;
            }
        } while ($current->next != null && ($current = $current->next));
    }

    /**
     * 獲取節(jié)點(diǎn)長度
     * @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();