当前位置：首页 > PHP

php实现链表

2026-02-27 21:30:56PHP

PHP 实现链表的基本方法

链表是一种线性数据结构，由节点组成，每个节点包含数据和指向下一个节点的指针。PHP 中可以通过类来实现链表结构。

定义链表节点类

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

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

实现链表类

class LinkedList {
    private $head = null;

    // 插入节点到链表末尾
    public function insert($data) {
        $newNode = new ListNode($data);
        if ($this->head === null) {
            $this->head = $newNode;
        } else {
            $current = $this->head;
            while ($current->next !== null) {
                $current = $current->next;
            }
            $current->next = $newNode;
        }
    }

    // 删除指定数据的节点
    public function delete($data) {
        if ($this->head === null) {
            return;
        }

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

        $current = $this->head;
        while ($current->next !== null) {
            if ($current->next->data === $data) {
                $current->next = $current->next->next;
                return;
            }
            $current = $current->next;
        }
    }

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

    // 打印链表
    public function display() {
        $current = $this->head;
        while ($current !== null) {
            echo $current->data . " ";
            $current = $current->next;
        }
        echo "\n";
    }
}

使用链表

$list = new LinkedList();
$list->insert(10);
$list->insert(20);
$list->insert(30);
$list->display(); // 输出: 10 20 30

$list->delete(20);
$list->display(); // 输出: 10 30

$node = $list->search(30);
if ($node !== null) {
    echo "Found: " . $node->data . "\n"; // 输出: Found: 30
}

实现双向链表

双向链表节点包含指向前一个和后一个节点的指针：

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

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

class DoublyLinkedList {
    private $head = null;
    private $tail = null;

    // 插入节点到末尾
    public function insert($data) {
        $newNode = new DoublyListNode($data);
        if ($this->head === null) {
            $this->head = $newNode;
            $this->tail = $newNode;
        } else {
            $newNode->prev = $this->tail;
            $this->tail->next = $newNode;
            $this->tail = $newNode;
        }
    }

    // 其他方法类似，需要处理prev指针
}