Detailed explanation of linked list in php

The operation of linked list is much more complicated than that of sequence list. Because PHP has indeed solved many array operation problems for us, we can operate arrays very conveniently, and we do not need to define many logical operations for arrays. For example, in C, arrays have a length limit, but in PHP we will not consider this issue.

Definition of linked structure

First of all, in the first article about linear lists, we talked about the definition of linked lists. Here , let’s review the previous diagram about a linked list to understand the concept of a linked list more clearly.

We represent the node Node in the graph as a class:

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

A linked list class can be regarded as a node in the linked list. Contains two contents, data represents data, and next represents the pointer of the next node. Just like a chain, one link inside another, this is the legendary linked list structure.

Generating a linked list and initializing operations

/**
 * 生成链表
 */
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] =>
//                                                                                 )

//                                                                         )

//                                                                 )

//                                                         )

//                                                 )

//                                         )

//                                 )

//                         )

//                 )

//         )

// )

When using a linked list, we usually make the first node not contain any data and just serve as an empty node to point to the third node. A node with data. We can call this kind of node the head node. If you need to determine whether the linked list is empty, you only need to determine whether the next of the first node is empty. In the above code, the createLinkedList() function actually generates such a head node.

Then, we construct this linked list through the Init() initialization function. The construction process is relatively simple. Here we pass in an array and construct the linked list according to the array structure. Of course, in practical applications, we can use any data to construct the linked list. The construction process is not complicated. Just assign the current node to the r variable, then create a new node, and make r->next equal to the newly created node. The structure printed directly from the constructed linked list is the form in the comment.

Traversing the linked list

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

Is traversing the linked list very similar to the cursor operation of some databases, or like the operation of the iterator mode? That's right, in fact, the structure of cursors and iterators is a form of linked list. We keep looking for $next until there is no next node, thus completing a linked list traversal. It can be seen that the time complexity of this process is O(n).

Insertion and deletion

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

The insertion and deletion of linked lists are actually very similar. They both need to find the previous element at the insertion or deletion position, which is the element at the i-1th position. Then the insertion and deletion of linked list elements is implemented by operating the next pointer of this element.

The codes in the two functions of traversal and position judgment are actually the same. The difference is that when creating, a new node must be created, and then the next of this node points to the previous i-1 position. The next of the element, and then point the next of the element at position i-1 to the newly created node. The deletion operation is to save the node at position i to be deleted into a temporary variable, and then point the next of the element at position i-1 to the next at the deleted position i.

The above explanation needs to be viewed step by step with the code. Of course, we can also learn it with the following picture. Insertion and deletion operations are the core of linked list operations and the most complex part, which require a lot of understanding and mastery.

Search based on position, search based on data

/**
 * 根据位置查找元素位置
 * @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)

There are two forms of linked list search, one is to give a position, for example, I want the fifth If the element content at a position is found, then the value of the element is found based on the specified position, just like the subscript of the array. However, it should be noted that the index of the linked list starts from 1, because the position of 0 is our head node. Of course, we can also change the code to ignore the U-turn node and make it consistent with the array, but in this case, the characteristics of the linked list will not be obvious, so we still start with 1 in the test code here.

Another type of search is to given a data content and find where it is in the linked list. In fact, both algorithms are traversing the entire linked list, and there is essentially no difference. Since a linked list does not have the ability to subscript like an array, the time complexity of its search operations is O(n).

Summary

How about it, the difficulty is getting higher. The operation of the linked list will be a lot more complicated. Don't worry, this is just an appetizer. The content you will learn later will basically revolve around the two forms of sequential lists (arrays) and linked lists. And our study of linked lists is not over yet. In the next article, we will take a deeper look at other forms of linked lists: doubly linked lists, circular linked lists, and doubly circular linked lists.

Test code:

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

Recommended learning: php video tutorial

The above is the detailed content of Detailed explanation of linked list in php. For more information, please follow other related articles on the PHP Chinese website!