In the last article, we said that there are several forms of linked lists besides the simple one-way list. Of course, this is also a major feature of the linked list structure, very flexible and convenient. Let’s think about it briefly. If the next of the last node refers back to the first node, then this would form a loop. This would be a circular linked list. If we add a prev attribute to each node that points to the previous node, the list becomes a bidirectional linked list. If we have the next of the last node refer to the first node, and the prev of the first node refer to the last node on the basis of the bidirectional linked list, it would be a bidirectional circular linked list. Let’s take a look at it in detail.

Circular linked list

As mentioned above, we make the last node point to the first node, so that the linked list is a circular linked list, as shown in the figure below:

We will not go into details about the operation of the circular linked list. In fact, most of the code is the same as the one-way linked list, but we need to pay attention to two things:

1. During initialization and insertion, pay attention to the point of the last node, and the next of the last node should point to the first node

Item ->next == head. In other words, if the next node of this node is the head node, the list traversal is completed.

Two-way linked list

A bidirectional list adds a property to the LinkedList class that points to the previous node.

// class LinkedList {public $data; public $prev; public $next; }

Next, we initialize a bidirectional linked list.

/ / function createLinkedList() {$list = new LinkedList(); $list->data = null; $list->next = null; $list->prev = null; ** return $list; // return $list; } /** * initialize the list * @param array $data; */ 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; $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

As you can see, the difference with the unidirectional linked list is the addition of more operations on the prev property. It’s a little bit easier to understand here. Printing the list directly shows a lot of *RECURSION*, which is PHP’s output protection mechanism. This identifier indicates that the current property variable is of RECURSION type.

/** ** @Param LinkedList $list * @Param int $I * @Param mixed $data */ function Insert(LinkedList)  &$list, int $i, $data) { $j = 0; $item = $list; $item = $item->next; if ($j < $I - 1) {$item->next; $j++; } / / if the item does not exist or $I > n + 1 or $I < 0 if ($item = = null | | $j > $I - 1) {return false. } // Create a new node $s = new LinkedList(); $s->data = $data; $s->next = $item->next; $s->next = $item->next; $s->prev = $item; $s->prev = $item; $item->next = $s; $item->next = $s; $item->next = $s; ** $s->next->prev = $s; $s->next->prev = $s; return true; }

Inserting a linked list is simply adding two lines of code. One is a reference to the parent of the newly created node. That is, the parent of the new node is designated as I -1 node. The other is to change the parent point of the original I location 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 insert node operation, the delete node operation not only changes the point of the next node of the data of i-1 position node to the point of the next level node of I node, but also changes the point of the parent node of the next level node of I to the point of the i-1 node.

In fact, the definition and operation of a bidirectional linked list are not very different from that of a unidirectional linked list, except that there is a prev to refer to the previous node, which is essentially just an operation on the property prev. So what good does this extra superior pointer do? So when we traverse the list, we’re going to prev, so we have another way of traversing the list, which is to traverse the list backwards. When looking for an element, we can search in both directions at the same time, and the efficiency is not doubled all at once. The time complexity of O(n) suddenly becomes the time complexity of O(n/2).

Bidirectional circular linked lists

Finally, we will also briefly introduce the bidirectional cyclic linked list. As the name suggests, it is in the bidirectional linked list on the basis of the concept of circular linked list. Let the next of the last node point to the head node, and let the prev of the head node point to the last node. Easier to say but more complicated to implement, because you need to be concerned not only with the last node’s descendant pointing, but also with the head node’s superior pointing. So we will not do code demonstration here, the most important thing is when inserting and deleting header and tail nodes need to pay more attention to their upper and lower node pointing.

conclusion

Have you suddenly found a new continent? Linked lists used to come in many different forms. Of course, that’s not all, we still have a very big cross linked list, but the cross linked list just adds more points to the property, the basic data field is always the same data. In fact, the most common unidirectional linked list, which is the last article introduced in detail is what we really want to master for the linked list learning. Therefore, you do not need to worry, do not need to panic, master the ordinary one-way linked list you can kill the vast majority of people in seconds, and today’s study of these? To master the best, can not master at least a face familiar can be mixed, life, the most important thing is happy, don’t force yourself too hard, too hard, or Jackie Chan, or adult, recognize their status quo and ability is the most important.

So much for linear tables. So much for the storage of physical structures, and then we move on to the world of logical structures. Also from the most simple start, that is stack and queue, do not be afraid, they and tree, compared with the figure is really sprinkling water!!

Test code:

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/2. LinearLists/Source /2.4%20 Linked Lists Other Forms.php

References:

Data Structures, 2nd Ed., Weimin Yan

Data Structure, 2nd Edition, Yue Chen

“Notes on Data Structure with High Score”, 2020 edition, Tianqin postgraduate entrance examination

Search for “Hardcore Project Manager” on all media platforms