php如何实现链表

实现链表的基本结构

在PHP中，链表可以通过类和对象来实现。每个节点是一个对象，包含数据和指向下一个节点的引用。

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 "\n";
    }
}

使用链表

创建链表实例并执行插入、删除和遍历操作。

$list = new LinkedList();
$list->insertAtHead(1);
$list->insertAtTail(2);
$list->insertAtTail(3);
$list->printList(); // 输出: 1 2 3

$list->deleteNode(2);
$list->printList(); // 输出: 1 3

实现双向链表

双向链表的每个节点包含指向前一个和后一个节点的引用。

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

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

class DoublyLinkedList {
    public $head;
    public $tail;

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

    // 在头部插入节点
    public function insertAtHead($data) {
        $newNode = new DoublyListNode($data);
        if ($this->head === null) {
            $this->head = $newNode;
            $this->tail = $newNode;
            return;
        }
        $newNode->next = $this->head;
        $this->head->prev = $newNode;
        $this->head = $newNode;
    }

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

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

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

使用双向链表

创建双向链表实例并执行插入、删除和遍历操作。

$dlist = new DoublyLinkedList();
$dlist->insertAtHead(1);
$dlist->insertAtTail(2);
$dlist->insertAtTail(3);
$dlist->printList(); // 输出: 1 2 3

$dlist->deleteNode(2);
$dlist->printList(); // 输出: 1 3