️ Preface ️

This article is about an important part of data structure , Will be used frequently , It is also the foreshadowing content of the linked list data structure .

Blog home page ：【 Warm the sun like the wind 】
The high-quality goods Java special column 【JavaSE】、【 Prepare for blue bridge 】、【JavaEE The first step 】、【MySQL】、【 data structure 】
Welcome to thumb up Collection Leave a comment Private letters must be answered

This paper is written by 【 Warm the sun like the wind 】 original , First appeared in CSDN

Bloggers will continue to update their learning records and gain , If you have any questions, you can leave a message in the comment area

The source code involved in the blog and the daily practice code of the blogger have been uploaded Code cloud (gitee)、GitHub

---

ArrayList And sequence table

1. The linear table

The linear table （linear list） yes n A finite sequence of data elements with the same characteristics .

Linear table is a data structure widely used in practice , Common linear tables ： The order sheet 、 Linked list 、 Stack 、 queue …

A linear table is logically a linear structure , That is to say, it is a continuous straight line . But it is not necessarily continuous in physical structure , When a linear table is physically stored , It is usually stored in the form of array and chain structure .

2. The order sheet

The sequence table uses a paragraph The physical address is continuous The linear structure of the data elements is sequentially stored in the storage units of the , In general, array storage is used . Complete the number on the array

According to the addition, deletion, inspection and modification of , Actually , Speaking of human words is a higher-level array , Some functions can be completed on this advanced array .

So what exactly does this advanced array look like , Let's take a look at it

In fact, it will look like this after it is visualized , There is one more element than an ordinary array ——usedSize, Used to store the number of valid data .

Let's use code to create this sequence table ：

public class MyArrayList {
    
    public int[] elem;// Array 
    public int usedSize;// The number of valid data   The two on the left form our sequence table in the heap area 
    public static final int DEFAULT_CAPACITY=5;;//DEFAULT_CAPACITY Is the capacity of the sequence table array , Store it in the method area , Does not belong to the object 

    public MyArrayList() {
    // The constructor instantiates the sequence table 
        this.elem = new int[DEFAULT_CAPACITY];
        //this.usedSize = 0; The default is 0  You can write or not 
    }
}

This is the function of this sequence table （ Interface ）：

public void display() {
     } //  Print order table  
public void add(int pos, int data) {
     } //  stay  pos  Location new element  
public boolean contains(int toFind) {
     return true; }//  Determine whether to include an element  
public int search(int toFind) {
     return -1; }//  Find the corresponding position of an element 
public int getPos(int pos) {
     return -1; } //  obtain  pos  The element of location value
public void setPos(int pos, int value) {
     } //  to  pos  The element of the position is set to key
public void remove(int toRemove) {
     } // Delete the first keyword 
public int size() {
     return 0; } //  Get the length of the order table  
public void clear() {
     }//  Clear the sequence table  

Next, the specific implementation of these interfaces （ The order is consistent ）

1. Print order table （ The two methods ）

