实战PHP数据结构基础之双链表

Michael_Lin 发布于2019-07-01 10:07 / 3177人阅读

摘要：什么是双链表上一篇实战数据结构基础之单链表说到单链表由一个一个的作为节点的对象构成的，每一个节点都有指向下一个节点的指针，最后一个节点的指针域指向空。

什么是双链表？

上一篇实战PHP数据结构基础之单链表说到

单链表由一个一个的作为节点的对象构成的，每一个节点都有指向下一个节点的指针，最后一个节点的指针域指向空。每个节点可以存储任何数据类型。

而双链表每个节点有两个指针域，分别指向前驱和后继节点。单链表是单向的，而双链表是双向的。

常见操作

对双链表我们常见的操作有如下：

insert

insertBefore

insertAfter

insertAtFirst

insertAtLast

deleteFirst

deleteLast

delete

reverse

getNthNode

...

PHP语言实现

首先我们根据定义实现一个双链表的ListNode类。

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

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

再来看链表类，首先需要3个私有属性，分别是头节点、尾巴节点和长度。

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

接下来还是老规矩，直接看如何实现第一个即常用的插入，这是是一个平均时间复杂度为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;
    }

}

再来看如何删除节点。

/**
 * 删除一个节点
 * @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;
}

反转双链表也不是很复杂。

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;
        }
    }
}

双链表其他操作的详细实现可以参考这里。

双链表是链表这种链式存取数据结构中相对于单链表比较特殊的部分，同样属于链表结构的还有单链表，环形链表和多链表。

专题系列

PHP基础数据结构专题系列目录地址：https://github.com/... 主要使用PHP语法总结基础的数据结构和算法。还有我们日常PHP开发中容易忽略的基础知识和现代PHP开发中关于规范、部署、优化的一些实战性建议，同时还有对Javascript语言特点的深入研究。

云服务器 GPU云服务器双链表之基础篇黑客基础之DOS 零基础课程之c语言

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/28817.html

PHPer也刷《剑指Offer》之链表

摘要：剑指中链表相关题目俗话说光说不练假把式，既然学习了链表的基础概念和基本操作那我们一定要找些题目巩固下，下面来看剑指中的相关题目。题目分析合并两个排序的链表，需要分别比较两个链表的每个值，然后改变指针。温故知新链表由一个一个的作为节点的对象构成的，每一个节点都有指向下一个节点的指针，最后一个节点的指针域指向空。每个节点可以存储任何数据类型。根据类型可以分为单链表、双链表、环形链表、...

daydream 2019-07-01 10:11 评论0 收藏0
实战PHP数据结构基础之单链表

摘要：常见操作对单链表我们常见的操作有如下语言实现首先我们根据定义实现一个类。单链表是链表这种链式存取数据结构中基础的部分，同样属于链表结构的还有双链表，环形链表和多链表。专题系列基础数据结构专题系列目录地址主要使用语法总结基础的数据结构和算法。什么是链表？链表由一个一个的作为节点的对象构成的，每一个节点都有指向下一个节点的指针，最后一个节点的指针域指向空。每个节点可以存储任何数据类型。...

xumenger 2019-07-01 10:06 评论0 收藏0
实战PHP数据结构基础之栈

摘要：栈和队列栈和队列和之前讲到的实战数据结构基础之双链表一样都是线性结构。来看基于数组的栈实现得益于强大的结构，我们轻而易举的写出来了栈的基本操作方法。专题系列基础数据结构专题系列目录地址主要使用语法总结基础的数据结构和算法。栈和队列栈和队列和之前讲到的实战PHP数据结构基础之双链表一样都是线性结构。栈有什么特点栈遵循后进先出的原则(LIFO)。这意味着栈只有一个出口用来压入元素...

banana_pi 2019-07-01 10:08 评论0 收藏0
[个人心得]数据结构之双链表

摘要：一般我们都构造双向循环链表。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。单向循环链表双向循环链表单向循环链表是在单链表基础上，将最后一个节点的指针指向链表头。维基百科双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构...

jokester 2019-08-21 17:54 评论0 收藏0