php单链表实现代码分享

让我为您详细讲解一下“PHP单链表实现代码分享”的攻略。

什么是单链表

单链表是一种链式存储结构，是由头节点和若干个节点组成的。 每个节点包含两个成员，一个成员是数据，另一个成员是指向下一个节点的指针。一个链表可以看做是一个链式存储的节点的集合，其中每个节点指向下一个节点，直到最后一个节点指针指向NULL。

单链表的实现

实现一个单链表需要维护以下几个操作：

1. 初始化链表：创建一个空链表，头部指针指向NULL。
2. 插入节点：在某个节点后面插入一个新节点。
3. 删除节点：删除指定节点。
4. 查找节点：查找指定节点。

下面是一个PHP实现的单链表代码，您可以参考其中的实现逻辑。

<?php

class Node {
    public $data;   // 节点数据
    public $next;   // 指向下一个节点的指针

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

class LinkedList {
    private $head;  // 链表头指针

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

    // 在指定节点后面插入一个新节点
    public function insertAfter($node, $data) {
        if ($node == null) {
            return false;
        }

        $newNode = new Node($data);
        $newNode->next = $node->next;
        $node->next = $newNode;
    }

    // 删除指定节点
    public function delete($node) {
        if ($node == null || $this->head == null) {
            return false;
        }

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

        $prev = $this->head;
        while ($prev != null && $prev->next != $node) {
            $prev = $prev->next;
        }

        if ($prev == null) {
            return false;
        }

        $prev->next = $node->next;
        return true;
    }

    // 查找节点
    public function search($data) {
        $node = $this->head;
        while ($node != null && $node->data != $data) {
            $node = $node->next;
        }

        return $node;
    }

    // 遍历链表
    public function traverse() {
        $node = $this->head;
        while ($node != null) {
            echo $node->data . " ";
            $node = $node->next;
        }
    }
}

$linkedList = new LinkedList();

// 插入新节点
$node1 = new Node(100);
$linkedList->insertAfter(null, $node1);
$node2 = new Node(200);
$linkedList->insertAfter($node1, $node2);
$node3 = new Node(300);
$linkedList->insertAfter($node2, $node3);

// 遍历链表
$linkedList->traverse();  // 输出: 100 200 300

// 删除节点
$linkedList->delete($node2);
$linkedList->traverse();  // 输出: 100 300

// 查找节点
$node = $linkedList->search(100);
echo $node->data;  // 输出: 100

?>

上面的代码实现了单链表的初始化、插入节点、删除节点、查找节点等操作，您可以根据您的需求进行相应的修改和扩展。

下面提供一些示例，帮助您更好地了解单链表的使用。

示例1：链表实现栈

下面是一个用单链表实现栈的示例，具体实现思路是：链表头指针作为栈顶指针，每次入栈时在链表头插入一个新节点，每次出栈时删除链表头节点即可。

class Stack {
    private $list;

    public function __construct() {
        $this->list = new LinkedList();
    }

    public function push($data) {
        $this->list->insertAfter(null, $data);
    }

    public function pop() {
        $node = $this->list->delete($this->list->head);
        if ($node) {
            return $node->data;
        }
        return null;
    }
}

$stack = new Stack();
$stack->push(100);
$stack->push(200);
$stack->push(300);
echo $stack->pop() . "<br>";   // 输出: 300
echo $stack->pop() . "<br>";   // 输出: 200
echo $stack->pop() . "<br>";   // 输出: 100

示例2：链表实现队列

下面是一个用单链表实现队列的示例，具体实现思路是：链表尾指针作为队尾指针，每次入队时在链表尾部插入一个新节点，每次出队时删除链表头节点即可。

class Queue {
    private $list;

    public function __construct() {
        $this->list = new LinkedList();
    }

    public function enqueue($data) {
        $this->list->insertAfter($this->list->searchLast(), $data);
    }

    public function dequeue() {
        $node = $this->list->delete($this->list->head);
        if ($node) {
            return $node->data;
        }
        return null;
    }
}

$queue = new Queue();
$queue->enqueue(100);
$queue->enqueue(200);
$queue->enqueue(300);
echo $queue->dequeue() . "<br>";    // 输出: 100
echo $queue->dequeue() . "<br>";    // 输出: 200
echo $queue->dequeue() . "<br>";    // 输出: 300

希望以上的讲解和示例能够帮助您更好地理解和使用单链表。