# Interview question: the difference between array and sequential list

2021-10-14 06:28:08

# One 、 Array (Array)

### 1. Array characteristics

So called array , Namely Elements of the same data type A collection arranged in a certain order ; The storage interval of the array is continuous , It takes up a lot of memory , So the space is very complex . But the time complexity of binary search is small , All are O(1); Array is characterized by ： Simple query , Add and delete difficulties .

• In memory , An array is a contiguous region .
• The array needs to reserve space .
Before using, you need to apply for the amount of memory occupied in advance , If you don't know how much space you need in advance , Pre application may waste memory space , That is, the space utilization of array is low . notes ： The space of the array needs to be determined during the compilation phase , So we need to give the size of array space in advance ( It is not allowed to change in the operation phase ).
• At the beginning of the array , Inserting and deleting data is inefficient .
When inserting data , The element to be inserted and all elements behind it need to be moved back . When deleting data , All elements after the position to be deleted need to be moved forward .
• Random access is very efficient , Time complexity can reach O(1).
Because the memory of the array is continuous , Want to access that element , Directly from the array's first address back offset can be accessed .
• The space opened up by the array , It needs to be expanded when it is not enough ; For expansion , It involves moving all the elements in the old array to the new array .
• Array space is allocated from the stack .（ Stack ： First in, then out ）

• Random access , Fast search speed , The time complexity is 0（1）.

• Remove... From the head 、 The efficiency of inserting from the head is low , The time complexity is o(n), Because we need to move forward and backward accordingly .
• Space utilization is not high .
• High memory requirements , There must be enough continuous memory space .
• The space size of the array is fixed , No dynamic expansion .
• The array is out of bounds .

# Two 、 Linked list (ListNode)

### 1. The characteristics of linked list ：

The so-called chain list , A linked list is a physical storage unit that is discontinuous 、 Nonsequential storage structure , The logical order of data elements is achieved by the order of Pointers in a linked list . A linked list consists of a series of nodes （ Each element in a linked list is called a node ） form , Nodes can be generated dynamically at run time . Each node has two parts ： One is the data domain where the data elements are stored , The other is a pointer field that stores the address of the next node . Compared to linear table order structure , The operation is complicated . Because you don't have to store in order , The list can be inserted to O(1) Complexity , It's much faster than the other linear order table , But finding a node or accessing a specific number of nodes requires O(n) Time for , The time complexity of linear table and sequential table is O(logn) and O(1).

Linked list : Discrete storage interval of linked list , It takes up a lot of memory , So the space complexity is very small , But time is very complicated , reach O（N）. The feature of the list is ： Queries are difficult relative to arrays , Easy to add and delete .

• In memory , The space of elements can be anywhere , Space is scattered , There is no need for continuity .
• The elements in the linked list have two attributes , One is the value of the element , The other is the pointer , This pointer marks the address of the next element .
Each data will save the memory address of the next data , Through this address, you can find the next data .
• Inefficient time to find data , The time complexity is o(n).
Because the space of the linked list is scattered , So it doesn't have random access , If you need to access data at a location , You need to start with the first number , Go back in turn , Know where to find the query , Therefore, when looking for an element , The time complexity is O(n).
• Space does not need to be specified in advance , It's a dynamic application , Dynamically apply and delete memory space according to requirements , Easy to expand , So the utilization rate of space is high .
• The time efficiency of inserting and deleting elements at any position is high , The time complexity is O(1).
• The space of the linked list is allocated from the heap .（ Pile up ： fifo , last in last out ）.

• The speed of inserting and deleting elements anywhere , The time complexity is O(1).
• High memory utilization , It doesn't waste memory .
• The space size of the linked list is not fixed , It can be expanded dynamically .
• There is no cross boundary problem in linked list .

Random access is inefficient , The time complexity is O(1).

# 3、 ... and 、 Array 、 Summary of the list • For want to access data quickly , Not often when you insert and delete elements , Select array .
• For elements that need to be inserted and deleted frequently , And the efficiency of accessing elements is not very high , Choose the list . https://chowdera.com/2021/10/20211002145852958p.html