数据结构入门到入土——ArrayList与顺序表

注意：

        1. ArrayList 最长使用的遍历方式是： for 循环 + 下标 以及 foreach

        2. 迭代器是设计模式的一种，后序容器接触多了再给大家铺垫

ArrayList是一个动态类型的顺序表，即：在插入元素的过程中会自动扩容。以下是ArrayList源码中扩容方式。

Object[] elementData; // 存放元素的空间

private static fifinal Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认空间

private static fifinal int DEFAULT_CAPACITY = 10; // 默认容量大小

public boolean add(E e) {

ensureCapacityInternal(size + 1); // Increments modCount!!

elementData[size++] = e;

return true;

}

private void ensureCapacityInternal(int minCapacity) {

ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

}

private static int calculateCapacity(Object[] elementData, int minCapacity) {

if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

return Math.max(DEFAULT_CAPACITY, minCapacity);

}

return minCapacity;

}

private void ensureExplicitCapacity(int minCapacity) {

modCount++;

// overflflow-conscious code

if (minCapacity - elementData.length > 0)

grow(minCapacity);

}

private static fifinal int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {

// 获取旧空间大小

int oldCapacity = elementData.length;

// 预计按照1.5倍方式扩容

int newCapacity = oldCapacity + (oldCapacity >> 1);

// 如果用户需要扩容大小 超过 原空间1.5倍，按照用户所需大小扩容

if (newCapacity - minCapacity < 0)

newCapacity = minCapacity;

// 如果需要扩容大小超过MAX_ARRAY_SIZE，重新计算容量大小

if (newCapacity - MAX_ARRAY_SIZE > 0)

newCapacity = hugeCapacity(minCapacity);

// 调用copyOf扩容

elementData = Arrays.copyOf(elementData, newCapacity);

}

private static int hugeCapacity(int minCapacity) {

// 如果minCapacity小于0，抛出OutOfMemoryError异常

if (minCapacity < 0)

throw new OutOfMemoryError();

return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;

}

【总结】

1. 检测是否真正需要扩容，如果是调用grow准备扩容

2. 预估需要库容的大小

•   初步预估按照1.5倍大小扩容

•   如果用户所需大小超过预估1.5倍大小，则按照用户所需大小扩容

•   真正扩容之前检测是否能扩容成功，防止太大导致扩容失败

3. 使用copyOf进行扩容

五，ArrayLisit的具体使用

杨辉三角

class Solution {
    //求杨辉三角方法
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<>();//二维数组
        List<Integer> list = new ArrayList<>();
        list.add(1);
        ret.add(list);
        for (int i = 1; i < numRows; i++) {
            List<Integer> curRow = new ArrayList<>();//当前行
            List<Integer> prevRow = ret.get(i-1);//上一行
            curRow.add(1);//当前行首个元素为1
            for (int j = 1; j < i; j++) {
                int val = prevRow.get(j-1) + prevRow.get(j);
                curRow.add(val);
            }
            curRow.add(1);//当前行最后一个元素为1
            ret.add(curRow);
        }
        return ret;
    }
}
public class Test {
    //方法使用
    public static void main(String[] args) {
        Solution solution = new Solution();
        List<List<Integer>> mylist = new ArrayList<>();
        mylist = solution.generate(3);
        for (int i = 0; i < 3; i++) {
            List<Integer> arr = mylist.get(i);
            System.out.println(arr);
        }
    }
}

洗牌系统：

Card类：

public class Card implements Comparable{
    @Override
    public int compareTo(Object o) {
        return 0;
    }

    private String suit;//花色
    private String rank;//数字

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

    public Card(String rank) {
        this.rank = rank;
    }
    public String getSuit() {
        return suit;
    }

    public void setSuit(String suit) {
        this.suit = suit;
    }

    public String getRank() {
        return rank;
    }

    public void setRank(String rank) {
        this.rank = rank;
    }

    @Override
    public String toString() {
        return (suit == null) ? rank : suit + rank;
    }
}

cardDemo类（各方法实现）

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

public class CardDemo {
    public final String[] suits = {"♥", "♠", "♦", "♣"};
    public final String[] ranks = {"3", "4", "5",
            "6", "7", "8",
            "9", "10", "J",
            "Q", "K", "A", "2", "👸", "🤴"};

    public List<Card> buyCard() {
        List<Card> cardList = new ArrayList<>();
        for (int i = 0; i < 13; i++) {
            for (int j = 0; j < 4; j++) {
                Card card = new Card(suits[j], ranks[i]);
                cardList.add(card);
            }
        }
        for (int i = 13; i < 15; i++) {
            Card card = new Card(ranks[i]);
            cardList.add(card);
        }
        return cardList;
    }

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

