鍊錶

鍊錶（Linked list）是一種常見的基礎資料結構，是一種線性表，但是並不會以線性的順序儲存數據，而是在每一個節點裡存到下一個節點的指標(Pointer)。

使用鍊錶結構可以克服陣列鍊錶需要預先知道資料大小的缺點，鍊錶結構可以充分利用電腦記憶體空間，實現靈活的記憶體動態管理。但是鍊錶失去了數組隨機讀取的優點，同時鍊錶由於增加了結點的指標域，空間開銷比較大。

鍊錶有很多種不同的類型：單向鍊錶，雙向鍊錶以及循環鍊錶。

單向鍊錶

鍊錶中最簡單的一種是單向鍊錶，它包含兩個域，一個資訊域和一個指標域。這個連結指向列表中的下一個節點，而最後一個節點則指向一個空值。

PHP實作簡單的單向鍊錶

<?php class Node
{
    private $Data;//节点数据
    private $Next;//存储下个点对象

    public function __construct($data, $next)
    {        $this->Data = $data;        $this->Next = $next;
    }

    public function __set($name, $value)
    {        if (isset($this->$name))            $this->$name = $value;
    }

    public function __get($name)
    {        if (isset($this->$name))            return $this->$name;        else
            return NULL;
    }
}

class LinkList
{
    private $head;//头节点
    private $len;

    /**
     * 初始化头节点
     */
    public function __construct()
    {        $this->init();
    }

    public function setHead(Node $val)
    {        $this->head = $val;
    }

    public function getHead()
    {        return $this->head;
    }

    public function getLen()
    {        return $this->len;
    }

    public function init()
    {        $this->setHead(new Node(NULL, NULL));        $this->len = 0;
    }

    /**
     * 设置某位置节点的数据
     * @param int $index
     * @param $data
     * @return bool
     */
    public function set(int $index, $data)
    {        $i = 1;        $node = $this->getHead();        while ($node->Next !== NULL && $i Next;            $i++;
        }        $node->Data = $data;        return TRUE;
    }

    /**
     * 获取某位置节点的数据
     * @param int $index
     * @return mixed
     */
    public function get(int $index)
    {        $i = 1;        $node = $this->getHead();        while ($node->Next !== NULL && $i Next;            $i++;
        }        return $node->Data;
    }

    /**
     * 在某位置处插入节点
     * @param $data
     * @param int $index
     * @return bool
     */
    public function insert($data, int $index = 0)
    {        if ($index  $this->getLen())            return FALSE;        $i = 1;        $node = $this->getHead();        while ($node->Next !== NULL) {            if ($index === $i) break;            $node = $node->Next;            $i++;
        }        $node->Next = new Node($data, $node->Next);        $this->len++;        return TRUE;
    }

    /**
     * 删除某位置的节点
     * @param int $index
     * @return bool
     */
    public function delete(int $index)
    {        if ($index  $this->getLen())            return FALSE;        $i = 1;        $node = $this->getHead();        while ($node->Next !== NULL) {            if ($index === $i) break;            $node = $node->Next;            $i++;
        }        $node->Next = $node->Next->Next;        $this->len--;        return TRUE;
    }
}

雙向鍊錶一種更複雜的鍊錶是「雙向鍊錶」或「雙面鍊錶」。每個節點有兩個連接：一個指向前一個節點，（當此「連接」為第一個「連接」時，指向空值或空列表）；而另一個指向下一個節點，（當此「連接」為最後一個「連接」時，指向空值或空列表）

#循環鍊錶在一個循環鍊錶中,首節點和末節點被連接在一起。這種方式在單向和雙向鍊錶中皆可實現。要轉換一個循環鍊錶，你開始於任一個節點然後沿著列表的任一方向直到返回開始的節點。再來看另一種方法，循環鍊錶可以被視為「無頭無尾」。這種列表很利於節約資料儲存緩存，假定你在一個列表中有一個物件並且希望所有其他物件迭代在一個非特殊的排列下。指向整個清單的指標可以被稱為存取指標。