链表的操作绝对程序表（数组）来说就简单了许多。因为 PHP 的确曾经为咱们解决了很多数组操作上的问题，所以咱们能够很不便的操作数组，也就不必为数组定义很多的逻辑操作。比方在 C 中，数组是有长度限度的，而在 PHP 中咱们就不会思考这个问题。如果是应用 C 的话，这个长度限度就是数组构造的一大劣势，而链表，不论是在 C 还是在 PHP 中，都不会受到长度问题的限度。可能限度链表的只有内存的大小。另外，链表的链式构造也可能为咱们带来一种全新的不同于数组操作的体验，对某些性能算法来说，链表也更有劣势。

话不多说，间接来进入明天的内容吧！

链式构造的定义

首先，在之前的对于线性表的第一篇文章中咱们就说过链表的定义，在这里，咱们再温习一下之前的那个对于链表的图来更清晰的了解链表的概念。

咱们将图中的节点 Node 用类来示意：

/**
 * 链表构造
 */
class LinkedList
{
    public $data;
    public $next;
}

一个链表类就看能够看做是链表中的一个节点，它蕴含两个内容，data 示意数据，next 示意下一个节点的指针。就像链条一样一环套一环，这就是传说中的链表构造。

生成链表及初始化操作

/**
 * 生成链表
 */
function createLinkedList()
{$list = new LinkedList();
    $list->data = null;
    $list->next = null;
    return $list;
}

/**
 * 初始化链表
 * @param array $data 链表中要保留的数据，这里以数组为参考
 * @return LinkedList 链表数据
 */
function Init(array $data)
{
    // 初始化
    $list = createLinkedList();
    $r = $list;
    foreach ($data as $key => $value) {$link = new LinkedList();
        $link->data = $value;
        $link->next = null;
        $r->next = $link;
        $r = $link;
    }
    return $list;
}

$link = Init(range(1, 10));

print_r($link);
// LinkedList Object
// (//     [data] =>
//     [next] => LinkedList Object
//         (//             [data] => 1
//             [next] => LinkedList Object
//                 (//                     [data] => 2
//                     [next] => LinkedList Object
//                         (//                             [data] => 3
//                             [next] => LinkedList Object
//                                 (//                                     [data] => 4
//                                     [next] => LinkedList Object
//                                         (//                                             [data] => 5
//                                             [next] => LinkedList Object
//                                                 (//                                                     [data] => 6
//                                                     [next] => LinkedList Object
//                                                         (//                                                             [data] => 7
//                                                             [next] => LinkedList Object
//                                                                 (//                                                                     [data] => 8
//                                                                     [next] => LinkedList Object
//                                                                         (//                                                                             [data] => 9
//                                                                             [next] => LinkedList Object
//                                                                                 (//                                                                                     [data] => 10
//                                                                                     [next] =>
//                                                                                 )

//                                                                         )

//                                                                 )

//                                                         )

//                                                 )

//                                         )

//                                 )

//                         )

//                 )

//         )

// )

在应用链表的时候，咱们个别会让第一个结点不蕴含任何数据，仅仅是做为一个空的结点来指向第一个有数据的结点。这种结点咱们能够称之为头结点，如果须要判断链表是否为空的话，只须要判断第一个结点的 next 是否为空就能够了。在下面的代码中，创立链表 createLinkedList() 函数其实就是生成了这样一个头结点。

而后，咱们通过 Init() 初始化函数来结构这个链表。结构过程还是比较简单的，这里咱们是固定的传递进来一个数组，依照这个数组构造来结构这个链表，当然，在理论利用中，咱们能够应用任何数据来结构链表。结构过程也并不简单，将以后结点赋值给 r 变量，而后创立一个新结点，让 r->next 等于这个新创建的节点就能够了。结构好的链表间接打印进去的构造就是正文中的模式。

遍历链表

function IteratorLinkedList(LinkedList $link)
{while (($link = $link->next) != null) {echo $link->data, ',';}
    echo PHP_EOL;
}

链表的遍历是不是十分像某些数据库的游标操作，或者像迭代器模式的操作一样。没错，其实游标和迭代器的构造就是链表的一种表现形式。咱们不停的寻找 $next 直到没有下一个结点为止，这样就实现了一次链表的遍历。能够看出，这个过程的工夫复杂度是 O(n)。

插入、删除

/**
 * 链表指定地位插入元素
 * @param LinkedList $list 链表数据
 * @param int $i 地位
 * @param mixed $data 数据
 */
