浅谈PHP链表数据结构(单链表)

介绍

链表是一种常见的数据结构，它包括单链表和双链表，本文中我们将会介绍PHP的单链表数据结构实现，具体而言我们将会实现一个包括插入节点，删除节点，打印节点等基本操作的单链表，帮助读者深入理解PHP链表数据结构。

创建节点

链表数据结构是由一个个节点组成的，我们首先要实现一个节点的创建函数，这个函数接受两个参数，一个是节点数据，另一个是下一个节点的指针地址。

/**
 * 定义节点类
 */
class ListNode {
    /**
     * 节点数据
     * @var mixed
     */
    public $val;

    /**
     * 下一个节点指针
     * @var ListNode
     */
    public $next;

    /**
     * 构造函数
     */
    public function __construct($val=0, $next=null) {
        $this->val = $val;
        $this->next = $next;
    }
}

插入节点

链表的插入操作分为在链表头插入和在链表尾插入两种情况。

在链表头插入节点

在链表头插入节点是在链表头部创建一个新的节点，然后将新节点的指针指向旧的头节点。实现这个功能时，我们需要维护一个头节点指针，这样才能在链表头插入数据。

下面是在链表头插入节点的代码示例：

/**
 * 在链表头插入数据
 * @param mixed $val 插入的数据
 */
public function addAtHead($val) {
    $node = new ListNode($val);
    $node->next = $this->head;
    $this->head = $node;
}

在链表尾插入节点

在链表尾部插入节点是一种比较常见的情况，我们需要将新节点的指针指向链表尾节点，然后将尾节点的指针指向新节点。为了实现尾插法，我们需要维护一个尾节点指针。

下面是在链表尾插入节点的代码示例：

/**
 * 在链表尾插入数据
 * @param mixed $val 插入的数据
 */
public function addAtTail($val) {
    $node = new ListNode($val);
    $node->next = null;

    if ($this->head == null) {
        $this->head = $node;
        return;
    }

    $pointer = $this->head;
    while ($pointer->next != null) {
        $pointer = $pointer->next;
    }

    $pointer->next = $node;
}

遍历链表

遍历链表是一种常见的操作，我们需要将头节点指针传递给一个临时指针变量，然后不断移动指针，直到指针为null。

下面是遍历链表的代码示例：

/**
 * 遍历链表
 */
public function printList() {
    $pointer = $this->head;
    while ($pointer != null) {
        echo $pointer->val . " -> ";
        $pointer = $pointer->next;
    }

    echo "NULL\n";
}

删除节点

链表中的删除节点操作有两种情况：

删除指定节点

删除指定节点是在链表中删除某个节点，我们需要将要删除节点的前一个节点的指针指向要删除节点的后一个节点。

/**
 * 删除指定节点
 * @param mixed $val 要删除节点的数据
 */
public function deleteNode($val) {
    $temp = new ListNode(0);
    $temp->next = $this->head;

    $pointer = $temp;
    while ($pointer->next != null) {
        if ($pointer->next->val == $val) {
            $pointer->next = $pointer->next->next;
            break;
        }

        $pointer = $pointer->next;
    }

    $this->head = $temp->next;
}

删除第N个节点

删除链表中第N个节点是一个比较复杂的操作，需要我们维护前一个节点的指针。在实现这个操作时，我们需要先遍历链表，获取第N个节点前一个节点的指针，然后将这个指针指向第N个节点的下一个节点。

下面是删除链表中第N个节点的代码示例：

/**
 * 删除链表中第N个节点
 * @param int $n 删除的节点下标
 */
public function deleteAtIndex($n) {
    $temp = new ListNode(0);
    $temp->next = $this->head;

    $pointer = $temp;
    for ($i = 0; $i < $n; $i++) {
        $pointer = $pointer->next;
    }

    $pointer->next = $pointer->next->next;
    $this->head = $temp->next;
}

示例说明

下面为您提供两个实例，帮助您更好的理解链表相关操作的实现。

示例一：打印链表

$list = new LinkedList();
$list->addAtHead(3);
$list->addAtHead(5);
$list->addAtTail(8);
$list->printList();

上面的代码将会输出：5 -> 3 -> 8 -> NULL

示例二：删除链表中第2个节点

$list = new LinkedList();
$list->addAtHead(3);
$list->addAtHead(5);
$list->addAtTail(8);
$list->deleteAtIndex(1);
$list->printList();

上面的代码将会输出：5 -> 8 -> NULL