    private void swap(List<Card> cards, int a, int b) {
        Card tmp = cards.get(a);
        cards.set(a, cards.get(b));
        cards.set(b, tmp);
    }

    public List<List<Card>> getCard(List<Card> cardList) {
        List<Card> player1Cards = new ArrayList<>();
        List<Card> player2Cards = new ArrayList<>();
        List<Card> player3Cards = new ArrayList<>();
        List<Card> landlordCards = new ArrayList<>();
        List<List<Card>> cards = new ArrayList<>();
        cards.add(player1Cards);
        cards.add(player2Cards);
        cards.add(player3Cards);
        cards.add(landlordCards);
        Random random = new Random();
        int[] array = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 17};
        //第一轮发flag张牌
        int flag = random.nextInt(14);
        //最后一轮发牌数
        int lastCards = (cardList.size() - flag * 3 - 3) / 3;
        //发第一轮玩家手牌
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < flag; j++) {
                cards.get(i).add(cardList.get(0));
                cardList.remove(0);
            }
        }
        //发底牌三张
        for (int i = 0; i < 3; i++) {
            cards.get(3).add(cardList.get(0));
            cardList.remove(0);
        }
        //最后一轮发牌
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < lastCards; j++) {
                cards.get(i).add(cardList.get(0));
                cardList.remove(0);
            }
        }
        return cards;
    }

    //查看发的牌
    public void ViewCards(List<List<Card>> cards) {
        for (int i = 0; i < 3; i++) {
            System.out.println("玩家" + (i + 1) + "手牌如下：");
            System.out.println(cards.get(i));
        }
        System.out.println("底牌如下：");
        System.out.println(cards.get(3));
    }

    //排序
    //使用compareTo比较，小为正，大为负
    public List<List<Card>> handSort(List<List<Card>> cards) {
        for (int i = 0; i < 4; i++) {
            List<Card> tmp = bubbleSort(cards.get(i));
            cards.set(i,tmp);
        }
        return cards;
    }

    private List<Card> bubbleSort(List<Card> cards) {
        //为手牌排序
        for (int i = 0; i < cards.size(); i++) {
            Card tmp = new Card("♠","3");
            for (int j = 0; j < cards.size() - i- 1; j++) {
                Card card1 = cards.get(j);
                Card card2 = cards.get(j + 1);
                if (war(card1.getRank(),card2.getRank()) < 0) {
                    tmp.setRank(card1.getRank());
                    tmp.setSuit(card1.getSuit());
                    card1.setRank(card2.getRank());
                    card1.setSuit(card2.getSuit());
                    card2.setRank(tmp.getRank());
                    card2.setSuit(tmp.getSuit());
                }
            }
        }
        return cards;
    }
    private int war(String num1,String num2) {
        String[] sortSamples = new String[]{"3","4","5","6","7","8","9","10","J","Q","K","A","2","👸","🤴"};
        int ret1 = 0;
        int ret2 = 0;
        for (int i = 0; i < sortSamples.length; i++) {
            if (num1.equals(sortSamples[i])) {
                ret1 = i;
            }
            if (num2.equals(sortSamples[i])) {
                ret2 = i;
            }
        }
        return ret1 - ret2;//num1大则为正
    }
}

Test类（运行测试）

import java.awt.*;
import java.util.List;

public class Test {
    static void display(List<Card> cardList) {
        for (int i = 0; i < cardList.size(); i++) {
            System.out.print(cardList.get(i) + " ");
            if (i != 0 && (i + 1)% 4 == 0) {
                System.out.println(" ");
            }
        }
        System.out.println(" ");
    }
    public static void main(String[] args) {
        CardDemo cardDemo = new CardDemo();
        List<Card> cardList= cardDemo.buyCard();
        System.out.println("买的牌如下：");
        display(cardList);
        System.out.println("==========");
        System.out.println("洗牌");
        cardDemo.shuffle(cardList);
        System.out.println("洗的牌如下：");
        display(cardList);
        System.out.println("==========");
        List<List<Card>> cards = cardDemo.getCard(cardList);
        cardDemo.ViewCards(cards);
        System.out.println("===========");
        System.out.println("整理过后的牌如下：");
        cardDemo.handSort(cards);
        cardDemo.ViewCards(cards);
    }
}

测试结果：

---

完。