связанный список

Связный список — это общая базовая структура данных, это линейный список, но он хранит данные не в линейном порядке, а хранит указатель (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 <= $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;
    }
}

Двусвязный списокБолее сложным типом связанного списка является «двусторонний связанный список» или «двусторонний связанный список». Каждый узел имеет два соединения: одно указывает на предыдущий узел (когда это «соединение» является первым «соединением», оно указывает на нулевое значение или пустой список); а другое указывает на следующий узел (когда это «соединение» — это первое «соединение» — это последнее «соединение», указывающее на нулевое значение или пустой список)

Круговой связанный списокВ круговом связанном списке первый узел и последний узел связаны вместе. Этот метод может быть реализован как в односвязных, так и в двусвязных списках. Чтобы преобразовать круговой связанный список, вы начинаете с любого узла и двигаетесь в любом направлении по списку, пока не вернетесь к начальному узлу. Глядя на другой подход, круговой связанный список можно рассматривать как «безголовый и бесхвостый». Такие списки отлично подходят для сохранения кешей хранилища данных, если у вас есть объект в списке и вы хотите, чтобы все остальные объекты перебирали неспециальную перестановку. Указатель на весь список можно назвать указателем доступа.

Основные идеи почти пора продолжать обновлять