Arrays and Linked Lists of Java Object Oriented Fundamentals

Advantages of arrays:

Strong random access Fast search speed Array requires a continuous memory space to store, which requires that this space is continuous physically, and each element has a specified index index pointing to the memory address. Therefore, when querying, the information stored at the corresponding address can be quickly found according to index, which is fast query.

Disadvantages of arrays:

Inefficient insertion and deletion When adding or deleting an array, all elements after the target position must be moved as a whole, so it is time-consuming, which is slow to add or delete. May waste memory Memory space requirements are high, and there must be enough continuous memory space. The array size is fixed and cannot be expanded dynamically

Advantages of linked lists:

Fast insertion and deletion speed Linked lists dynamically allocate storage space physically, which does not require continuity, but requires logical continuity. It needs to store the address of each element in memory, as well as the address of its neighboring elements, and then chain the elements like Chain 1 to ensure logical continuity.

For example:

In a single linked list, each element not only stores its own value, but also stores the reference of the precursor, that is, stores the memory address information where the precursor is located.

A double-linked list stores not only preceding references but also subsequent references.

When adding an element, you only need to add the address of its previous element or its subsequent element to the added element; When deleting an element, modify the first connection address of the precursor and postdriver of the target element. Therefore, it is fast to add and delete. High memory utilization rate, no waste of memory size is not fixed, and expansion is flexible.

Disadvantages of linked list:

It can't be searched randomly, and it must be traversed from the first one, which is inefficient to search Because there is no index like array, it is necessary to traverse the memory addresses of all elements in the whole linked list before determining the target element, which is slow for query.

Memory storage can be divided into continuous storage and discrete storage. Therefore, there are two physical storage structures of data: continuous storage and discrete storage, which correspond to what we usually call arrays and linked lists.

Because the array is stored continuously, when manipulating the data in the array, the data in the corresponding position can be directly accessed according to the offset from the first address. However, if you want to insert an element at any position in the data group, you need to move the following elements backward by one bit to free up the storage space.

On the contrary, the linked list is stored discretely, so when inserting one data, it is only necessary to apply for one new space, and then make one modification to the connection relationship, but obviously, when looking for one data on the linked list, it is necessary to traverse one by one.

Considering the above summary, it can be seen that arrays and linked lists have their own advantages and disadvantages. When using it, it should be selected according to the specific situation. It is best to use arrays when there are many operations to find data; When adding or deleting more data in the dataset, it is best to choose linked list.

An array is like a person numbered and standing in a row. It is easy to find the 10th person, and it can be found quickly according to the number on the person. But insert, delete slow, want to look at a certain position insert or delete a person, the number of the person behind will change. Of course, people who join or delete are always fast at the end

A linked list is like a person standing in a circle hand in hand. It is not easy to find the 10th person. It must be counted from the first person. But insert and delete quickly. When inserting, just untie the hands of two people and take the hands of the newly added people again. Delete the reason of 1.

Summary:

Array statically allocates memory, linked list dynamically allocates memory; Arrays are continuous in memory, and linked lists are discontinuous; Array elements are in the stack area and linked list elements are in the heap area. The array is located by subscript, and the time complexity is O (1), and the time complexity of linked list positioning elements is O (n); The time complexity of inserting or deleting elements in array is O (n), and the time complexity of linked list is O (1);

This article is here, I hope to give you help, but also hope that you can pay more attention to this site more content!