Zero, Preface:

When it comes to containers, you’re probably used to using arrayLists and arrays. Have you ever thought about the difference between arrayLists and arrays?

ArrayList = Array + List ArrayList = Array + List ArrayList = Array + List ArrayList = Array + List ArrayList = Array + List ArrayList = Array + List Don’t ask me what software to draw renderings… Because there is no software to draw. The next section will take you to draw your own picture!! I hope you can join me at Github to witness the birth and growth of DS4Android. Welcome star

0. No matter what else, leave the picture first:

Routine operations on table structures

Expansion and reduction of arrays

1. What kinds of watches do we have in our lives?
Class schedules, grades, schedules, train schedules, watches (forget it...)Copy the code
2. What’s the use of watches?

The same kind of object can be unified management, such as the score table: grade three class 12 54 students for the achievement of students is the object, the object also includes mathematics, Chinese, English... Attributes such as The chaos of the 54 objects together, so in a row, which is the outstanding student, which is the result of poor student be clear at a glance, is very convenient If one object per grades, can get back to the object is set about, is also very convenient If a man cheated, scores cancelled, remove directly, It is very convenient for us to compare our grades between Class 12 and Class 11Copy the code
3. What’s the difference between tables and arrays?

The best analogy is that an array is like a printed paper version and a table structure is like an operational version of Excel

2. For example: if the array is removed, the ranking of the people behind it will remain the same ----(I have not a blank ranking high, you say not annoying people...) The young monk asked the old monk: "What is a saint?" The young monk asked the old monk:" What is a saint?" The old monk said: "good good study, day day up, ready to help others, the good faith friendly" here "saints" is an abstract, "good good study, day day up, ready to help others, the good faith friendly" is the "saint" "conditions (function)," the young monk according to do so, he is a old monk in the eyes of "saint", namely the young monk has realized the saint. 4. Also, the table is an abstraction, it is possible to define your view of the table, and add(),get(),set(),remove() and other functions to it 5. In fact, ArrayList in Java implements the List abstract interfaceCopy the code
4. Array table structure: the priority of this article

Define your own table structure

Since Java uses List, I’ll give it a new name, Chart, for the sake of confusion

1. Define the interface of the table

What does your table do? (Interface methods should be clearly commented.)

/** * Author: Zhang Feng Jiete Lie * Time: 2018/9/25 0025:8:25 * Email: [email protected] * Description: Linear table structure interface * / public interface IChart < T > {/ / region -- -- -- -- -- -- -- -- -- -- -- -- -- add operation -- -- -- -- -- -- -- -- -- -- -- -- / designated add * * * * * @ param index index * @ param Void add(int index, T el); /** * add tail ** @param el data element */ void add(T el); / / endregion / / region -- -- -- -- -- -- -- -- -- -- -- -- -- delete -- -- -- -- -- -- -- -- -- -- -- -- / positioning delete * * * * * @ param index index * @ the element of return to delete * / T remove (int index); /** * remove the end ** @return remove the element */ T remove(); /** * remove the first occurrence of the specified element ** @param el data element * @return element position */ int removeEl(T el); /** * remove all specified elements ** @param el data element */ Boolean removeEls(T el); /** * Clear the collection */ void clear(); / / endregion / / region -- -- -- -- -- -- -- -- -- -- -- -- -- to check operation -- -- -- -- -- -- -- -- -- -- -- - / * * * * * set the elements of a position of new value @ param index index * @ param el new value * @ * / T return the old values  set(int index, T el); /** * get(int index) ** @param index * @return data element */ T get(int index); ** @param el data element * @return index set */ int[] getIndex(T el); / / endregion / / region -- -- -- -- -- -- -- -- -- -- -- -- other operations -- -- -- -- -- -- -- -- -- -- -- -- - / * * * collection contains elements of a * * * @ @ param el data elements return contains * / public Boolean contains(T el); /** * connect two sets ** @param iChart insert set ** @return merge set */ public iChart <T> contact(iChart <T> iChart); @param <T> contact(int index) ** @param <T> contact(int index) ** @param <T> contact(int index) ** @param <T> contact(int index) ** @param <T> contact(int index) ** @param <T> contact(int index) ** @param <T> contact(int index), IChart<T> iChart); /** * is null ** @return is null */ Boolean isEmpty(); /** * Return the size of the collection ** @return size */ int size(); /** * Get array capacity * @return array capacity */ int capacity(); //endregion }Copy the code
2. Use arrays to implement table structure: ArrayChart

Implement the interface and implement all the methods in the interface

/** * Author: Zhang Feng Jiete Lie <br/> * Time: 2018/11/210021:8:18 <br/> * Email: [email protected]<br/> * Description: */ public class implements IChart<T> {// Implements IChart<T>Copy the code
3. Member variables and construct initialization
private int size; Private T[] data; private T[] data; Private static final int DEFAULT_CAPACITY = 10; Private static final float GROW_RATE = 1.f; private static final float GROW_RATE = 1.f; Public ArrayChart() {this(DEFAULT_CAPACITY); } public ArrayChart(int capacity) {data = (T[]) new Object[capacity]; // Initialize array table when creating array tableCopy the code
4. Simple interface implementation:
@Override
public boolean isEmpty() {
    return size == 0;
}

@Override
public int size() {
    return size;
}

@Override
public int capacity() {
    return data.length;
}
Copy the code

Ii. Implementation of the main method (CRUD)

1. Add elements at a fixed point:

The idea is to move all elements after a fixed point back one bit, leaving the top spot open for the element to be added

The purple box represents the empty array bit, and the middle is filled with the actual elements in the table. The point add is added before the selected index, so add to the end is add(size,data)

@Override public void add(T el) { add(size , el); } @override public void add(int index, int index) T el) { if (index < 0 || index > size) { throw new IllegalArgumentException("Add failed! Make sure index < 0 || index > size"); } for (int I = size -1; int I = size -1; i >= index; i--) { data[i + 1] = data[i]; } data[index] = el; size++; }Copy the code

Get (),set() :

@Override public T set(int index, T el) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Set failed! Make sure index < 0 || index > size"); } T oldEl = get(index); data[index] = el; Return oldEl; return oldEl; } @Override public T get(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Get failed! Make sure index < 0 || index > size"); } return data[index]; // Query the corresponding index of the array}Copy the code

The fixed value query gets the index

