The operation of linked lists is much more complicated than that of sequential lists (arrays). Because PHP does take care of a lot of array manipulation for us, we can easily manipulate arrays without having to define a lot of logical operations for arrays. For example, in C, arrays have a length limit, but in PHP we don’t care about that. This length limit is a major disadvantage of array structure in C, and linked lists, in C or PHP, are not subject to length issues. The only thing that limits a linked list is the size of memory. In addition, the chained structure of the list can also bring us a new experience that is different from the array operation, and for some functional algorithms, the list is also more advantageous.

Without further ado, let’s go straight to today’s content!

Definition of chained structure

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

The Node Node in the figure is represented by a class:

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

A linked list class can be thought of as a node in a linked list. It contains two contents, data representing data and next representing a pointer to the next node. Like a chain, one link to another link, this is the legend of the linked list structure.

Generate the linked list and initialize the operation

/ / function createLinkedList() {$list = new LinkedList(); $list->data = null; $list->next = null; 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; $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 we use linked lists, we usually make the first node contain no data, and simply point to the first node that has data as an empty node. This type of node is called a head node, and if you want to determine if the list is empty, you just need to determine if the first node’s next is empty. In the above code, creating the list createLinkedList() function actually generates such a header.

We then construct the list with the Init() initializer function. The construction process is relatively simple, so we’re just going to stick an array in and construct the list according to that array structure, and of course, in practice, we can use any data to construct the list. The construction process is not complicated. Assign the current node to the r variable, and then create a new node, setting R-> next equal to the newly created node. The structure printed directly out of the constructed list is the form in the comment.

Traversing the list

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

Is the traversal of a linked list very much like some database cursor operations, or iterator mode operations. Yes, the structure of cursors and iterators is a form of a linked list. We keep looking for $next until there is no next node, thus completing a linked list traversal. As you can see, the time of this process is order n.

Insert, delete

/** ** @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; $item->next = $s; $item->next = $s; $item->next = $s; return true; } /** ** Delete($list, $I, $I, $I, $I, $I, $I, $I); int $i) { $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. } / / save the current using a temporary node information, $item is the first I - 1 node, so $item - > next is what we want to find the current node $I temp = $item - > next; $item->next = $temp->next; $item->next = $temp->next; return true; } // Insert($link, 5, 55); // iteratorLinkedList ($link); / / 1,2,3,4,55,5,6,7,8,9,10, / / Delete the Delete ($link, 7); // iteratorLinkedList ($link); / / 1,2,3,4,55,5,7,8,9,10,

Insertions and deletions are very similar in that we need to find the element before the insertion or deletions position, which is at the position I minus 1. The next pointer of the element is then used to insert and delete the linked list elements. The code in traversal and position determination is actually the same. The only difference is that we need to create a new node, then make the next of this node point to the next of the previous i-1 position element, and then point the next of the i-1 position element to the newly created node. The delete operation saves the node at position I to be deleted in a temporary variable, and then points the next at position I -1 to the next at position I.

The above explanation needs to be combined with the code step by step, of course, we can also be combined with the following diagram to learn. Insertion and deletion operations are the core and most complex parts of linked list operations, and require a lot of understanding.

Search according to location, search according to data

/** ** ** @Param LinkedList $list * @Param int $I */ function getEem (LinkedList &$list, $I, $I) int $i) { $item = $list; $j = 1; While ($item && $j <= $I) {$item = $item->next; $j++; } if (! $item || $j > $i + 1) { return false; } return $item->data; ** ** ** ** ** */ function locateEem (linkedList &$list, $list, $list, $list, $list, $list, $list, $list, $list, $list, $list, $list, $list, $list, $list, $list, $list, $list, $list, $list, $list, $list, $list, $list, $list, $list) $data) { $item = $list; $j = 1; While (($item = $item->next)) {$item->next); =null) { if($item->data == $data){ return $j; } $j++; } return false; } var_dump(getElem ($link, 5)); Var_dump (locateEem ($link, 55)); // int(5)

There are two ways to look up a linked list. One way is to give a position, for example, I want the contents of the element in the fifth position, so I look up the value of the element according to the specified position, just like the index of an array. But notice that the index of the list starts at 1, because 0 is our head node. Of course, we could have changed the code to ignore the head node and make it the same as the array, but that would have made the list less obvious, so the test code here is going to start with 1.

Another kind of lookup is to find where in the linked list a data item is given. In fact, both of these algorithms are traversing the entire linked list, and there is essentially no difference. Because lists don’t have the subscripting capability of arrays, these lookups are O(n) in time.

conclusion

Well, here we go. Linked list operation is a lot more complicated, don’t worry, this is just appetizer. The following content will basically focus on the two forms of sequential list (array) and linked list. And we have not finished the study of linked lists, next article, we will have a deeper understanding of the other forms of linked lists: bidirectional linked lists, cyclic linked lists, bidirectional cyclic linked lists.

Test code:

https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/2. Linear Lists /source/2.3%20 Linked Lists

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