Односвязный список на основе фактической структуры данных PHP

задняя часть PHP GitHub JavaScript

Что такое список?

Связанный список состоит из объектов, которые являются узлами один за другим, каждый узел имеет указатель на следующий узел, а по области указателя последнего узла указывает на NULL. Каждый узел может хранить любой тип данных.

Общие операции

Наши общие операции над односвязными списками следующие:

  • insert
  • insertBefore
  • insertAfter
  • insertAtFirst
  • search
  • deleteFirst
  • deleteLast
  • delete
  • reverse
  • getNthNode
  • ...

Реализация языка PHP

Сначала мы реализуем класс ListNode по определению.

class ListNode
{
    private $data;
    private $next;

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

    public function __get($var)
    {
        return $this->$var;
    }

    public function __set($var, $val)
    {
        return $this->$var = $val;
    }
}

Глядя на класс связанного списка, нам сначала нужны два частных атрибута, а именно головной узел и длина.

class LinkedList
{
    private $head;
    private $length;
}

Давайте вкратце рассмотрим, как реализовать первую, обычно используемую вставку, которая является операцией со средней временной сложностью O(n).

/**
 * 插入一个节点
 * @param string|null $data
 * @return bool
 * complexity O(n)
 */
public function insert(string $data = null)
{
    $newNode = new ListNode($data);

    if ($this->head === null) {
        $this->head = &$newNode;
    } else {
        $currentNode = $this->head;
        while ($currentNode->next !== null) {
            $currentNode = $currentNode->next;
        }

        $currentNode->next = $newNode;
    }

    $this->length++;
    return true;
}

Посмотрите на поиск, это тоже операция средней временной сложности O(N).

/**
 * 搜索一个节点
 * @param string $data
 * @return bool|ListNode
 * complexity O(n)
 */
public function search(string $data)
{
    if ($this->length > 0) {
        $currentNode = $this->head;
        while ($currentNode !== null) {
            if ($currentNode->data === $data) {
                return $currentNode;
            }

            $currentNode = $currentNode->next;
        }
    }

    return false;
}

обратный односвязный список

public function reverse()
{
    if ($this->head !== null) {
        if ($this->head->next !== null) {
            $reveredList = null;
            $next = null;
            $currentNode = $this->head;

            while ($currentNode !== null) {
                $next = $currentNode->next;
                $currentNode->next = $reveredList;
                $reveredList = $currentNode;
                $currentNode = $next;
            }

            $this->head = $reveredList;
        }
    }

}

Подробное описание других операций в односвязном списке см.здесь.

Односвязный список является основной частью связанной структуры данных доступа связанного списка.К структуре связанного списка также относятся двусвязный список, кольцевой связанный список и многосвязный список.

Ряд

Адрес каталога серии тем по базовой структуре данных PHP:github.com/...Он в основном использует синтаксис PHP для обобщения основных структур данных и алгоритмов. Есть также базовые знания, которые легко игнорировать в нашей повседневной разработке PHP, и некоторые практические предложения по спецификации, развертыванию и оптимизации в современной разработке PHP, а также углубленное исследование характеристик языка Javascript.

Категории