function Insert(LinkedList &$list, int $i, $data)
{
    $j = 0;
    $item = $list;
    // 遍历链表，找指定地位的前一个地位
    while ($j < $i - 1) {
        $item = $item->next;
        $j++;
    }

    // 如果 item 不存在或者 $i > n+1 或者 $i < 0
    if ($item == null || $j > $i - 1) {return false;}

    // 创立一个新节点
    $s = new LinkedList();
    $s->data = $data;

    // 新创建节点的下一个节点指向原 i-1 节点的下一跳节点，也就是以后的 i 节点
    $s->next = $item->next;
    // 将 i-1 节点的下一跳节点指向 s，实现将 s 插入指定的 i 地位，并让原来的 i 地位元素变成 i+1 地位
    $item->next = $s;

    return true;
}

/**
 * 删除链表指定地位元素
 * @param LinkedList $list 链表数据
 * @param int $i 地位
 */
function Delete(LinkedList &$list, int $i)
{
    $j = 0;
    $item = $list;
    // 遍历链表，找指定地位的前一个地位
    while ($j < $i - 1) {
        $item = $item->next;
        $j++;
    }
    // 如果 item 不存在或者 $i > n+1 或者 $i < 0
    if ($item == null || $j > $i - 1) {return false;}

    // 应用一个长期节点保留以后节点信息，$item 是第 i-1 个节点，所以 $item->next 就是咱们要找到的以后这个 i 节点
    $temp = $item->next;
    // 让以后节点，也就是指标节点的上一个节点，i-1 的这个节点的下一跳（原来的 i 地位的节点）变成原来 i 地位节点的下一跳 next 节点，让 i 地位的节点脱离链条
    $item->next = $temp->next;

    return true;
}

// 插入
Insert($link, 5, 55);
// 遍历链表
IteratorLinkedList($link); // 1,2,3,4,55,5,6,7,8,9,10,

// 删除
Delete($link, 7);
// 遍历链表
IteratorLinkedList($link); // 1,2,3,4,55,5,7,8,9,10,

链表的插入和删除其实很相似，都是须要寻找到插入或删除地位的前一个元素，也就是第 i-1 这个地位的元素。而后通过对这个元素的 next 指针的操作来实现链表元素的插入删除操作。它们在遍历和地位判断这两个性能中的代码其实都是一样的，不同的是创立时要新创建一个结点，而后让这个结点的 next 指向之前 i-1 地位元素的 next，再将 i-1 地位元素的 next 指向新创建的这个结点。而删除操作则是保留要删除这个地位 i 的结点到一个长期变量中，而后将 i-1 地位元素的 next 指向删除地位 i 的 next。

下面的解释须要联合代码一步一步来看，当然，咱们也能够联合上面的这个图来学习。插入和删除操作是链表操作的外围，也是最简单的局部，须要多多了解把握。

依据地位查找、依据数据查找

/**
 * 依据地位查找元素地位
 * @param LinkedList $list 链表数据
 * @param int $i 地位
 */
function GetElem(LinkedList &$list, int $i)
{
    $item = $list;
    $j = 1; // 从第一个开始查找，0 是头结点 
    while ($item && $j <= $i) {
        $item = $item->next;
        $j++;
    }

    if (!$item || $j > $i + 1) {return false;}
    return $item->data;

}

/**
 * 依据数据查找数据元素所在位置
 * @param LinkedList $list 链表数据
 * @param mixed $data 数据
 */
function LocateElem(LinkedList &$list, $data)
{
    $item = $list;
    $j = 1; // 从第一个开始查找，0 是头结点 
    while (($item = $item->next)!=null) {if($item->data == $data){return $j;}
        $j++;
    }

    return false;
}

// 获取指定地位的元素内容
var_dump(GetElem($link, 5)); // int(55)

// 获取指定元素所在的地位
var_dump(LocateElem($link, 55)); // int(5)

链表的查找有两种模式，一种是给一个地位，比方要我要第五个地位的元素内容，那么就是依据指定地位查找元素的值，就像数组的下标一样。不过须要留神的是，链表的下标是从 1 开始的，因为 0 的地位是咱们的头结点了。当然，咱们也能够变换代码疏忽掉头结点让它和数组保持一致，但这样的话，链表的特点就不显著了，所以这里的测试代码咱们还是以 1 为起始。

另一种查找就是给定一个数据内容，查找它在链表的什么地位。其实这两种算法都是在遍历整个链表，实质上没有什么区别。因为链表不像数组一样有下标的能力，所以它的这些查找操作的工夫复杂度都是 O(n)。

总结

怎么样，难度上来了吧。链表的操作一下就简单了很多吧，别急，这只是开胃菜。前面学习的内容基本上都会围绕着程序表（数组）和链表这两种模式进行。而且咱们的链表学习还没有完结，下一篇文章，咱们将更深刻的理解一下链表的另外几种模式：双向链表、循环链表、双向循环链表。

测试代码：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/2. 线性表 /source/2.3%20 链表的相干逻辑操作.php

参考资料：

《数据结构》第二版，严蔚敏

《数据结构》第二版，陈越

《数据结构高分笔记》2020 版，天勤考研

各自媒体平台均可搜寻【硬核项目经理】