前面已经介绍了很多关于数组的内容.下面我们来讨论一下链表.在多数语言中,数组是定长的结构,当然就不能动态增长,缩减和移除.出于这些原因,大多数开发者都偏向于使用链表来代替数组.考虑到PHP数组中有额外的字节消耗,而链表的对内存使用的效率很高.下面将介绍PHP中不同类型的链表以及实现.

链表是什么?

链表是节点的集合.每一个节点通过链表相互连接.节点可以存储任何数据结构和内容.

链表有以下操作:

• 链表是否为空
• 遍历所有节点
• 搜索某一节点
• 求链表长度
• 插入新节点
• 移除节点
• 链表的反转

下面描述一种简单的节点,包含节点数据和下一个节点的地址
next:

class ListNode { 
    public $data = NULL; 
    public $next = NULL; 

    public function __construct(string $data = NULL) { 
        $this->data = $data; 
    } 
}

下面看一个 链表 LinkedList 的实现 ,包含insert和display操作

class LinkedList { 
    private $_firstNode = NULL; 
    private $_totalNodes = 0; 

    public function insert(string $data = NULL) { 
       $newNode = new ListNode($data); 

        if ($this->_firstNode === NULL) {           
            $this->_firstNode = &$newNode;             
        } else { 
            $currentNode = $this->_firstNode; 
            while ($currentNode->next !== NULL) { 
                $currentNode = $currentNode->next; 
            } 
            $currentNode->next = $newNode; 
        } 
       $this->_totalNode++; 
        return TRUE; 
    } 

    public function display() { 
      echo "Total book titles: ".$this->_totalNode."\n"; 
        $currentNode = $this->_firstNode; 
        while ($currentNode !== NULL) { 
            echo $currentNode->data . "\n"; 
            $currentNode = $currentNode->next; 
        } 
    } 
} 

$linked_list = new LinkedList();

$linked_list->insert(1);
$linked_list->insert(2);
$linked_list->insert(3);
$linked_list->insert(4);

$linked_list->display();

返回结果:
Total book titles: 4 
1 2 3 4

不同类型的链表

到此我们已经实现了一种最简单的单向链表类 LinkedList 这里还有其他几中链表

• 双向链表
• 环向列表
• 多链表

双向列表

双向链表

环向列表

环向列表

多链表

多链表

链表的插入,删除,查找

前面了解了链表的插入和遍历操作,下面来看一下链表的其他操作

• 在第一个节点处插入
• 节点的搜索
• 在特殊节点前插入
• 在特殊节点后插入
• 删除第一个节点
• 删除最后一个节点
• 搜索和删除一个节点
• 链表的反转
• 获取第N个位置的元素

下面依次讨论

在第一个节点处插入

节点搜索

   public function insertAtFirst(string $data = NULL) { 
        $newNode = new ListNode($data); 
        if ($this->_firstNode === NULL) {             
            $this->_firstNode = &$newNode;             
        } else { 
            $currentFirstNode = $this->_firstNode; 
            $this->_firstNode = &$newNode; 
            $newNode->next = $currentFirstNode;            
        } 
        $this->_totalNode++; 
        return TRUE; 
    } 

在特殊节点前插入

public function insertBefore(string $data = NULL, string $query =NULL)
    {   
        $newNode = new ListNode($data);
        if ($this->_firstNode && $this->_firstNode->data = $query) {
            $newNode->next = $this->_firstNode;
            $this->_firstNode-> &$newNode;
        }

        if ($this->_firstNode !== NULL) {       
            $previous = NULL;
            $currentNode = $this->_firstNode;
            while ($currentNode !== NULL) {
                if ($currentNode->data === $query) {
                    $previous->next = &$newNode;
                    $newNode->next = $currentNode;
                    $this->_totalNode++;
                    break;
                }
                $previous = $currentNode;
                $currentNode = $currentNode->next;
            }
        }
    }

在特定节点后插入

    public function insertAfter(string $data = NULL, string $query =NULL)
    {   
        $newNode = new ListNode($data);
        if ($this->_firstNode !== NULL) {
            $currentNode = $this->_firstNode;
            while ($currentNode !== NULL) {
                if ($currentNode->data === $query) {
                    $newNode->next = $currentNode->next;
                    $currentNode->next = &$newNode;
                    $this->_totalNode++;
                    break;
                }
                $currentNode = $currentNode->next;
            }
        }
    }

链表的反转

    public function reverse() { 
        if ($this->_firstNode !== NULL) { 
            if ($this->_firstNode->next !== NULL) { 
                $reversedList = NULL; 
                $next = NULL; 
                $currentNode = $this->_firstNode; 
                while ($currentNode !== NULL) { 
                    $next = $currentNode->next; 
                    $currentNode->next = $reversedList; 
                    $reversedList = $currentNode; 
                    $currentNode = $next; 
                } 
                $this->_firstNode = $reversedList; 
            } 
        } 
    } 

获取第N个位置的元素

    public function getNthNode(int $n = 0)
    {
        $count = 1;
        if ($this->_firstNode !== NULL) {
            $currentNode = $this->_firstNode;
            while ($currentNode !== NULL) {
                if ($count === $n) {
                    return $currentNode;
                }
                $count++;
                $currentNode = $currentNode->next;
            }
        }
    }

理解链表的算法复杂度

使链表可迭代

上面我们使用 while 遍历链表的每一个节点.那我们可以通过链表本身进行迭代吗?PHP 有非常直观的 Iterator（迭代器） 接口

• Current
• Next
• Key
• Rewind
• Valid

上面的方法可以通过 php 手册查询,不再赘述.下面我们将通过类 LinkedList 来实现上述接口来实现直接进行节点的迭代.为了在迭代的过程中追踪当前节点和当前的位置,类 LinkedList 需要额外的两个属性

private $_currentNode = NULL;  // 当前节点
private $_currentPosition = 0; // 当前位置

下面实现 Iterator（迭代器）的5个方法

    #pragram make implements Iterator
    public function current()
    {
        return $this->_currentNode->data;
    }

    public function next()
    {
        $this->_currentPosition++;
        $this->_currentNode = $this->_currentNode->next;
    }    

    public function key() { 
        return $this->_currentPosition; 
    } 

    public function rewind() { 
        $this->_currentPosition = 0; 
        $this->_currentNode = $this->_firstNode; 
    } 

    public function valid() { 
        return $this->_currentNode !== NULL; 
    } 

哈哈,现在我们有了列表的迭代方法了,意味着我们可以使用 foreach 或者其他过程函数来进行迭代:例如下面:

foreach ($BookTitles as $title) { 
    echo $title . "\n"; 
}

for ($BookTitles->rewind(); $BookTitles->valid(); $BookTitles->next()) { 
    echo $BookTitles->current() . "\n"; 
}

双向列表

后面双向列表和多向列表的内容和算法我觉得不需要在赘述了,有空在写吧

使用 PHP SplDoublyLinkedList

如果我们使用内置的类,我们不需要去实现双向列表.官方手册中清楚的列出了双向列表的接口,这里也不再介绍了,下面就举个例子: