This is the 10th day of my participation in Gwen Challenge

What is an array?

  1. An Array is a linear table data structure. It uses a contiguous set of memory Spaces to store a set of data of the same type.
  2. The second is contiguous memory space and the same type of data.
  3. Advantages: Two restrictions enable random access. Disadvantages: Low efficiency in deleting and inserting data

What is a linear table structure

A linear table is a row of data formed as a line. Each linear table has at most two directions: forward and back. In addition to arrays, linked lists, queues, stacks, etc., are also linear table structures.

Non-linear tables, such as binary trees, heaps, graphs, etc. It is called nonlinear because, in a nonlinear table, there is no simple contextual relationship between data.

How to implement random access to array elements according to the index?

a[i]_address = base_address + i * data_type_size
Copy the code

Base_address The first address of the memory block

Data_type_size represents the size of each element in the array

Array complexity?

Linked lists are suitable for insertion and deletion, and the time complexity is O(1). Arrays support random access with a time complexity of O(1) based on subscripts.

Why does the data need to start at zero?

  1. From the memory model of storage, subscript is best defined as offset (offset); A [0] is the position offset to 0, which is the first address; If you start at one, you have to do one more subtraction; Efficiency is not optimized to perfection
  2. Historical reasons; C language designers use 0 to start counting array subscripts, reducing learning costs

If the array is counted from 1, the memory address of the element a[k] will be changed to:

a[k]_address = base_address + (k-1)*type_size
Copy the code

Comparing the two formulas, it is not hard to see that numbering from 1 increases the number of subtractions for each random access to the array element, which in the case of the CPU increases the number of subtractions.