双向链表.md

双向链表

单向链表无法查找前面的结点, 在双向链表中, 每个结点有两个指针, 一个指向后继结点, 一个指向前驱结点.

目录

• 知识准备
• 代码实现

知识准备

• 数据结构的概念和分类

代码实现

class Node
{
    public $data;
    // 前驱指针
    public $prev = NULL;
    // 后继指针
    public $next = NULL;

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

class DoubleLinkedList
{
    private $head;

    // 判断链表是否为空
    public function isEmpty()
    {
        return is_null($this->head);
    }

    // 获取链表长度
    public function length()
    {
        $length = 0;
        $currNode = $this->head;
        while ($currNode != NULL) {
            $length++;
            $currNode = $currNode->next;
        }

        return $length;
    }

    // 遍历打印
    public function display()
    {
        $currNode = $this->head;
        while (!is_null($currNode)) {
            echo $currNode->data . ' ';
            $currNode = $currNode->next;
        }
    }

    // 头部插入元素
    public function add($data)
    {
        $node = new Node($data);

        if ($this->isEmpty()) {
            $this->head = $node;
        } else {
            // 新插入结点next指向原来的头结点
            $node->next = $this->head;
            // 原来的头结点prev指向新插入结点
            $this->head->prev = $node;
            // 头结点指向新插入结点
            $this->head = $node;
        }
    }

    // 尾部插入元素
    public function append($data)
    {
        $node = new Node($data);

        if ($this->isEmpty()) {
            $this->head = $node;
        } else {
            // 移动到尾结点
            $currNode = $this->head;
            while ($currNode->next != NULL) {
                $currNode = $currNode->next;
            }

            // 原来的尾结点指向新插入结点
            $currNode->next = $node;
            // 新插入结点prev指向原来的尾结点
            $node->prev = $currNode;
        }
    }

    // 指定位置插入元素
    public function insert($offset, $data)
    {
        // 头部插入元素
        if ($offset <= 0) {
            $this->add($data);
        }
        // 尾部插入元素
        else if($offset > $this->length() - 1) {
            $this->append($data);
        }
        // 指定位置插入
        else {
            $node = new Node($data);
            $currNode = $this->head;
            $count = 0;

            // 移动到指定位置的前一个结点
            while ($count != ($offset - 1)) {
                $currNode = $currNode->next;
                $count++;
            }

            $node->prev = $currNode;
            $node->next = $currNode->next;
            $currNode->next->prev = $node;
            $currNode->next = $node;
        }
    }

    // 删除元素
    public function delete($data)
    {
        if ($this->head == NULL) {
            throw new Exception('LinkedList is NULL');
        }

        $currNode = $this->head;

        // 头结点
        if ($currNode->data == $data) {
            // 只有头结点
            if (is_null($currNode->next)) {
                $this->head = NULL;
            } else {
                $currNode->next->prev = NULL;
                $this->head = $currNode->next;
            }
        } else {
            while (!is_null($currNode)) {
                if ($currNode->data == $data) {
                    $currNode->prev->next = $currNode->next;
                    // 判断是否是最后一个结点
                    if ($currNode->next != NULL) {
                        $currNode->next->prev = $currNode->prev;
                    }
                    break;
                }
                $currNode = $currNode->next;
            }
        }
    }

    // 查找元素
    public function find($data)
    {
        if (!$this->isEmpty()) {
            $currNode = $this->head;

            while ($currNode != NULL) {
                if ($currNode->data == $data) {
                    echo 'found' . PHP_EOL;
                    return true;
                }

                $currNode = $currNode->next;
            }
        }

        echo 'not found';
        return false;
    }

    // 反转链表
    public function reverse()
    {
        if ($this->head != NULL && $this->head->next != NULL) {
            $reversedList = NULL;
            $currNode = $this->head;

            while ($currNode != NULL) {
                $next = $currNode->next;

                $currNode->next = $reversedList;
                $currNode->prev = $next;

                $reversedList = $currNode;
                $currNode = $next;
            }

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

// Test
$list = new DoubleLinkedList();
$list->append(1);
$list->append(2);
// 1 2
$list->display();
$list->add(0);
// 0 1 2
$list->display();
// 3
echo $list->length();
$list->insert(1, 10);
// 0 10 1 2
$list->display();
$list->delete(10);
// 0 1 2
$list->display();
// not found
$list->find(10);
$list->reverse();
// 2 1 0
$list->display();
$list->delete(1);
// 2 0
$list->display();