当前位置：首页 > PHP

php实现链表

2026-01-29 00:27:31PHP

链表的基本概念

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表在内存中是非连续存储的，动态增删节点更高效。

单链表实现

PHP中可以通过类实现单链表。节点类包含数据（data）和指向下一个节点的指针（next），链表类提供插入、删除等操作方法。

class ListNode {
    public $data;
    public $next;

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

class LinkedList {
    public $head;

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

    // 在链表头部插入节点
    public function insertAtHead($data) {
        $newNode = new ListNode($data);
        $newNode->next = $this->head;
        $this->head = $newNode;
    }

    // 在链表尾部插入节点
    public function insertAtTail($data) {
        $newNode = new ListNode($data);
        if ($this->head === null) {
            $this->head = $newNode;
            return;
        }
        $current = $this->head;
        while ($current->next !== null) {
            $current = $current->next;
        }
        $current->next = $newNode;
    }

    // 删除指定值的节点
    public function deleteNode($data) {
        if ($this->head === null) return;
        if ($this->head->data === $data) {
            $this->head = $this->head->next;
            return;
        }
        $current = $this->head;
        while ($current->next !== null && $current->next->data !== $data) {
            $current = $current->next;
        }
        if ($current->next !== null) {
            $current->next = $current->next->next;
        }
    }

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

// 使用示例
$list = new LinkedList();
$list->insertAtHead(3);
$list->insertAtHead(2);
$list->insertAtHead(1);
$list->insertAtTail(4);
$list->printList(); // 输出: 1 -> 2 -> 3 -> 4 -> NULL
$list->deleteNode(2);
$list->printList(); // 输出: 1 -> 3 -> 4 -> NULL

双向链表实现

双向链表的节点包含指向前驱和后继的指针，支持双向遍历。实现时需额外维护prev指针。

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

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

class DoublyLinkedList {
    public $head;

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

    // 在尾部插入节点
    public function insertAtTail($data) {
        $newNode = new DoublyListNode($data);
        if ($this->head === null) {
            $this->head = $newNode;
            return;
        }
        $current = $this->head;
        while ($current->next !== null) {
            $current = $current->next;
        }
        $current->next = $newNode;
        $newNode->prev = $current;
    }

    // 打印链表（正向）
    public function printForward() {
        $current = $this->head;
        while ($current !== null) {
            echo $current->data . " <-> ";
            $current = $current->next;
        }
        echo "NULL\n";
    }
}

// 使用示例
$dll = new DoublyLinkedList();
$dll->insertAtTail(1);
$dll->insertAtTail(2);
$dll->printForward(); // 输出: 1 <-> 2 <-> NULL