@Override public int[] getIndex(T el) { int[] tempArray = new int[size]; Int count = 0; For (int I = 0; i < size; If (data[I].equals(el)) {tempArray[count] = I; count++; Int [] indexArray = new int[count]; for (int i = 0; i < count; i++) { indexArray[i] = tempArray[i]; } return indexArray; // Return an indexed array to find the elements (equivalent to a score sheet to see who scored 80 in math)}Copy the code
3. Delete elements:

@Override public T remove() { return remove(size - 1); } @Override public T remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Remove failed! Make sure index < 0 || index > size"); } T temp = get(index); System.arraycopy(data, index + 1, data, index + 1-1, size - index + 1); for (int i = index + 1; i < size; i++) { data[i - 1] = data[i]; } size--; Data [size] = null; return temp; }Copy the code

Other deletes:

Delete single and delete all of the elements equivalent to the previous combined operations, not to demonstrate the operation

@Override public int removeEl(T el) { int[] indexes = getIndex(el); Int index = -1; int index = -1; if (indexes.length > 0) { index = indexes[0]; remove(indexes[0]); } return index; } @override public Boolean removeEls(T el) {// remove all int[] indexArray = getIndex(el); if (indexArray.length ! = 0) { for (int i = 0; i < indexArray.length; i++) { remove(indexArray[i] - i); -i} return true; } return false; }Copy the code

3. Realization of dynamic capacity expansion and capacity reduction

There’s nothing high and mighty, it just doesn’t fit in one basket, it just fits in a bigger basket, right

1. Implementation of capacity expansion and capacity reduction
/** * Capacity Expansion/Capacity reduction ** @param newCapacity New capacity */ private void grow(int newCapacity) {T[] newData = (T[]) new Object[newCapacity]; For (int I = 0; i < size; I ++) {newData[I] = data[I]; } data = newData; }Copy the code
2. Capacity expansion and capacity reduction

When is capacity expansion —- basket not enough for bai — When does add need to shrink the capacity —-1000 capacity basket for 1 egg think it is a waste –remove

1) Add detects expansion time: Full
@Override public void add(int index, T el) {if (size == data.length) {// grow((int) (GROW_RATE * data.length)); / / change the 1.5 times of basket} the if (index < 0 | | index > size) {throw new IllegalArgumentException (" Add failed! Make sure index < 0 || index > size"); } system.arrayCopy (data, index, data, index + 1, size - index); for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } data[index] = el; size++; }Copy the code
2) Remove Detects the capacity reduction timing

The judgment mark here is to reserve many points for use, otherwise frequent insertions and removals may lead to repeated capacity expansion or reduction.

The basket might say, “Are you shrinking or putting? Are you playing with me….? “I’ll leave you more space!”

@Override public T remove(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException("Remove failed! Make sure index < 0 || index > size"); } T temp = get(index); System.arraycopy(data, index + 1, data, index + 1-1, size - index + 1); for (int i = index + 1; i < size; i++) { data[i - 1] = data[i]; } size--; Data [size] = null; If (size == data.length / 4 && data.length / 2! = 0 && data.length > 5) { grow(data.length / 2); } return temp; }Copy the code
3. When clearing, the array scales to its initial value
@Override
public void clear() {
    size = 0;
    grow(DEFAULT_CAPACITY);
}
Copy the code

Iv. Other operations

1. Whether to include an element
@Override public boolean contains(T el) { return getIndex(el).length ! = 0; // Query data by value}Copy the code
2. Contact the array

@Override public IChart<T> contact(IChart<T> iChart) { return contact(size - 1, iChart); } @Override public IChart<T> contact(int index, IChart<T> iChart) { if (! (iChart instanceof ArrayChart)) {return null; } for (int I = index; int I = index; i < index + iChart.size(); i++) { add(i + 1, iChart.get(i - index)); } return this; }Copy the code

So that’s pretty much it as a table structure, but there are other operations that you can customize the interface and implement yourself,

But any operation, no matter how complex, is a combination of the above.

V. Summary:

For the analysis of complexity, wait until all the table structures are covered and then compare them as a whole, but here’s a rough feel

Take the test
Method \ Number of operations 1000 10000 10W 100W 1000W
Add the first 0.0063 seconds 0.2706 seconds 19.5379 seconds —- —-
Add the tail 0.0004 seconds 0.0025 seconds 0.0141 seconds 0.0687 seconds 1.26014 seconds
Remove the first 0.0063 seconds 0.2771 seconds 19.7902 seconds —- —-
Remove the tail 0.0005 seconds 0.0036 seconds 0.0091 seconds 0.02301 seconds 0.1607 seconds:

You can see how hard it is to add/remove at the beginning, as you can see from the code, after all, to get everyone to move

Think about if 30,000 people in a row, the first person to go, all the people behind move forward, is it a lot of work if you decide to plug in the first, let the people behind move back….. (Big brother, is it not good to be alive….) So if you operate on the first element too often, don’t die. ArrayList structures don’t work for you

Further updates in this series link collection :(dynamic updates)

  • Visible data structures: the introduction to the Android version
  • Array Tables for Android (Data Structures)
  • Android Array Table (View Section)
  • Visible data structure Android version of the single linked list
  • Visible data structure Android version of the double Linked list
  • Visible data structure stack for Android version
  • Visible data structure of the Android version of the queue article
  • Visible data structure Android version of the binary search tree
  • More data structures – more on that later

Postscript: Jie wen standard

1. Growth record and Errata of this paper
Program source code The date of note
V0.1 – making 2018-11-21 Table array implementation for Android
2. More about me
Pen name QQ WeChat hobby
Zhang Feng Jie te Li 1981462002 zdl1994328 language
My lot My Jane books I’m the nuggets Personal website
3. The statement

1—- This article is originally written by Zhang Fengjie, please note if reproduced

2—- welcome the majority of programming enthusiasts to communicate with each other 3—- personal ability is limited, if there is something wrong welcome to criticize and testify, must be humble to correct 4—- see here, I thank you here for your love and support