import java.util.Arrays;// The first method 
	public void display() {
      // Import until package , And use it directly Arrays.toString（） To print the sequence table 
        System.out.println(Arrays.toString(this.elem));
    }


    public void display() {
    // The second method 
        for (int i = 0; i < this.usedSize; i++) {
    // Set the cycle to print the elements in the sequence table in turn 
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }

2. stay pos Location new element

There are three steps to complete this work ：

（1） Judge pos Whether the location is legal

（2） Move data （pos The data after the position makes room for new elements , Move back as a whole to flash an open space ）

（3） Put the data （ The new boss is sitting here ）

import java.util.Arrays;
	private boolean isFull() {
    // Determine whether the sequence table is full 
        return this.usedSize==this.elem.length;// Equal return true, Otherwise return to false
    }    
	public void add(int pos,int data) {
    
        if(pos<0||pos>this.usedSize) {
    // When pos When it is negative or greater than the effective number , The location is illegal. Return directly 
            return;
        }
        if (isFull()) {
    // If the sequence table is full , Capacity increase is required 
            this.elem = Arrays.copyOf(this.elem, 2*elem.length);// The new array needs to copy the progressiveness of the original array , Then its capacity becomes original 2 times 
        }
        for (int i = usedSize-1; i >=pos; i--) {
    // Set the loop , Start from the back and move forward , To pos Position end cycle , Flash out a seat 
            this.elem[i+1]=this.elem[i];
        }
        this.elem[pos]=data;// Put the data 
        this.usedSize++;// Effective number +1
    }

3. Determine whether to include an element

    public boolean contains(int toFind) {
    
        for (int i = 0; i < this.usedSize; i++) {
    // Traverse the sequence table and compare one by one , Same back true
            if(toFind==this.elem[i]) {
    
                return true;
            }
        }
        return false;// The traversal is still not complete return, Just go back to false
    }

4. Find the corresponding position of an element

    public int search(int toFind) {
    
        for (int i = 0; i < this.usedSize; i++) {
    // And 3 Actually, it's the same , Compare one by one , Find and return its corner sign 
            if(toFind==this.elem[i]) {
    
                return i;
            }
        }
        return -1;// Go back if you can't find it -1, Because the array subscript has no -1,-1 It means that... Is not found 
    }

5. obtain pos The element of location

    public int getPos(int Pos) {
    
        if(this.usedSize==0) {
    // If the sequence table is empty, it will be returned directly -1
            return -1;
        }
        if(Pos<0||Pos>this.usedSize-1) {
    //pos Illegal location , Go straight back to -1（ Legal location range [0,this.usedSize-1]）
            return -1;
        }
        return this.elem[Pos];
    }

6. to pos The element of the position is set to

    private boolean isEmpty() {
    
        return this.usedSize == 0;
    }
	public void setPos(int pos, int value) {
    
        if(pos < 0 || pos >= this.usedSize) {
    
            System.out.println("pos illegal ！");
            return;
        }
        if(isEmpty()) {
    
            System.out.println(" Sequence table is empty ！");
            return;
        }
        this.elem[pos] = value;
    }

7. Delete the first keyword

    private boolean isEmpty() {
    
        return this.usedSize == 0;
    }
	public void remove(int toRemove) {
    
        if(isEmpty()) return;
        int index = this.search(toRemove);//search Method in 4 To realize 
        if(index == -1) {
    
            System.out.println(" There are no numbers you want to delete ");
            return;
        }
        for (int i = index; i < this.usedSize-1; i++) {
    // The data behind the keyword moves forward as a whole , Cover it up 
            this.elem[i] = this.elem[i+1];
        }
        this.usedSize--;
    }

8. Get the length of the order table

    public int size() {
    
        return this.usedSize;
    }

9. Clear the sequence table

    public void clear() {
    
        this.elem=null;//JVM When reclaiming memory , When no one is referencing the object , This object will be recycled , take this.elem Set to empty , Then the array will have no object references , Automatically JVM Recycling 
        this.usedSize = 0;
    }

3. ArrayList

ArrayList The ground floor is a continuous space , And it can be dynamically expanded , In fact, it is a dynamic type sequence table

3.1 ArrayList Construction

Method	explain
ArrayList()	No arguments structure
ArrayList(Collection<? extends E> c)	Using others Collection structure ArrayList
ArrayList(int initialCapacity)	Specify the initial capacity of the sequence table

Code example ：

public static void main(String[] args) {
    
        // ArrayList establish , Recommend writing 
        //  Construct an empty list 
        List<Integer> list1=new ArrayList<>();
        List<Integer> list2=new ArrayList<>(10);
        list2.add(1);
        list2.add(2);
        list2.add(3);
        // list3 After construction , And list2 The elements in the are consistent 
        ArrayList<Integer> list3=new ArrayList<>(list2);
}

3.2 ArrayList Common operations

Most operating methods are similar to 2 The sequence table in is the same .

Method	explain
boolean add(E e)	Tail insertion e
void add(int index, E element)	take e Insert into index Location
boolean addAll(Collection<? extends E> c)	Tail insertion c The elements in
E remove(int index)	Delete index Location elements
boolean remove(Object o)	Delete the first o
E get(int index)	Get subscript index Location elements
E set(int index, E element)	Subscript index The location element is set to element
void clear()	Empty
boolean contains(Object o)	Judge o Is it in the linear table
int indexOf(Object o)	Return to the first o The subscript
int lastIndexOf(Object o)	Go back to the last o The subscript
List subList(int fromIndex, int toIndex)	Interception part list

3.3 ArrayList The traversal

ArrayList There are three ways to traverse ：for loop + Subscript 、foreach、 Using Iterators .

public static void main(String[] args) {
    
        List<Integer> list=new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        //for Loop traversal 
        for (int i = 0; i < list.size(); i++) {
    
            System.out.println(list.get(i)+" ");
        }
        System.out.println();
        for(Integer integer:list) {
    
            System.out.println(integer+" ");
        }
        System.out.println();
        // Iterator traversal 
        Iterator<Integer> it=list.listIterator();
        while (it.hasNext()) {
    
            System.out.println(it.next()+" ");
        }
        System.out.println();
}

The iterator acts as a line by line scan of the contents , Code it.next() The function of is to obtain the contents of the bank , And move to the next line .

3.4 ArrayList Capacity expansion mechanism of （ Source code analysis ）

 public static void main(String[] args) {
    
        ArrayList<Integer> list=new ArrayList<>();// The size of the sequential table is 0
        list.add(1);// The size changes to 10
        list.add(2);
        list.add(3);
        //........ When the ten slows down , Need to expand , The capacity expansion is 1.5 Times the capacity expansion method 
}

ArrayList Is a dynamically typed sequential table , namely ： During the process of inserting elements, the capacity will be expanded automatically ： Here are ArrayList Expansion method in the source code .

Let's see first ArrayList Construction method of ：

The size allocated to the array is 0, That is, at the beginning of instantiation , The array capacity is 0

Calling add When the method is used , It will judge whether to increase the capacity according to the current capacity （ If the capacity is increased 1.5 times ）

【 summary 】

1. Check whether capacity expansion is really needed , If it's a call to grow Ready to expand
2. Estimate the size of the required storage capacity
   The preliminary estimate is based on 1.5 Double size expansion
   If the user needs more than the estimated size 1.5 Multiple size , Then expand the capacity according to the size required by the user
   Before the real expansion, check whether the expansion is successful , Prevent too large to cause expansion failure
3. Use copyOf super-popular

4. Using examples （ Poker ）

A deck of cards （ Except big and small king ）, What we need to do now is to buy a card first , Shuffle the cards , Then three people take turns to touch five cards from the pile , This example is right ArrayList Summary and application of .

CardDemo class ：

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

class Card {
    
    public int rank;// Numbers 
    public String suit;// Design and color 

    public Card(int rank, String suit) {
    
        this.rank = rank;
        this.suit = suit;
    }

    // Rewrite the printing method   Numbers + Design and color 
    @Override
    public String toString() {
    
        return ""+suit+" "+rank;
    }
}
public class CardDemo {
    
    public static final String[] suits={
    "","","",""};

    /** *  How to buy poker  * @return  Poker  */
    public List<Card> buyDeskCard() {
    
        List<Card> cards=new ArrayList<>();
        //13 A digital , Each number has four different colors 
        for (int i = 1; i <=13 ; i++) {
    
            for (int j = 0; j < 4; j++) {
    
                Card card=new Card(i,suits[j]);
                cards.add(card);
            }
        }
        return cards;
    }

    /** *  Shuffle the cards  */
    public void shuffle(List<Card> cards) {
    
        for (int i = cards.size()-1; i >0 ; i--) {
    
            Random random=new Random();
            int index=random.nextInt(i);
            swap(cards,index,i);
        }
    }

    /** *  Swap two cards  * @param cards * @param i * @param j */
    private void swap(List<Card> cards,int i,int j) {
    
        Card tmp=cards.get(i);
        cards.set(i,cards.get(j));
        cards.set(j,tmp);
    }

    /** *  How to touch cards  * @param cards  Deck  * @return  The last touch card is cleared  */
    public List<List<Card>> test(List<Card> cards) {
    
        List<Card> hand1 = new ArrayList<>();
        List<Card> hand2 = new ArrayList<>();
        List<Card> hand3 = new ArrayList<>();
        List<List<Card>> hands = new ArrayList<>();
        hands.add(hand1);
        hands.add(hand2);
        hands.add(hand3);
        //3 personal   Everyone takes turns catching 5 card 
        for (int i = 0; i < 5; i++) {
    
            for (int j = 0; j < 3; j++) {
    
                //remove Method returns the first card in the stack , And will clear this card from the stack 
                Card card = cards.remove(0);
                hands.get(j).add(card);
            }
        }
        return hands;
    }
}

Test class ：

import java.util.List;

public class Test {
    
    public static void main(String[] args) {
    
        CardDemo cardDemo=new CardDemo();
        List<Card> ret=cardDemo.buyDeskCard();
        System.out.println(ret);
        System.out.println(" Shuffle ：");
        cardDemo.shuffle(ret);
        System.out.println(" Touch the card ：");
        List<List<Card>> ret2=cardDemo.test(ret);
        for (int i = 0; i < ret2.size(); i++) {
    
            System.out.println(" The first "+(i+1)+" Personal cards ："+ret2.get(i));
        }
        System.out.println(" The remaining cards :");
        System.out.println(ret);
    }
}

Running results ：

---

️ Last words ️

Summing up difficulties , hope uu Don't be stingy with your (＾Ｕ＾)ノ~ＹＯ！！ If there is a problem , Welcome comments and corrections in the comment area