### List of articles

# 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 ）

### 2. Array advantages

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

### 3. Array disadvantages

- 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 ）.**

### 2. The advantages of a linked list

- 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 .

### 3. The disadvantages of 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 .**