PHP data structure basics double linked list

This article mainly introduces the double-linked list, the basis of PHP data structure, which has certain reference value. Now I share it with you. Friends in need can refer to it

What is a double-linked list?

The previous article on the basics of practical PHP data structure - singly linked list

Singly linked list is composed of objects that are nodes one by one. Each node has a pointer to the next node. The pointer field of the last node points to null. Each node can store any data type.

Each node of the double linked list has two pointer fields, pointing to the predecessor and successor nodes respectively. A singly linked list is one-way, while a doubly linked list is two-way.

Common operations

Our common operations on double linked lists are as follows:

• insert

• insertBefore

• insertAfter

• insertAtFirst

• insertAtLast

• deleteFirst

• deleteLast

• delete

• reverse

• getNthNode

• ...

PHP language implementation

First we implement a ListNode of a doubly linked list according to the definition kind.

class ListNode
{
    public $data = null;
    public $next = null;
    public $prev = null;

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

Looking at the linked list class, we first need three private attributes, namely the head node, tail node and length.

class DoubleLinkedList
{
    private $head = null;
    private $last = null;
    private $length = 0;
}

The next step is to stick to the old rules and look directly at how to implement the first, commonly used insertion. This is an operation with an average time complexity of O(n).

/**
 * 插入一个节点
 * @param string|null $data
 * @return bool
 * complexity O(n)
 */
public function insert(string $data = null)
{
    $newNode = new ListNode($data);
    if ($this->head) {
        $currentNode = $this->head;
        while ($currentNode) {
            if ($currentNode->next === null) {
                $currentNode->next = $newNode;
                $newNode->prev = $currentNode;
                $this->last = $newNode;
                $this->length++;
                return true;
            }

            $currentNode = $currentNode->next;
        }
    } else {
        $this->head = &$newNode;
        $this->last = $newNode;
        $this->length++;
        return true;
    }

}

Let’s look at how to delete nodes.

/**
 * 删除一个节点
 * @param string $data
 * @return bool|ListNode
 * complexity O(n)
 */
public function delete(string $query = null)
{
if ($this->head) {
    $currentNode = $this->head;
    $prevNode = null;

    while ($currentNode) {
        if ($currentNode->data === $query) {
            if ($nextNode = $currentNode->next) {
                if ($prevNode) {
                    $prevNode->next = $nextNode;
                    $nextNode->prev = $prevNode;
                } else {
                    $this->head = $nextNode;
                    $nextNode->prev = null;
                }

                unset($currentNode);
            } else {
                if ($prevNode) {
                    $this->last = $prevNode;
                    $prevNode->next = null;
                    unset($currentNode);
                } else {
                    $this->head = null;
                    $this->last = null;
                }
            }

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

        $prevNode = $currentNode;
        $currentNode = $currentNode->next;
    }
}

    return false;
}

Reversing a double linked list is not very complicated either.

public function reverse()
{
    if ($this->head !== null) {

        if ($this->head->next !== null) {
            $reversedList = null;
            $currentNode = $this->head;

            while ($currentNode !== null) {
                $next = $currentNode->next;
                $currentNode->next = $reversedList;
                $currentNode->prev = $next;

                $reversedList = $currentNode;
                $currentNode = $next;

            }

            $this->last = $this->head;
            $this->head = $reversedList;
        }
    }
}

For detailed implementation of other operations on double linked lists, please refer here.

Double linked list is a special part of the linked list access data structure compared to single linked list. Also belonging to the linked list structure are single linked list, circular linked list and multi-linked list.

Special Series

PHP basic data structure special series directory address: https://github.com/... Mainly uses PHP syntax to summarize basic data structures and algorithms. There are also basic knowledge that is easily overlooked in our daily PHP development and some practical suggestions on standardization, deployment, and optimization in modern PHP development. There is also an in-depth study of the characteristics of the Javascript language.

The above is the entire content of this article. I hope it will be helpful to everyone's study. For more related content, please pay attention to the PHP Chinese website!

Related recommendations:

PHP data structure basic stack

Notes on php-fpm parameter configuration of php7

The above is the detailed content of PHP data structure basics double linked list. For more information, please follow other related articles on the PHP Chinese website!