The list

Linked list is a common basic data structure. It is a linear list, but it does not store data in a linear order. Instead, it stores Pointers to the next node in each node.

The linked list structure can overcome the disadvantage that the array linked list needs to know the data size in advance. The linked list structure can make full use of computer memory space and realize flexible memory dynamic management. However, linked lists lose the advantage of random array reading, and because of the increase of node pointer field, linked lists have a large space overhead.

There are many different types of linked lists: unidirectional, bidirectional and circular.

Singly linked list

The simplest type of linked list is a one-way linked list, which contains two fields, an information field and a pointer field. The link points to the next node in the list, and the last node points to a null value.

PHP implements simple one-way linked lists

<? php class Node { private$Data; // Node data private$Next; // Store the next point object publicfunction __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; // The header is private$len; /** * initializes the header node */ publicfunction __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; } /** * Sets the data of a node at a location * @param int$index
     * @param $data
     * @return bool
     */
    public function set(int $index.$data)
    {
        $i = 1;
        $node = $this->getHead();
        while ($node->Next ! == NULL &&$i< =$index) {
            $node = $node->Next;
            $i+ +; }$node->Data = $data;
        returnTRUE; } /** * get data from a node * @param int$index
     * @return mixed
     */
    public function get(int $index)
    {
        $i = 1;
        $node = $this->getHead();
        while ($node->Next ! == NULL &&$i< =$index) {
            $node = $node->Next;
            $i+ +; }return $node->Data; } /** * insert node * @param at some point$data
     * @param int $index
     * @return bool
     */
    public function insert($data, int $index = 0)
    {
        if ($index< = 0 | |$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++;
        returnTRUE; } /** * Delete a node * @param int$index
     * @return bool
     */
    public function delete(int $index)
    {
        if ($index< = 0 | |$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--;
        returnTRUE; }}Copy the code

A more complex type of linked list is a “bidirectional” or “double linked list”. Each node has two connections: one to the previous node (to a null value or an empty list if the connection is the first); And the other points to the next node (null value or empty list if this connection is the last connection).

Circular list In a circular list, the first node and the last node are joined together. This approach can be implemented in both one-way and bidirectional lists. To transform a circular list, you start at any node and follow the list in any direction until you return to the starting node. In another way, circular lists can be thought of as “headless and tailless.” Such lists are great for saving data store caches, assuming you have one object in a list and want all the other objects to iterate over in a non-special arrangement. A pointer to an entire list can be called an access pointer.

We have time to update the basic ideas