Are there other forms of representation of linked lists?

In the previous article, we have already said that in addition to the simple one-way linked list, there are several other forms of linked lists. Of course, this is also a major feature of the linked list structure, which is very flexible and convenient. Let's think about it briefly, if the next of the last node points back to the first node, then this will form a ring, which is a circular linked list.

If we add a prev attribute to each node that points to the previous node, then the linked list becomes a doubly linked list. If we also let next of the last node point to the first node on the basis of a doubly linked list, and let prev of the first node point to the last node, wouldn't this be a doubly linked list? Let’s take a closer look below.

Circular linked list

As mentioned above, we let the last node point to the first node, so the linked list formed is a circular linked list, as shown in the following figure:

We will not give a detailed explanation of the operation of the circular linked list. In fact, most of the code is the same as that of the one-way linked list, but you need to pay attention to two things:

1. When initializing and inserting operations, pay attention to the pointing of the last node. The next of the last node should point to the first node

2. The condition for judging whether the linked list traversal is completed is item->next == head , that is to say, if the next node of this node is the head node, the linked list traversal is completed.

Doubly linked list

A doubly linked list adds an attribute to the LinkedList class to point to the previous node.

// 双向链表
class LinkedList
{
    public $data;

    public $prev;
    public $next;
}

Next, we initialize a doubly linked list.

/**
 * 生成链表
 */
function createLinkedList()
{
    $list = new LinkedList();
    $list->data = null;
    $list->next = null;
    $list->prev = null; // ** 全部都初始化为 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;
        $link->prev = $r; // ** 增加上级指向 **
        $r = $link;
    }
    return $list;
}

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

var_dump($link);
var_dump($link->next->next->next->next);
// object(LinkedList)#5 (3) {
//     ["data"]=>
//     int(4)
//     ["prev"]=>
//     object(LinkedList)#4 (3) {
//       ["data"]=>
//       int(3)
//       ["prev"]=>
//       object(LinkedList)#3 (3) {
//         ["data"]=>
//         int(2)
//         ["prev"]=>
//         object(LinkedList)#2 (3) {
//           ["data"]=>
//           int(1)
//           ["prev"]=>
//           object(LinkedList)#1 (3) {
//             ["data"]=>
//             NULL
//             ["prev"]=>
//             NULL
//             ["next"]=>
//             *RECURSION*
//           }
//           ["next"]=>
//           *RECURSION*
//         }
//         ["next"]=>
//         *RECURSION*
//       }
//       ["next"]=>
//       *RECURSION*
//     }
//     ["next"]=>
//     object(LinkedList)#6 (3) {
//       ["data"]=>
//       int(5)
//       ["prev"]=>
//       *RECURSION*
//       ["next"]=>
//       object(LinkedList)#7 (3) {
//         ["data"]=>
//         int(6)
//         ["prev"]=>
//         *RECURSION*
//         ["next"]=>
//         object(LinkedList)#8 (3) {
//           ["data"]=>
//           int(7)
//           ["prev"]=>
//           *RECURSION*
//           ["next"]=>
//           object(LinkedList)#9 (3) {
//             ["data"]=>
//             int(8)
//             ["prev"]=>
//             *RECURSION*
//             ["next"]=>
//             object(LinkedList)#10 (3) {
//               ["data"]=>
//               int(9)
//               ["prev"]=>
//               *RECURSION*
//               ["next"]=>
//               object(LinkedList)#11 (3) {
//                 ["data"]=>
//                 int(10)
//                 ["prev"]=>
//                 *RECURSION*
//                 ["next"]=>
//                 NULL
//               }
//             }
//           }
//         }
//       }
//     }
//   }

echo $link->next->next->next->next->data, PHP_EOL; // 4
echo $link->next->next->next->next->prev->data, PHP_EOL; // 3

It can be seen that the difference from the one-way linked list is that there are more operations on the prev attribute. It’s relatively easy to understand here. Directly printing the linked list will display a lot of *RECURSION* content, which is an output protection mechanism of PHP. This mark indicates that the current attribute variable has a recursive type.

/**
 * 链表指定位置插入元素
 * @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;

    // ** 增加当前新创建的节点的上级指向 **
    $s->prev = $item;

    // 将 i-1 节点的下一跳节点指向 s ，完成将 s 插入指定的 i 位置，并让原来的 i 位置元素变成 i+1 位置
    $item->next = $s;

    // ** 将下级节点的 prev 指向新创建的这个节点 **
    $s->next->prev = $s;

    return true;
}

The insertion of the linked list actually adds two lines of code. One is the pointer to the superior of the currently newly created node, that is, the superior of this new node is designated as i-1 nodes. The other one is to change the superior pointer of the original i position node to the newly created node.

/**
 * 删除链表指定位置元素
 * @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;

    // ** 让目标下一个节点的上级指针指向当前这个节点 **
    $temp->next->prev = $item;

    return true;
}

Similar to the insertion node operation, the deletion node operation not only changes the point of the next node of the data of i-1 position nodes to the point of the next-level node of i node, but also changes i The superior node point of the lower-level node is changed to the i-1 node.

In fact, the definition and operation of a doubly linked list are not much different from that of a one-way linked list. It just has one more prev to point to the upper-level node. In essence, it only has one more attribute prev. It’s just an operation. So, what benefits does this extra superior pointer bring? When traversing the linked list, we use prev to have an additional traversal method, which is to traverse the linked list in reverse. When searching for a certain element, we can search from two directions at the same time, and the efficiency is doubled at once. The original time complexity of O(n) can instantly become O(n/2) time complexity.

Two-way circular linked list

Finally, we will briefly introduce the two-way circular linked list. As the name suggests, it adds the concept of a circular linked list to a doubly linked list. Let next of the last node point to the head node, and let prev of the head node point to the last node. It's easy to say but it's actually much more complicated to implement, because you not only have to pay attention to the pointing of the subordinate nodes of the last node, but also the pointing of the superior node of the head node. So we won’t do too much code demonstration here. The most important thing is that when inserting and deleting head and tail nodes, you need to pay more attention to the pointing of their upper and lower nodes.

Summary

Have you suddenly discovered a new continent? There are so many forms of linked lists. Of course, this is not finished yet. We still have a very high-end cross-linked list to talk about. However, in fact, the cross-linked list only adds more pointing attributes. The basic data field is always the same data. In fact, the most common one-way linked list, which is the one introduced in detail in the previous article, is the real focus of learning about linked lists.

Therefore, you don’t need to be anxious or panic. If you master the ordinary one-way linked list, you can kill most people in an instant. But what about these things you learned today? If you can master it, you can at least be familiar with it. The most important thing in life is to be happy. Don't push yourself too hard. If you are too hard, you will either become a dragon or an adult. Recognize your current situation and abilities. That's the most important thing.

关于线性表的内容到此为止。物理结构的存储问题就是这样了，接下来我们就要逻辑结构的世界了。也是从最简单的开始，那就是栈和队列，不要怕，它们和 树、图 比起来真的是洒洒水啦！！

测试代码：

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/2.线性表/source/2.4%20链表的其它形式.php

推荐学习：php视频教程

The above is the detailed content of Are there other forms of representation of linked lists?. For more information, please follow other related articles on the PHP Chinese website!