数据结构之单链表

数组需要一块连续的内存空间来存储，对内存的要求比较高。而链表恰恰相反，它并不需要一块连续的内存空间，它通过指针将一组零散的内存块串联起来使用。链表结构五花八门，三种最常见的链表结构，它们分别是：单链表、双向链表和循环链表。本文来看最简单、最常用的单链表。

/**
 * 单链表
 */
class SinglyLinkedList
{

    /**
     * 链表头结点|哨兵节点
     *
     * @var SinglyLinkedListNode
     */
    public $head;

    /**
     * 链表长度
     *
     * @var int
     */
    private $length;

    /**
     * 初始化
     *
     * @param null $head            
     */
    public function __construct($head = null)
    {
        $this->head = $head === null ? (new SinglyLinkedListNode()) : $head;
        $this->length = 0;
    }

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

    /**
     * 插入|头插法
     *
     * @param mixed $data            
     * @return SinglyLinkedListNode
     */
    public function insert($data)
    {
        return $this->insertDataAfter($this->head, $data);
    }

    /**
     * 删除节点
     *
     * @param SinglyLinkedListNode $node            
     * @return bool
     */
    public function delete(SinglyLinkedListNode $node)
    {
        if ($node === null) {
            return false;
        }
        $prev_node = $this->getPrevNode($node);
        $prev_node->next = $node->next;
        unset($node);
        $this->length --;
        return true;
    }

    /**
     * 获取前置节点
     *
     * @param SinglyLinkedListNode $node            
     * @return SinglyLinkedListNode|null
     */
    public function getPrevNode(SinglyLinkedListNode $node)
    {
        if ($node === null) {
            return null;
        }
        $curr = $this->head;
        $prev = $this->head;
        while ($curr !== $node && $curr !== null) {
            $prev = $curr;
            $curr = $curr->next;
        }
        return $prev;
    }

    /**
     * 通过索引获取节点
     *
     * @param int $index            
     * @return SinglyLinkedListNode|null
     */
    public function getNodeByIndex($index)
    {
        if ($index >= $this->length) {
            return null;
        }
        $curr = $this->head->next;
        for ($i = 0; $i < $index; $i ++) {
            $curr = $curr->next;
        }
        return $curr;
    }

    /**
     * 在指定节点后插入新节点
     *
     * @param SinglyLinkedListNode $origin_node            
     * @param SinglyLinkedListNode $node            
     * @return SinglyLinkedListNode|null
     */
    public function insertNodeAfter(SinglyLinkedListNode $origin_node, SinglyLinkedListNode $node)
    {
        if ($origin_node === null || $node === null) {
            return null;
        }
        $node->next = $origin_node->next;
        $origin_node->next = $node;
        $this->length ++;
        return $node;
    }

    /**
     * 在指定节点后插入新节点（插入数据）
     *
     * @param SinglyLinkedListNode $origin_node            
     * @param mixed $data            
     * @return SinglyLinkedListNode|null
     */
    public function insertDataAfter(SinglyLinkedListNode $origin_node, $data)
    {
        if ($origin_node === null) {
            return null;
        }
        $node = new SinglyLinkedListNode();
        $node->data = $data;
        $node->next = $origin_node->next;
        $origin_node->next = $node;
        $this->length ++;
        return $node;
    }

    /**
     * 打印链表
     *
     * @return null
     */
    public function print()
    {
        if ($this->head->next === null) {
            return;
        }
        $curr = $this->head;
        $length = $this->length;
        while ($curr->next !== null && $length --) {
            // 假设data均为可输出字符串格式
            echo $curr->next->data . ' -> ';
            $curr = $curr->next;
        }
        echo 'NULL', PHP_EOL;
    }
}

/**
 * 单链表节点
 */
class SinglyLinkedListNode
{

    /**
     * 节点的数据域
     *
     * @var mixed
     */
    public $data;

    /**
     * 节点的指针域|指向下一个节点
     *
     * @var SinglyLinkedListNode
     */
    public $next;

    /**
     * 构造函数
     */
    public function __construct($data = null)
    {
        $this->data = $data;
        $this->next = null;
    }
}

// 【调用示例】
$linked_list = new SinglyLinkedList();
$a = $linked_list->insert('A');
$linked_list->print();
$b = $linked_list->insert('B');
$linked_list->print();
$c = $linked_list->insertDataAfter($b, 'C');
$linked_list->print();
$d = $linked_list->insert('D');
$linked_list->print();
$new_node = new SinglyLinkedListNode('E');
$linked_list->insertNodeAfter($d, $new_node);
$linked_list->print();

输出如下：

A -> NULL
B -> A -> NULL
B -> C -> A -> NULL
D -> B -> C -> A -> NULL
D -> E -> B -> C -> A -> NULL