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

This article mainly explains "the detailed introduction of array and linked list". The content of the explanation in this article is simple and clear, and it is easy to learn and understand. let's study and learn the detailed introduction of array and linked list together.

Array

Array is a linear table data structure. It uses a continuous set of memory space to store a set of data of the same type.

Linear table and non-linear table

A linear table is a structure in which data is arranged like a line. The data on each linear table can only be in front and back directions at most. In fact, in addition to arrays, linked lists, queues, stacks and so on are also linear table structures.

For example, binary trees, heaps, graphs, and so on are called nonlinear tables, because in non-linear tables, the relationship between data is not simple.

Continuous memory space and the same type of data

Advantage: random access to elements according to the subscript.

Disadvantages: inserting and deleting elements in the array may need to migrate data to achieve continuous memory space, which is inefficient.

Random access

The computer assigns an address to each memory unit, and the computer accesses the data in memory through the address. When a computer needs to randomly access an element in an array, it first calculates the memory address stored for that element through the following addressing formula: a [I] _ address = base_address + I * data_type_size

Extension: a [I] [j] _ address = base_address + (I * n + j) * data_type_size for a [I] [j] _ array addressing formula

The expression that the time complexity of array search elements is O (1) is ❌, because even the array sorted by binary search is O (logn). The correct thing is that the array supports random access, and the time complexity of random access according to the subscript is O (1).

Inefficient insertion and deletion

Because of the continuous memory space, we need to move all the data after the element back or forward when inserting or deleting the element. That is, the best time complexity is O (1), and the worst time complexity is O (n). Since the probability of operating elements in each position is the same, the average time complexity is (1-2 +). N) / naugho (n).

If the stored data is not ordered, we can insert the element of the original position into the end of the array when inserting, and replace the element of the current position with the element at the end of the array when deleting; thus the time complexity of the insert or delete operation is O (1):

Containers and arrays

Many languages provide array-based container classes such as Java's ArrayList or C++ 's vector;. Take ArrayList as an example to see the advantages of containers over arrays:

The container can encapsulate the details of many array operations, such as the migration of other elements when elements are inserted or deleted. In addition, compared with arrays, containers can also be dynamically expanded.

Because the expansion operation involves memory request and data transfer is time-consuming, it is best to specify the data size when creating the container to avoid the expansion operation as much as possible.

For business development, the use of containers is sufficient, saving time and effort

For underlying development such as network framework and performance optimization, use arrays as much as possible.

Linked list

The linked list is also a linear table structure, which does not require continuous memory space compared to the array, and the scattered memory blocks can be concatenated by pointers, which requires less memory than the array.

Single linked list

In addition to storing data, each linked list node needs to record the position of the next node, that is, the successor pointer next.

In a single linked list, the first node is called the head node and the last node is called the tail node; the head node records the start address of the list, and the tail node subsequent pointer points to the open address NULL.

Efficient insertion and deletion

In the inefficient insertion and deletion of the above array, we said that the array needs to move the elements after the operation element in order to ensure the continuity of memory, so the time complexity is O (n). In the linked list, we only need to consider the subsequent pointer change of the adjacent nodes, so the corresponding time complexity is O (1).

Inefficient query

Because the memory address in the linked list is not contiguous, the memory address of the corresponding element cannot be calculated based on the start address and subscript, and the specified node needs to be found one by one according to the subsequent pointer.

Cyclic linked list

The only difference between a circular linked list and a single linked list is that the trailing node of the single linked list points to the null address NULL, while the subsequent pointer of the trailing node of the circular linked list points to the head node, which is connected like a ring.

Bidirectional linked list

One-way linked list has only one follow-up pointer next per node, while two-way linked list nodes have a leading pointer prev in addition to next.

Although bi-directional linked list takes up more memory space than single linked list when storing the same amount of data, it is more flexible to support two-way traversal than single linked list, which makes it easier and more efficient to insert and delete than single linked list in some cases.

In fact, when discussing the single linked list, we said that the time complexity of inserting and deleting is O (1). In fact, this description is not accurate. We have deleted the operation as an example:

Delete by comparing the values of nodes

Although the time complexity of the delete operation is O (1), we need to find the node to delete according to the value from the head node, and the time complexity of traversing the query is O (n). According to the addition rule, the time complexity of this deletion is O (n).

Delete by node

In this case, we have found the node to delete, but if it is a single linked list, we also need to traverse the single linked list to query its precursor node information, so the time complexity is still O (n).

However, the two-way linked list can find its precursor node information directly through the current node prev, so the time complexity is O (1).

Space for time

The implementation of double-linked list is the design idea of exchanging space for time; when there is sufficient memory space, if we pursue the execution speed of the code more, we can choose algorithms or data structures with relatively high space complexity but relatively low time complexity.

On the contrary, if the memory is relatively scarce, such as the code running on the mobile phone or single-chip microcomputer, at this time, it is necessary to use time for space design ideas.

Two-way cyclic linked list

Two-way circular linked list is a new version of the integration of two-way linked list and circular linked list.

Comparison between linked list and array

Array access is efficient; however, dynamic expansion is not supported and requires a whole block of memory space.

Linked lists naturally support dynamic expansion, and insert and delete operations are faster; but more memory is consumed, and frequent insertions and deletions are easy to cause memory fragmentation, which may lead to frequent GC.

Thank you for your reading. The above is the content of "detailed introduction of arrays and linked lists". After the study of this article, I believe you have a deeper understanding of the detailed introduction of arrays and linked lists. The specific use of the situation also needs to be verified by practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

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.