How to implement php linked list

How to implement PHP linked list: first create a PHP sample file; then initialize the head node; then set the data of a node at a certain position, and insert a node at a certain position; and finally delete the node at a certain position.

Recommendation: "PHP Video Tutorial"

Linked list

Linked list (Linked list) is A common basic data structure is a linear table, but it does not store data in a linear order. Instead, it stores a pointer to the next node in each node.

Using the linked list structure can overcome the shortcoming of the array linked list that the data size needs to be known in advance. The linked list structure can make full use of the computer memory space and achieve flexible dynamic memory management. However, the linked list loses the advantage of random reading of the array, and at the same time, the space overhead of the linked list is relatively large due to the increase of the pointer field of the node.

There are many different types of linked lists: one-way linked lists, doubly linked lists and circular linked lists.

Singly linked list

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

PHP implements a simple one-way linked list

<?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 <= $index) {            $node = $node->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 <= $index) {            $node = $node->Next;            $i++;
        }        return $node->Data;
    }

    /**
     * 在某位置处插入节点
     * @param $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++;        return TRUE;
    }

    /**
     * 删除某位置的节点
     * @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--;        return TRUE;
    }
}

Doubly linked list一A more complex linked list is a "doubly linked list" or "double-sided linked list". Each node has two connections: one points to the previous node (when this "connection" is the first "connection", it points to a null value or an empty list); and the other points to the next node (when this "connection" is the first "connection", it points to a null value or an empty list); "When it is the last "connection", it points to a null value or empty list)

Circular linked listIn a circular linked list ,The first node and the last node are connected together. This method can be implemented in both one-way and two-way linked lists. To convert a circular linked list, you start at any node and follow the list in either direction until you return to the starting node. Looking at another method, a circular linked list can be regarded as "headless and tailless". Such lists are useful for conserving data storage caches, assuming you have one object in a list and want all other objects to be iterated over in a non-specific arrangement. The pointer to the entire list may be called an access pointer.

The basic ideas are almost there and I have time to continue updating

The above is the detailed content of How to implement php linked list. For more information, please follow other related articles on the PHP Chinese website!