php链表结构 双链表（二）

双链表结构，我们这边定义一个节点类，属性有当前值(data)和指向下一个节点的(next)， 和指向上一个节点的（previous）。

class Node {
    //当前节点的值
    public $data;
    //指向的下一个节点
    public $next = NULL;
    //指向的上一个节点
    public $previous = NULL;

    //给节点添加值
    public function __construct(string $data = NULL) {
        $this->data = $data;
    }
}

之后是链表结构类 ，我们定义一个头节点，以头节点开始，next指向下一个节点，previous指向上一个节点，具体看情况添加你所需要的其他属性

class DoubleLinkedLIst {
    //头节点
    public $headNode = NULL;

    //初始双链表的头节点
    public function __construct($data) {
        $this->headNode = new Node($data);
    }
}

1. 往双链表添加节点(是链表的后面添加)

//往双链表的尾部中添加节点
public function insertNode($data) {
    $newNode = new Node($data);
    $currentNode = $this->headNode;
    while ($currentNode->next != NULL) {
        $currentNode = $currentNode->next;
    }
    $currentNode->next = $newNode;
    $newNode->previous = $currentNode;
}
$double_link = new DoubleLinkedLIst(1);
$double_link->insertNode(2);
$double_link->insertNode(3);

结果: 
object(DoubleLinkedLIst)#1 (1) {
  ["headNode"]=>
  object(Node)#2 (3) {
    ["data"]=>
    string(1) "1"
    ["next"]=>
    object(Node)#3 (3) {
      ["data"]=>
      string(1) "2"
      ["next"]=>
      object(Node)#4 (3) {
        ["data"]=>
        string(1) "3"
        ["next"]=>
        NULL
        ["previous"]=>
        *RECURSION*
      }
      ["previous"]=>
      *RECURSION*
    }
    ["previous"]=>
    NULL
  }
}

2. 根据值来查询出链表的当前节点

public function find($data) {
    $currentNode = $this->headNode;
    while ($currentNode != NULL) {
        if ($currentNode->data == $data) {
            return $currentNode;
        }
        $currentNode = $currentNode->next;
    }
    return NULL;
}

3. 往指定的值之前添加节点

public function insertNodeBefore($data, $query) {
    $queryNode = $this->find($query);
    if ($queryNode == NULL) {
        echo "未找到指定节点的位置" . PHP_EOL;
        return false;
    }
    $newNode = new Node($data);
    if ($queryNode->previous == NULL) {
        $newNode->next = $this->headNode;
        $this->headNode = $newNode;
    } else {
        $queryNode->previous->next = $newNode;
        $newNode->previous = $queryNode->previous;
        $newNode->next = $queryNode;
        $queryNode->previous = $newNode;
    }
}
$double_link = new DoubleLinkedLIst(1);
$double_link->insertNode(2);
$double_link->insertNode(3);
$double_link->insertNodeBefore(5, 2);
var_dump($double_link);
结果:
object(DoubleLinkedLIst)#1 (1) {
  ["headNode"]=>
  object(Node)#2 (3) {
    ["data"]=>
    string(1) "1"
    ["next"]=>
    object(Node)#5 (3) {
      ["data"]=>
      string(1) "5"
      ["next"]=>
      object(Node)#3 (3) {
        ["data"]=>
        string(1) "2"
        ["next"]=>
        object(Node)#4 (3) {
          ["data"]=>
          string(1) "3"
          ["next"]=>
          NULL
          ["previous"]=>
          *RECURSION*
        }
        ["previous"]=>
        *RECURSION*
      }
      ["previous"]=>
      *RECURSION*
    }
    ["previous"]=>
    NULL
  }
}

4. 删除指定值的节点

public function display($query) {
    $queryNode = $this->find($query);
    if ($queryNode == NULL) {
        echo "未找到指定节点的位置" . PHP_EOL;
        return false;
    }
    if ($queryNode->previous == NULL) {
        $tempNode = $this->headNode->next;
        $tempNode->previous = NULL;
        $this->headNode = $tempNode;
    } elseif ($queryNode->next == NULL) {
        $queryNode->previous->next = NULL;
    } else {
        $queryNode->previous->next = $queryNode->next;
        $queryNode->next->previous = $queryNode->previous;
    }
}

本次只列出这几种方式，还有其他方式，在此就不一一举例，有兴趣的可以自己搞搞啊。

上一篇：PHP 链表结构之单链表（一）
下一篇：PHP 链表结构之环型链表（三）

author: clown