An array of

1. Low-level implementation of arrays

Below, an array of the underlying hardware implementation, there’s something called a memory manager, when applying for an array, the computer is actually started a contiguous address in memory, each address can access through the memory manager, it can random access to any one element, access time complexity of each element are the same, The time constant is called O(1).

Java array implementation source code analysis: developer.classpath.org/doc/java/ut…

2. Analysis of the advantages and disadvantages of arrays

As shown below, when an element is inserted or deleted, all elements following it are moved down (deletion is the opposite) with a time complexity of O(n).

3. Time complexity of each array operation

  • prepend O(1)
  • append O(1)
  • lookup O(1)
  • insert O(n)
  • delete O(n)

Abstract data type

Abstract Data Type (ADT) is a set of operations, Abstract Data Type is a mathematical abstraction, in the definition of ADT does not involve how to implement the set of operations, this can be seen as an extension of modular design. For example, tables, collections, diagrams, and their operations.

They can be roughly divided into the following three categories.

  • Stack, queue, linked list
  • Collection, dictionary
  • Tree, heap, diagram

All operations on tables can be done using arrays. Although the array is dynamically specified, the maximum size of the table needs to be estimated. It is often necessary to estimate much more, thus wasting a lot of space. This is a serious limitation, especially if there are many tables of unknown size.

The array implementation makes PrintList and Find execute in linear time as expected, while FindKth takes constant time. However, insertions and deletions are expensive. For example, an insert at position 0 (which is actually making a new first element) first requires moving the entire array back one position to free up space, while removing the first element requires moving all the elements in the table forward one position, so the worst case for both operations is O (N). On average, both operations move half of the table, so they still take linear time. Creating a table with only N successive inserts will take two times.

Because the running time of inserts and deletes is so slow and the size of the table must be known in advance, simple arrays are generally not used to implement the structure of a table.

Dimension classification

A one-dimensional

Basic: Array (string), Linked List advanced: Stack, queue, deque, set, Map (hash or map), etc

A two-dimensional

Advanced: binary search tree(red-black tree, AVL), heap, disjoint set, Trie, etc

special

Bitwise, BloomFilter

The data structure of brain figure: naotu.baidu.com/file/b832f0…