(Java数据结构)ArrayList

ArrayList的构造方法

ArrayList()

ArrayList()
ArrayList<Integer> arrayList1=new ArrayList<>();

调用无参构造方法时，是没有分配内存的，那么数据是怎么放进去？

在调用无参构造方法，第一次调用add方法后，容量变成10

问题：add第11个的时候是怎么扩容的？

ArrayList(int initialCapacity)

ArrayList(int initialCapacity) 
ArrayList<Integer> arrayList2=new ArrayList<>(12);

ArrayList(Collection c)

ArrayList(Collection<? extends E> c) 
？只能传E或E的子类
ArrayList,并且实现了Collection接口的都可以,如LinkedList
例：
ArrayList<String> arrayList4=new ArrayList<>();
ArrayList<Integer> arrayList3=new ArrayList<>(arrayList4);
//err
//String不是Integer的子类

ArrayList的操作

remove()

ArrayList<Integer> arrayList1=new ArrayList<>();
arrayList1.add(1);
arrayList1.add(0,7);
System.out.println(arrayList1);
arrayList1.remove(new Integer(7));//引用类型
System.out.println(arrayList1);

[7, 1]
[1]

subList()

List<E> subList(int fromIndex, int toIndex) 
//左闭右开

public static void main(String[] args) {
        ArrayList<Integer> arrayList1=new ArrayList<>();
        arrayList1.add(1);
        arrayList1.add(2);
        arrayList1.add(3);
        arrayList1.add(4);
        arrayList1.add(5);
        List<Integer> ret=arrayList1.subList(1,3);
        System.out.println(ret);
}

[2, 3]

ret.set(0,99);
System.out.println(arrayList1);
System.out.println(ret);

[1, 99, 3, 4, 5]
[99, 3]

截取没有创建新数组，在原数组基础上修改

ArrayList的遍历

//使用迭代器
ArrayList<Integer> arrayList1=new ArrayList<>();
arrayList1.add(1);
arrayList1.add(2);
arrayList1.add(3);
arrayList1.add(4);
arrayList1.add(5);
Iterator<Integer> it=arrayList1.iterator();
//或Iterator it = list.listIterator();
//因为interface ListIterator extends Iterator
while(it.hasNext()){
    System.out.print(it.next()+" ");
}
System.out.println();

1 2 3 4 5 

Iterator.remove()

Iterator<Integer> it2=arrayList1.listIterator();
        while(it2.hasNext()){
            Integer i=it2.next();
            if(i==3) {
                it2.remove();
            }
        }
        System.out.println(arrayList1);

[1, 2, 4, 5]

练习题

1.

1.一个班有3名学生，这些学生的信息有姓名，年龄，分数。一直每个学生对象都在ArrayList当中存放，请输出每个学生的信息

import java.util.ArrayList;

class Student{
    private String name;
    private int age;
    private double score;

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public double getScore() {
        return score;
    }

    public void setScore(double score) {
        this.score = score;
    }

    public Student(String name, int age, double score) {
        this.name = name;
        this.age = age;
        this.score = score;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", age=" + age +
                ", score=" + score +
                '}';
    }
}
public class Test {
    public static void main(String[] args) {

        ArrayList<Student> arrayList=new ArrayList<>();
        arrayList.add(new Student("小王",10,19.9));
        arrayList.add(new Student("小宏",20,59.9));
        arrayList.add(new Student("小张",15,89.9));
        for (Student s:
             arrayList) {
            System.out.println(s);
        }

    }
}

对分数进行排序
class Student implements Comparable<Student> {
@Override
    public int compareTo(Student o) {
        return (int)(this.score-o.score);
    }
}
public static void main(String[] args) {
Collections.sort(arrayList);
        for (Student s:
                arrayList) {
            System.out.println(s);
        }
}

总结：1.可以指定存放自定义的类，2.可以对集合进行排序

2.

2.给你两个字符串，str1:"welcome to xx"  str2:"come"
请删除第一个字符串当中，出现的第二个字符串当中的字符。
结果：wl t xx
要求：请使用集合来完成，ArrayList

public static ArrayList<Character> func(String s1,String s2){
            ArrayList<Character> arrayList=new ArrayList<>();
        for (int i = 0; i < s1.length(); i++) {
            char ch=s1.charAt(i);
            if(!s2.contains(ch+"")){
                arrayList.add(ch);
            }
        }
        return arrayList;
    }

    public static void main(String[] args) {
        String str1="welcome to xx";
        String str2="come";
        ArrayList<Character> ret=func(str1,str2);
        for (int i = 0; i < ret.size(); i++) {
            System.out.print(ret.get(i));
        }
        System.out.println();
    }

3.简单的洗牌算法

去掉大小王，有52张牌，4个花色，每个花色13张牌

买牌：

//首先创建一个牌类
public class Poker {
    private String suit;
    private int rank;

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

    public String getSuit() {
        
        return suit;
    }

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

    public int getRank() {
        
        return rank;
    }

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

    @Override
    public String toString() {
        
        return suit+" "+rank;
    }
}

