PHP 循环双向链表

 PHP 数据结构

循环双向链表是一种线性数据结构，其中元素以节点的形式存储。每个节点包含三个子元素。数据部分存储元素的值，前一部分存储到前一个节点的链接，下一部分存储到下一个节点的链接，如下图所示:

始终使用第一个节点，也称为 HEAD作为遍历列表的参考。最后一个元素包含指向第一个元素（作为下一个）的链接，第一个元素包含最后一个元素（作为上一个）的链接。双向链接的循环可以可视化为节点链，其中每个节点都指向上一个和下一个节点。

循环双向链表的实现

表示方法:

在PHP中，双向链表可以表示为一个类和一个 Node 作为一个单独的类。 LinkedList 类包含 Node 类类型的引用。

//节点结构
class Node {
  public $data;
  public $next;
  public $prev;
}

class LinkedList {
  public $head; 

  //构造函数创建一个空的LinkedList
  public function __construct(){
    $this->head = null;
  }
}; 

创建一个循环双向链表

让我们创建一个简单的循环双向链表，其中包含三个数据节点。

<?php
//节点结构
class Node {
  public $data;
  public $next;
  public $prev;
}

class LinkedList {
  public $head; 

  //构造函数创建一个空的LinkedList
  public function __construct(){
    $this->head = null;
  } 
};

//测试代码
//创建一个空的链表
$MyList = new LinkedList();

//添加第一个节点。
$first = new Node();
$first->data = 10;
$first->next = null;
$first->prev = null;
//与头节点链接
$MyList->head = $first;
//将节点的下一个与头连接起来
$first->next = $MyList->head;
//链接头部的prev
$MyList->head->prev = $first;

//添加第二个节点。
$second = new Node();
$second->data = 20;
$second->next = null;
//与第一个节点链接
$second->prev = $first;
$first->next = $second;
//将节点的下一个与头连接起来
$second->next = $MyList->head;
//链接头部的prev
$MyList->head->prev = $second;

//添加第三个节点。
$third = new Node();
$third->data = 30;
$third->next = null;
//与第二个节点链接
$third->prev = $second;
$second->next = $third;
//将节点的下一个与头连接起来
$third->next = $MyList->head;
//链接头部的prev
$MyList->head->prev = $third;
?> 

遍历循环双向链表

可以使用临时节点从列表的任何节点遍历循环双向链表。继续将临时节点移动到下一个节点并显示其内容。到达起始节点后停止遍历。

<?php
//节点结构
class Node {
  public $data;
  public $next;
  public $prev;
}

class LinkedList {
  public $head;

  //构造函数创建一个空的LinkedList
  public function __construct(){
    $this->head = null;
  }

  //显示列表内容
  public function PrintList() {
    $temp = new Node();
    $temp = $this->head;
    if($temp != null) {
      echo "The list contains: ";
      while(true) {
        echo $temp->data." ";
        $temp = $temp->next;
        if($temp == $this->head)
          break;        
      }
      echo "\n";
    } else {
      echo "The list is empty.\n";
    }
  }    
};

//测试代码
//创建一个空的链表
$MyList = new LinkedList();

//添加第一个节点。
$first = new Node();
$first->data = 10;
$first->next = null;
$first->prev = null;
//与头节点链接
$MyList->head = $first;
//将节点的下一个与头连接起来
$first->next = $MyList->head;
//链接头部的prev
$MyList->head->prev = $first;

//添加第二个节点。
$second = new Node();
$second->data = 20;
$second->next = null;
//与第一个节点链接
$second->prev = $first;
$first->next = $second;
//将节点的下一个与头连接起来
$second->next = $MyList->head;
//链接头部的prev
$MyList->head->prev = $second;

//添加第三个节点。
$third = new Node();
$third->data = 30;
$third->next = null;
//与第二个节点链接
$third->prev = $second;
$second->next = $third;
//将节点的下一个与头连接起来
$third->next = $MyList->head;
//链接头部的prev
$MyList->head->prev = $third;

//打印列表内容
$MyList->PrintList();   
?> 

上面的代码将给出以下输出:

The list contains: 10 20 30