Shulou(Shulou.com)06/02 Report--

This article mainly explains how to understand the inversion of web array and linked list to single linked list. Interested friends may wish to have a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn how to understand the inversion of web arrays and linked lists to single linked lists.

Array and linked list

One of the biggest features of an array is that it requires a contiguous piece of memory. Suppose there is 1MB left in memory, but it is not contiguous. Applying for an array of size 1MB at this time will tell you that the application failed because the memory space is not contiguous.

One of the biggest features of linked lists is that they do not require a contiguous piece of memory. In the above example, if the application is not an array of size 1MB, but a linked list, the application will be successful.

If you only understand this level, will you think that I will always use linked lists as a data structure? No, the array has its own advantages.

When consulting the relevant information, A Fan found that the array is simple and easy to use, and because it uses continuous memory space, you can use CPU's cache mechanism to pre-read the data in the array, so the access efficiency is higher, so there are fewer insert and delete operations, and more queries, the use of arrays is more advantageous.

Linked list

It is not stored continuously in memory, and it is not friendly to the CPU cache mechanism, so it is impossible to read ahead effectively. Therefore, the linked list is suitable for use in the case of more insert and delete operations.

Linked lists are divided into single linked lists, circular linked lists, and two-way linked lists.

For a single linked list, its first node, the head node, records the base address of the list, while the last node, the tail node, points to an empty address NULL, and the circular linked list can also be understood as a special single linked list, but the tail node points to the header node instead of pointing to an empty address NULL.

The single linked list goes like this:

The circular linked list looks like this:

But in the actual development, the more commonly used linked list structure is: two-way linked list.

Its structure is as follows:

We can see that it takes up a lot of memory and supports two-way traversal. Because it has two pointers, one data takes up more memory than a single linked list.

Since it takes up a lot of memory, why is it more commonly used in actual development? there is an idea in it, let's talk about it in detail.

We know that when deleting single and double linked lists, the time complexity is O (1), but in actual development, its time complexity is not like this, why?

Think of it this way, what is your operation when you do data deletion?

First of all, look for the node in the node whose value is equal to a given value, and then delete it after finding it, right? In other words, you need to do the search work before deleting it. The time complexity of one-way linked list and two-way linked list is O (n), because it needs to traverse all the elements in order to find the element to be deleted. Combing the above process, the search time complexity is O (n), the deletion time complexity is O (1), and the total time complexity is O (n).

What does the above process look like in a double linked list? Because the double-linked list supports two-way traversal, the time complexity of finding this operation is O (1). Because it is two-way traversal, there is no need to traverse all elements when looking for elements. the time complexity of deletion is O (1), and the total time complexity is O (1).

Because the time complexity of the two-way linked list is O (1), it is more popular in development. And one of the most important ideas embodied in this is: space for time.

When memory space is not so important to time, can we ignore the secondary factors and focus on solving the principal contradiction?

Just talking and not doing is not in line with the style of Ah Fan. Today, A Fan realized a common single-linked list operation-single-linked list inversion.

Implementation of single linked list inversion code

/ * list reversal * / public class ReverseList {public static class Node {private int data; private Node next; public Node (int data, Node next) {this.data=data; this.next=next;} public int getData () {return data }} public static void main (String [] args) {/ / initialize single linked list Node node5=new Node (5 precinct null); Node node4=new Node (4 record5); Node node3=new Node (3 record4); Node node2=new Node (2 record3); Node node1=new Node (1 record2); / / call the inversion method Node reverse=reverse (node1) System.out.println (reverse);} / * * single linked list inversion * @ param list is the incoming single linked list * / public static Node reverse (Node list) {Node current=list, / / defines current as the current linked list afterReverse=null / / define afterReverse as the new linked list after conversion, initially null / / the current linked list is not empty, and reverse operation while {/ / 1. Saves the linked list Node next=current.next; / / 2 that the next pointer of the current node points to. Point the next pointer of the current node to the new linked list current.next=afterReverse; / / 3 after inversion. Save the current linked list state to the new linked list afterReverse=current; / / 4. Move the current node pointer one bit back for the next cycle current=next;} return afterReverse;}}

Next, let's debug the breakpoint and look at the results each time:

Initial state:

The first cycle ends.

The second cycle ends.

The third cycle ends.

The fourth cycle ends.

The fifth cycle ends.

At this point, I believe that everyone on the "web array and linked list to single list inversion how to understand" have a deeper understanding, might as well to the actual operation of it! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.