public class Pokers {
    public static final String[] SUITS={"♥","♠","♣","♦"};
    public static List<Poker> buyPokers(){
        List<Poker> pokerList=new ArrayList<>();
        for (int i = 0; i < 4; i++) {
            for (int j = 1; j <=13; j++) {
                String suit=SUITS[i];
                Poker poker=new Poker(suit,j);
                pokerList.add(poker);
            }
        }
        return pokerList;
    }
    public static void main(String[] args) {
        List<Poker> pokerList=buyPokers();
        System.out.println("买牌:"+pokerList);
        shuffle(pokerList);
        }
}

洗牌：

把有序的牌打乱

public static void shuffle(List<Poker> pokerList){
        Random random=new Random();
        for (int i = pokerList.size()-1; i>0; i--) {
            int index=random.nextInt(i);
            //生成随机数，[0,i)和i交换
            swap(pokerList,i,index);
        }
    }
public static void swap(List<Poker> pokerList,int i,int j){
        Poker tmp=pokerList.get(i);
        pokerList.set(i,pokerList.get(j));
        pokerList.set(j,tmp);
    }

揭牌

有3个人轮流揭牌，有5轮，最后3个人手里都有5张牌
类似于二维数组，3个人的手是一个数组，每一个手要存放5张牌也是一个数组。

        List<Poker> hand1=new ArrayList<>();
        List<Poker> hand2=new ArrayList<>();
        List<Poker> hand3=new ArrayList<>();
        List<List<Poker>> hand=new ArrayList<>();
        hand.add(hand1);
        hand.add(hand2);
        hand.add(hand3);
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 3; j++) {
                List<Poker> handTmp=hand.get(j);
                handTmp.add(pokerList.remove(0));
                //E remove(int index);返回值是删除的那个元素
            }
        }
        for (int i = 0; i < 3; i++) {
            System.out.println("第"+(i+1)+"个人的牌："+hand.get(i));
        }
        System.out.println("剩余的牌："+pokerList);

Java ArrayList remove() 方法
// 删除指定元素
arraylist.remove(Object obj)
// 删除指定索引位置的元素
arraylist.remove(int index)
返回值
如果传入元素，删除成功，则返回 true。
如果传入索引值，则返回删除的元素。

买牌:[♥ 1, ♥ 2, ♥ 3, ♥ 4, ♥ 5, ♥ 6, ♥ 7, ♥ 8, ♥ 9, ♥ 10, ♥ 11, ♥ 12, ♥ 13, ♠ 1, ♠ 2, ♠ 3, ♠ 4, ♠ 5, ♠ 6, ♠ 7, ♠ 8, ♠ 9, ♠ 10, ♠ 11, ♠ 12, ♠ 13, ♣ 1, ♣ 2, ♣ 3, ♣ 4, ♣ 5, ♣ 6, ♣ 7, ♣ 8, ♣ 9, ♣ 10, ♣ 11, ♣ 12, ♣ 13, ♦ 1, ♦ 2, ♦ 3, ♦ 4, ♦ 5, ♦ 6, ♦ 7, ♦ 8, ♦ 9, ♦ 10, ♦ 11, ♦ 12, ♦ 13]
洗牌:[♦ 6, ♠ 11, ♦ 10, ♠ 13, ♥ 13, ♦ 12, ♦ 5, ♥ 7, ♠ 1, ♦ 1, ♠ 7, ♣ 5, ♠ 6, ♥ 1, ♣ 12, ♠ 4, ♠ 12, ♠ 9, ♠ 10, ♥ 9, ♥ 2, ♠ 8, ♣ 1, ♦ 2, ♥ 8, ♠ 3, ♠ 2, ♦ 3, ♥ 10, ♦ 13, ♦ 9, ♥ 12, ♣ 3, ♦ 11, ♦ 8, ♥ 5, ♦ 4, ♣ 11, ♦ 7, ♥ 11, ♣ 7, ♣ 8, ♣ 4, ♣ 9, ♥ 4, ♣ 6, ♥ 6, ♥ 3, ♣ 10, ♣ 13, ♣ 2, ♠ 5]
第1个人的牌：[♦ 6, ♠ 13, ♦ 5, ♦ 1, ♠ 6]
第2个人的牌：[♠ 11, ♥ 13, ♥ 7, ♠ 7, ♥ 1]
第3个人的牌：[♦ 10, ♦ 12, ♠ 1, ♣ 5, ♣ 12]
剩余的牌：[♠ 4, ♠ 12, ♠ 9, ♠ 10, ♥ 9, ♥ 2, ♠ 8, ♣ 1, ♦ 2, ♥ 8, ♠ 3, ♠ 2, ♦ 3, ♥ 10, ♦ 13, ♦ 9, ♥ 12, ♣ 3, ♦ 11, ♦ 8, ♥ 5, ♦ 4, ♣ 11, ♦ 7, ♥ 11, ♣ 7, ♣ 8, ♣ 4, ♣ 9, ♥ 4, ♣ 6, ♥ 6, ♥ 3, ♣ 10, ♣ 13, ♣ 2, ♠ 5]

4.杨辉三角

类似于二维数组

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret=new ArrayList<List<Integer>>();
        for(int i=0;i<numRows;++i){
            List<Integer> row=new ArrayList<>();
            for(int j=0;j<=i;++j){
                if(j==0||j==i){
                    row.add(1);
                }else{
                    int num=ret.get(i-1).get(j)+ret.get(i-1).get(j-1);
                    row.add(num);
                }
            }
            ret.add(row);
        }
        return ret;
    }
}

for循环里面定义的变量循环外面用不了