### 一、链表
链表是由一组节点组成的集合。每个节点包括两个部分：

一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

每个节点都使用一个对象的引用指向它的后继，最后一个节点的指针指向NULL。

链表不需要提前分配固定大小存储空间，当需要存储数据的时候分配一块内存并将这块内存插入链表中。

![](https://blog.junphp.com/public/upload/20220309/2b595384ca46f0012c2971fd71acbdf6.png)

链表分为单链表、双链表、循环链表。

![](https://blog.junphp.com/public/upload/20220309/9709f1c52e6b00009150d23e907d8d49.png)

在链表中查找第 n 个数据以及查找指定的数据的时间复杂度是 O(N) ，插入和删除数据的时间复杂度是 O(1) 。

![](https://blog.junphp.com/public/upload/20220309/323f30735cb787dc5d6ed29b7a045d3f.png)

数组和链表的区别：

||数组|链表|
|----|----|----|
|动态存储分配|数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。|链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）。|
|逻辑结构角度|数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。|链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。|
|内存存储角度|(静态)数组从栈中分配空间, 对于程序员方便快速,但自由度小。|链表从堆中分配空间, 自由度大但申请管理比较麻烦。|
|总结|1）数组静态分配内存，链表动态分配内存；2）数组在内存中连续，链表不连续；3）数组元素在栈区，链表元素在堆区；4）数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)；5）数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。||

### 单链表
![](https://blog.junphp.com/public/upload/20220309/11260a12d61d5a47d88fab94c97aa5ab.png)

插入：链表中插入一个节点的效率很高。向链表中插入一个节点，需要修改它前面的节点(前驱)，使其指向新加入的节点，而新加入的节点则指向原来前驱指向的节点（见下图）。

![](https://blog.junphp.com/public/upload/20220309/cbfa24eba587ae9f4965a47a706dfc0b.png)

由上图可知，B、C之间插入D，三者之间的关系为
```
current为插入节点的前驱节点
new->next = current->next        // 新节点D指向B的后继节点C
current->next = new              // B节点指向新节点D
```
删除：从链表中删除一个元素，将待删除元素的前驱节点指向待删除元素的后继节点，同时将待删除元素指向 null，元素就删除成功了（见下图）。

![](https://blog.junphp.com/public/upload/20220309/ee56f43e04814c96241ad7be5f70938f.png)

由上图可知，A、C之间删除B，三者之间的关系为
```
current为要删除节点的前驱节点
current->next = current->next->next    // A节点指向C节点
```
具体代码如下：
```php
// 节点类
class Node {
    public $data;   // 节点数据
    public $next;   // 下一节点

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

// 单链表类
class SingleLinkedList {
    private $header;    // 头节点

function __construct($data) {
        $this->header = new Node($data);
    }

// 查找节点
    public function find($item) {
        $current = $this->header;
        // 链路纵深查询
        while ($current->data != $item) {
            $current = $current->next;
        }
        return $current;
    }
    // （在节点后）插入新节点
    public function insert($item, $new) {
        // 节点结构
        $newNode = new Node($new);
        // 查询出上级节点信息
        $current = $this->find($item);
        // 新节点的下级节点使用父类的
        $newNode->next = $current->next;
        // 父类的下级节点改为当前节点
        $current->next = $newNode;
        return true;
    }
    // 更新节点
    public function update($old, $new) {
        $current = $this->header;
        if ($current->next == null) {
            echo "链表为空！";
            return;
        }
        // 找出节点
        while ($current->next != null) {
            if ($current->data == $old) {
                break;
            }
            $current = $current->next;
        }
        // 修改节点
        return $current->data = $new;
    }
    // 查找待删除节点的前一个节点
    public function findPrevious($item) {
        $current = $this->header;
        // 递归找出上一节点
        while ($current->next != null && $current->next->data != $item) {
            $current = $current->next;
        }
        return $current;
    }
    // 从链表中删除一个节点
    public function delete($item) {
        $previous = $this->findPrevious($item);
        if ($previous->next != null) {
            // 找出父节点，然后把下级节点修改为下下级
            $previous->next = $previous->next->next;
        }
    }
    // findPrevious和delete的整合
    public function remove($item) {
        $current = $this->header;
        while ($current->next != null && $current->next->data != $item) {
            $current = $current->next;
        }
        if ($current->next != null) {
            $current->next = $current->next->next;
        }
    }
    // 清空链表
    public function clear() {
        $this->header = null;
    }

// 显示链表中的元素
    public function display() {
        $current = $this->header;
        if (empty($current) || $current->next == null) {
            echo "链表为空！";
            return;
        }
        // 递归打印
        while ($current->next != null) {
            echo $current->next->data . "   ";
            $current = $current->next;
        }
    }
}

$linkedList = new SingleLinkedList('header');
$linkedList->insert('header', 'China');
$linkedList->insert('China', 'USA');
$linkedList->insert('USA','England');
$linkedList->insert('England','Australia');
echo '链表为：';
$linkedList->display();
echo "";
echo '-----删除节点USA-----';
echo "";
$linkedList->delete('USA');
echo '链表为：';
$linkedList->display();
echo "";
echo '-----更新节点England为Japan-----';
echo "";
$linkedList->update('England', 'Japan');
echo '链表为：';
$linkedList->display();
echo "";
echo "-----清空链表-----";
echo "";
$linkedList->clear();
$linkedList->display();
```

### 双链表
单链表从链表的头节点遍历到尾节点很简单，但从后向前遍历就没那么简单了。

它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。

所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

![](https://blog.junphp.com/public/upload/20220309/d731947d95642bbba91301b5fa341260.png)

插入：插入一个节点时，需要指出该节点正确的前驱和后继。

修改待插入节点的前驱节点的next属性，使其指向新加入的节点，而新插入的节点的next属性则指向原来前驱指向的节点，同时将原来前驱指向的节点的previous属性指向新节点，而新加入节点的previous属性指向它前驱节点（见下图）。

![](https://blog.junphp.com/public/upload/20220309/75ed6450667540e31d4d7e885dfec6b8.png)

由上图可知，B、C之间插入D，三者之间的关系为
```
current为插入节点的前驱节点
new->next = current->next        // 新节点D的next属性指向B的后继节点C
current->next->previous = new    // B的后继节点C的previous属性指向新节点D（原先是C的previous属性指向B）
current->next = new              // B的next属性指向新节点D
new->previous = current          // B的previous属性指向节点B
```
删除：双向链表的删除操作比单向链表的效率更高，因为不需要再查找前驱节点了。

首先需要在链表中找出存储待删除数据的节点，然后设置该节点前驱的 next 属性，使其指向待删除节点的后继;设置该节点后继的 previous 属性，使其指向待删除节点的前驱。

![](https://blog.junphp.com/public/upload/20220309/bf18e07dbe431936eb0724f661c71603.png)

由上图可知，B、C之间删除D，三者之间的关系为
```
current为要删除的节点
current->previous->next = current->next        // B的前驱节点A的next属性指向B的后继节点C
current->next->previous = current->previous    // B的后继节点C的previous属性指向B的前驱节点A
current->previous = null                       // B的previous属性指向null
current->next = null                           // B的next属性指向null
```
具体代码如下：
```php
// 节点类
class Node {
    public $data;              // 节点数据
    public $previous = NULL;   // 前驱
    public $next = NULL;       // 后继

public function __construct($data) {
        $this->data = $data;
        $this->previous = NULL;
        $this->next = NULL;
    }
}
// 双链表类
class DoubleLinkedList {
    private $header;    // 头节点

// 测试
$linkedList = new DoubleLinkedList('header');
$linkedList->insert('header', 'China');
$linkedList->insert('China', 'USA');
$linkedList->insert('USA','England');
$linkedList->insert('England','Australia');
echo '链表为：';
$linkedList->display();
echo "";
echo '-----删除节点USA-----';
echo "";
$linkedList->delete('USA');
echo '链表为：';
$linkedList->display();
```

### 循环链表
循环链表和单向链表相似，节点类型都是一样的。

唯一的区别是，在创建循环链表时，让其头节点的 next 属性指向它本身，即:`head.next = head`，这种行为会传导至链表中的每个节点，使得每个节点的 next 属性都指向链表的头节点。换句话说，链表的尾节点指向头节点，形成了一个循环链表。

![](https://blog.junphp.com/public/upload/20220309/6b83115166835c9b6f0b2c2893fcdac8.png)

在循环链表中，涉及遍历的操作，其终止条件是判断它们是否等于头结点，而不是像单链表那样判别p或p->next是否为空。

插入：如果不是在链表尾端插入，则与单链表相似，将待插入节点的前驱节点指向新加入的节点，而新加入的节点指向原来前驱指向的节点；如果是在尾端插入，则待插入节点的前驱节点指向新加入的节点，而新加入的节点指向头节点（见下图）。

![](https://blog.junphp.com/public/upload/20220309/cac877d26eee8e6a8ba9049440d0809a.jpg)

由上图可知，插入节点D，B、C、D三者之间的关系为
```
current为插入节点的前驱节点
// 中间
new->next = current->next        // 新节点D指向B的后继节点C
current->next = new              // B节点指向新节点D
 
// 尾端
current->next = new              // C节点指向新节点D
new->next = header               // 新节点D指向头节点Header
```
删除：如果删除的是中间元素，则与单链表操作相同，将待删除节点的前驱节点指向待删除节点的后继节点；如果删除的是尾端元素，则将待删除节点的前驱节点指向头节点。

![](https://blog.junphp.com/public/upload/20220309/dc89a55d0cb9b5dc623963fa9db734e4.jpg)

由上图可知，删除节点时，B、C、D三者之间的关系为
```
current为要删除节点的前驱节点
// 中间
current->next = current->next->next    // A节点指向C节点
 
// 尾端
current->next = header                 // B节点指向头节点Header
```
具体代码如下：
```php
// 节点类
class Node {
    public $data;   // 节点数据
    public $next;   // 下一节点

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

// 循环链表类
class CircularLinkedList {
    private $header;    // 头节点

// 修改节点
        return $current->data = $new;
    }
    // 删除节点
    public function delete($item) {
        $current = $this->header;
        while ($current->next != null && $current->next->data != $item) {
            $current = $current->next;
        }
        // 链表中间
        if ($current->next != $this->header) {
            $current->next = $current->next->next;
        } else { // 链表尾端
            $current->next = $this->header;
        }
    }
    // 显示链表中的元素
    public function display() {
        $current = $this->header;
        while ($current->next != $this->header) {
            echo $current->next->data . "   ";
            $current = $current->next;
        }
    }
}

// 测试
$linkedList = new CircularLinkedList('header');
$linkedList->insert('header', 'China');
$linkedList->insert('China', 'USA');
$linkedList->insert('USA', 'England');
$linkedList->insert('England', 'Australia');
echo '链表为：';
$linkedList->display();
echo "";
echo '-----删除节点USA-----';
echo "";
$linkedList->delete('USA');
echo '链表为：';
$linkedList->display();
echo "";
echo '-----更新节点China为Japan-----';
echo "";
$linkedList->update('China', 'Japan');
echo '链表为：';
$linkedList->display();
```
注：循环链表还可以分为单循环链表和双循环链表，这里只实现了单循环链表。

已有0条评论

添加新评论☺

如果认为本文对您有所帮助请赞助本站

支付宝扫一扫赞助

已有0条评论

添加新评论☺