Lists and arrays in memory

Conclusion:

  • JAVA does not automatically increase the memory allocation space,JavaScript can automatically increase the memory allocation space
  • The storage space of an array must be continuous. There is no requirement for a linked list
  • Array reads are O(1) fast, inserts are O(n) slow (lists are reversed)

For example, in JS, you can add or remove an array after naming an array, and you can change the length of an array by passing. Length.

Properties of arrays

  • The array name is actually the first address of the contiguic memory address
  • Arrays must be contiguous in memory, so when an array is added, a contiguous memory space is reallocated

First of all:

  • JavaScript can either pre-allocate memory space or not declare it

    For example, if you only have a 2-cell Array, you can declare 10 positions up front new Array(10)

    New Array() or[] new Array() or[]

    Or we can instantiate new Array(a,b,c)

  • Disadvantages:

    The extra requested space may not be used and cause a waste of memory

    After adding more than 10 arrays, the memory address must be transferred again

Properties of linked lists

  • Linked lists can be stored anywhere in memory, and each element in the list stores the address of the next element
  • Such chained storage of addresses strings together a series of array elements stored in random memory addresses.

First of all:

  • Adding a new element is as simple as putting it in memory and storing its address in the previous element.

    It does not have to be contiguous

    You don’t need to move elements

    Higher memory utilization

  • Disadvantages: A problem arises when the address of each element in the list must be retrieved from the previous element

    When obtaining the NTH element in the list, it must be accessed from the first element of the list, and the memory address can be found by obtaining the chain, which is very inefficient.

    Because the array is ordered, it takes a simple operation to find any element in the array

conclusion

It can be seen from the characteristics of the two:

  • The array insertion takes O(n) and the array read takes O(1).
  • The list takes O(1) to insert and O(n) to read.

The reading speed of arrays is fast, while the insertion speed is slow. The reading speed of linked lists is slow (random but not full reading), and the insertion speed is fast. Select an appropriate storage scheme based on the actual service scenario.

You may also be interested in the following

  • # Algorithm Diagram 2 (recursion and call stack in memory)
  • # Algorithm Diagram 3 (Quicksort and Euclid)
  • # Algorithm Figure 4 (hash table and loading factor)
  • # JavaScript Language Essence
  • How are some of the apis implemented in # VUE3.0?
  • JavaScript reads local file configuration (compatible with lower IE versions)
  • # What do you ask about the front end of one year’s work experience?