双向链表php实现

以下是一个用PHP实现双向链表的代码示例，包含节点类和链表类的基本操作：

双向链表节点类

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

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

双向链表类实现

class DoublyLinkedList {
    private $head;
    private $tail;
    private $length;

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

    // 在链表头部插入节点
    public function prepend($data) {
        $newNode = new ListNode($data);

        if ($this->head === null) {
            $this->head = $newNode;
            $this->tail = $newNode;
        } else {
            $newNode->next = $this->head;
            $this->head->prev = $newNode;
            $this->head = $newNode;
        }

        $this->length++;
    }

    // 在链表尾部插入节点
    public function append($data) {
        $newNode = new ListNode($data);

        if ($this->tail === null) {
            $this->head = $newNode;
            $this->tail = $newNode;
        } else {
            $newNode->prev = $this->tail;
            $this->tail->next = $newNode;
            $this->tail = $newNode;
        }

        $this->length++;
    }

    // 在指定位置插入节点
    public function insertAt($position, $data) {
        if ($position < 0 || $position > $this->length) {
            throw new OutOfBoundsException("Invalid position");
        }

        if ($position === 0) {
            $this->prepend($data);
            return;
        }

        if ($position === $this->length) {
            $this->append($data);
            return;
        }

        $current = $this->head;
        for ($i = 0; $i < $position - 1; $i++) {
            $current = $current->next;
        }

        $newNode = new ListNode($data);
        $newNode->prev = $current;
        $newNode->next = $current->next;
        $current->next->prev = $newNode;
        $current->next = $newNode;

        $this->length++;
    }

    // 删除头部节点
    public function deleteFirst() {
        if ($this->head === null) {
            return null;
        }

        $deletedNode = $this->head;

        if ($this->head->next !== null) {
            $this->head = $this->head->next;
            $this->head->prev = null;
        } else {
            $this->head = null;
            $this->tail = null;
        }

        $this->length--;
        return $deletedNode->data;
    }

    // 删除尾部节点
    public function deleteLast() {
        if ($this->tail === null) {
            return null;
        }

        $deletedNode = $this->tail;

        if ($this->tail->prev !== null) {
            $this->tail = $this->tail->prev;
            $this->tail->next = null;
        } else {
            $this->head = null;
            $this->tail = null;
        }

        $this->length--;
        return $deletedNode->data;
    }

    // 删除指定位置的节点
    public function deleteAt($position) {
        if ($position < 0 || $position >= $this->length) {
            throw new OutOfBoundsException("Invalid position");
        }

        if ($position === 0) {
            return $this->deleteFirst();
        }

        if ($position === $this->length - 1) {
            return $this->deleteLast();
        }

        $current = $this->head;
        for ($i = 0; $i < $position; $i++) {
            $current = $current->next;
        }

        $current->prev->next = $current->next;
        $current->next->prev = $current->prev;

        $this->length--;
        return $current->data;
    }

    // 获取链表长度
    public function getLength() {
        return $this->length;
    }

    // 正向遍历链表
    public function traverseForward() {
        $current = $this->head;
        while ($current !== null) {
            echo $current->data . " ";
            $current = $current->next;
        }
        echo "\n";
    }

    // 反向遍历链表
    public function traverseBackward() {
        $current = $this->tail;
        while ($current !== null) {
            echo $current->data . " ";
            $current = $current->prev;
        }
        echo "\n";
    }
}

使用示例

$list = new DoublyLinkedList();
$list->append(1);
$list->append(2);
$list->append(3);
$list->prepend(0);
$list->insertAt(2, 1.5);

echo "Forward traversal: ";
$list->traverseForward(); // 输出: 0 1 1.5 2 3

echo "Backward traversal: ";
$list->traverseBackward(); // 输出: 3 2 1.5 1 0

$list->deleteAt(2);
echo "After deletion: ";
$list->traverseForward(); // 输出: 0 1 2 3

这个实现包含了双向链表的基本操作，包括在头部/尾部插入节点、在指定位置插入节点、删除节点以及正向/反向遍历链表。