当前位置:网站首页>Interview question: the difference between array and sequential list

Interview question: the difference between array and sequential list

2021-10-14 06:28:08 The senming Gang is bigger than the black tiger gang

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

 Insert picture description here

  • 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 .
     Insert picture description here

版权声明
本文为[The senming Gang is bigger than the black tiger gang]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/10/20211002145852958p.html

随机推荐