[java数据结构篇]List,ArrayList,LinkedList的使用

一.List的使用

常用方法：

方法	解释
boolean add(E e)	尾插 e
void add(int index, E element)	将 e 插入到 index 位置
boolean addAll(Collection<? extends E> c)	尾插 c 中的元素
E remove(int index)	删除Index位置的元素
boolean remove(Object o)	删除list中的第一个o
E get(int index)	得到index位置的元素
E set(int index, E element)	设置list中下标为index位置的元素为element
void clear()	把整个list清空
boolean contains(Object o)	看看list中是否存在o
int lastIndexOf(Object o)	返回在list中遍历的最后一个o元素的下标
List<E> subList(int fromIndex, int toIndex)	在list中截取[frimIndex,toIndex)之间的元素。注意方法的返回值为是list
int Indexof(object o)	返回在list中遍历的第一个o元素的下标

代码演示：

案例一：

先用list建一个元素为整形的顺序表

boolean add(E e)方法

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

运行结果 [1,2,3]

案例二：

void add(int index, E element)

list.add(0,8);//在list中下标为0的位置上添加一个整形元素8
System.out.println(list);

运行结果：[8,1,2,3]

案例三：

boolean addAll(Collection<? extends E> c)

List<Integer>list1 = new ArrayList<>();
list1.add(12);
list1.add(45);
list.addAll(list1);
System.out.println(list);

注意在使用addAll()这个方法的时候，()中传进去的值必须是实现了Collection接口的，并且类型和原来中的list中添加的值的类型相同，如果不相同的话，就会报错。

运行结果为：[8,1,2,3,12,45]

案例四：
E remove(int index)

System.out.println(list);
list.remove(5);//删除list中下标为5的元素
System.out.println(list);
//运行结果：[8,1,2,3,12,45] [8,1,2,3,12]

案例五：
boolean remove(Object o)

list.add(12);
 System.out.println(list);
System.out.println(list.remove((Integer) 12));
System.out.println(list);
//运行结果： [8, 1, 2, 3, 12, 45, 12]
//true
//[8, 1, 2, 3, 45, 12]

案例六：
E get(int index)

System.out.println(list.get(0));//得到list下标为0的元素
//运行结果: 8

案例七：
E set(int index, E element)

list.set(0,25);
System.out.println(list);//把list中下标为0的元素改为25
//运行结果:[25,1,2,3,12,45,12]

案例八：
void clear()

list.clear();//起到清空list的作用
System.out.println(list);
//运行结果: []

案例九：
boolean contains(Object o)

System.out.println(list.contains(12));//在线性表list中是否存在12这个元素

案例十：
int lastIndexOf(Object o)

System.out.println(list);
System.out.println(list.lastIndexOf(12));//显示出在list中最后一个元素12所出现的位置，返回其下标
//运行结果：[25,1,2,3,12,45,12]
//6

案例十一：
List<E> subList(int fromIndex, int toIndex)

List<Integer>list2 = list.subList(2,5);
System.out.println(list2);
//在原有的线性表中截取一部分，返回一个子线性表，注意在原有的list当中截取的时候是左闭右开的去进行截取------[)
//运行结果：[2,3,12]

案例十二：
int Indexof(object o)

System.out.println(list);
System.out.println(list.indexOf(12));
//返回在线性表中第一个出进来的数字的下标---12
//运行结果：4

二.ArrayList的使用

相关构造方法的介绍：

方法	解释
ArrayList()	无参构造
ArrayList(Collection<?extends E> c)	利用其它Collection构建ArrayList
ArrayList< int iniaialCapicaly >	指定顺序表的初始容量

案例一：

ArrayList<Integer>list = new ArrayList<>()

案例二：

ArrayInteger>list == new ArrayList<>(10)//在这里初始化顺序表的初始为10

案例三：

ArrrayList<Integer>list = new ArrayList<>();
Arraylist.add(1);
Arraylist.add(2);
Arraylist<Integer> list1 = new ArrayList<>(list);
//这里在实例化一个list1的时候传进去了一个list，这个list必须的list1的数据类型相同。

关于ArrayList的初始容量分析：

首先当创建一个ArrayList顺序表的时候，查看源码。

按住Ctrl键，鼠标单击ArrayList,就进入到ArrayList.java文件，也就是关于ArrayList的源码。

可以发现这是在实现ArrayList的无参构造方法，这时候进入elementDate的定义，可以看到elementDate实则是一个数组，所以我们就可以断定ArrayList顺序表的底层使用数组实现的。

然后再进入DEFAULTCAPACITY_EMPTY_ELEMENTDATE发现该数组为空。

经过以上源码，可以断定ArrayList顺序表在实例化之后的容量为空。

既然ArrayList的初始容量为空，为什么不报异常呢？

看看下面对于他的add()方法的定义。可以看到数组的ensureCapacityInternal()方法有关，

然后进入ensureCapacityInternal()方法的定义，那么传进来的minCapacity又是多少呢？
在没有对size赋值之前size = 0;所以minCapacity的值为1.我们还可以知道在ensureCapacityInternal()方法的定义中，又调用ensureExplicitCapacity()方法，而这个方法的所传来的参数，是calculateCapacity(elementDate,minCapacity)方法的返回值.

然后进入calcuateCapacity()方法的定义，返回一个DEFAULT_CAPACITY和minCapacity之间的最大值。然后转DEFAULT_CAPACITY，看看它的大小是多少。

然后可以看到这个默认容量的大小为10.

所以说calculateCapacity()这个方法，返回一个10，然后转到ensureExplicitCapacity()的定义。在源码中，如果这个最小容量minCapacity大于数组elementData的长度，就执行grow()扩容方法。在这里minCapacity的大小为10，数组elementData的长度为0.

然后进入到grow()方法的定义。我们在这里看到newCapacity所接收的值是1.5倍扩容之后的。在这时，数组的长度还是0，所以此时的oldCapacity大小自然也为0，newCapacity的大小也为0，这是newCapacity小于minCapacity的大小。minCapacity的值就赋予了newCapacity,然后就进入到了Arrays.copyOf()方法，对数组进行扩容，扩容大小为newCapacity.

综上所述，可以得出结论，当实例化一个顺序表对象的时候，底层数组的初始容量为0，在执行到第一个add()方法的时候，实现了扩容，这时候底层数组的长度为10，在此之后如果要进行扩容，就是按1.5倍进行的。如果想要知道底层数组最多能够容纳多少元素，可以点到MAX_ARRAY_SIZE进行查明。

三.LinkedList的使用

LinkedList的简单介绍

LinkedList也是一个基s本的数据结构，它是一种线性表，但是它不和ArrayList相同，不是按下标进行遍历的，LiskedList是一个节点一个节点进行遍历的，它的底层是靠一个双向链表实现的。

这就有了有个几乎面试都会被提到的问题。那就是LinkedList和ArrayList的区别？

其实就是LinkedList的底层是用双向链表实现的，而ArrayList的底层使用数组实现的。

ArrayList这个数据结构，它的优点是可以快速的去访问元素，并对访问元素进行修改。

LinkedList既然是一个双向链表，它的优点在于能够更快的实现增加和删除。

关于LinkedList的构造方法：

方法	解释
LinkedList()	无参构造
LinkedList(Collection<?extends E>) c	利用其它Collection构建LInkedList

案例一：

LinkedList<Integer>list = new LinkedList<>()

案例二：

LinkedList<Integer> list1 = new LinkedList<>();
list1.add(2);
list1.add(3);
LinkedList<Integer> list2 = new LinkedList<>(list1);
System.out.println(list2);
//运行结果：[2,3]
//只有和list2类型相同的集合才能够传到LinkedList

四.代码练习题。

题目一：自定义一副扑克牌

要求显示所有的牌，洗牌，发牌(一共有三个人，一共有五轮)

//首先创建一个card，这个类中有着每一个牌所具有的属性，包括牌的面值，牌的花色
public class Card {
    private String suit;//牌的花色
    private int rank;//牌的面值

    public Card(String suit, int rank) {//对每一张牌进行初始化
        this.suit = suit;
        this.rank = rank;
    }

    @Override
    public String toString() {//因为要打印每张牌所以要重写Object类的抽象方法
        return suit + " " + rank;
    }
}
public class CardDemo{
    public static String []suits = {"♥","♦","♣","♠"};
    public static void swap(ArrayList<Card> cardList,int x,int y){//下标随机值的卡片元素，和对应i下标的元素之间进行交换
     Card temp = cardList.get(x);
     cardList.set(x,cardList.get(y));
     cardList.set(y,temp);
    }
    public static void stuffle(ArrayList<Card> cardList){
        //生成随机下标
        Random random = new Random();
        for(int i = cardList.size()-1;i > 0;i--) {
            int cardRand = random.nextInt(i);//生成随机下标在[0,i)之间
            swap(cardList,i,cardRand);
        }
    }
    public static void main(String[] args) {
        ArrayList<Card>cardList = new ArrayList<>();
        for(int i = 1 ;i<=13;i++){
            for(int j = 0;j<4;j++){
                Card card = new Card(suits[j],i);
                cardList.add(card);
            }
        }
        System.out.println(cardList);
        stuffle(cardList);
        System.out.println(cardList);
        //发牌
        ArrayList<Card> list1 = new ArrayList<>();//因为三个人中，每个人都会抽到牌，一个人抽到的牌，相当于一个list，这个list又组成了一个二维的ret,这个ret就是cardList中的所有卡片元素
        ArrayList<Card> list2 = new ArrayList<>();
        ArrayList<Card> list3 = new ArrayList<>();
        ArrayList<ArrayList<Card>> ret = new ArrayList<>();
        ret.add(list1);//每个一维的list添加到二维的ret中
        ret.add(list2);
        ret.add(list3);
        for(int i = 0;i<5;i++){
            for(int j = 0;j<3;j++){
                Card card = cardList.remove(0);//因为在cardList，每次在0下标删除一个元素，那么cardList的头元素就会被更新
                ret.get(j).add(card);//把从cradList中删除的牌，添加到每一个一维的list中
            }
        }
        System.out.println(list1);
        System.out.println(list2);
        System.out.println(list3);
    }
}
//运行结果：
//[♥ 1, ♦ 1, ♣ 1, ♠ 1, ♥ 2, ♦ 2, ♣ 2, ♠ 2, ♥ 3, ♦ 3, ♣ 3, ♠ 3, ♥ 4, ♦ 4, ♣ 4, ♠ 4, ♥ 5, ♦ 5, ♣ 5, ♠ 5, ♥ 6, ♦ 6, ♣ 6, ♠ 6, ♥ 7, ♦ 7, ♣ 7, ♠ 7, ♥ 8, ♦ 8, ♣ 8, ♠ 8, ♥ 9, ♦ 9, ♣ 9, ♠ 9, ♥ 10, ♦ 10, ♣ 10, ♠ 10, ♥ 11, ♦ 11, ♣ 11, ♠ 11, ♥ 12, ♦ 12, ♣ 12, ♠ 12, ♥ 13, ♦ 13, ♣ 13, ♠ 13]
//[♦ 7, ♦ 8, ♥ 4, ♣ 4, ♥ 10, ♥ 7, ♠ 9, ♦ 12, ♦ 10, ♣ 3, ♠ 11, ♣ 9, ♣ 11, ♠ 6, ♠ 3, ♥ 9, ♠ 10, ♥ 5, ♠ 13, ♠ 7, ♦ 6, ♠ 12, ♠ 5, ♣ 12, ♥ 13, ♦ 9, ♦ 13, ♣ 1, ♦ 1, ♥ 12, ♣ 10, ♣ 8, ♦ 3, ♠ 4, ♥ 8, ♦ 4, ♣ 13, ♠ 2, ♣ 7, ♥ 2, ♦ 5, ♠ 8, ♥ 11, ♣ 2, ♥ 3, ♥ 1, ♦ 2, ♠ 1, ♣ 6, ♣ 5, ♦ 11, ♥ 6]
//[♦ 7, ♣ 4, ♠ 9, ♣ 3, ♣ 11]
//[♦ 8, ♥ 10, ♦ 12, ♠ 11, ♠ 6]
/[♥ 4, ♥ 7, ♦ 10, ♣ 9, ♠ 3]

题目二：现在计算机学院有若干名学生，学生的基本信息有姓名String类型,班级String类型，成绩Double类型，现在要把 每个学生的基本信息加到List中，然后遍历List，输出每个学生的信息。

//先实现一个学生类，在这个类里边存放一个人的信息
public class Student {
    private String name;
    private String classes;
    private int score;
    //因为要添加学生的基本信息，所以要对学生的属性进行初始化，所以要实现一个Student的构造方法
    public Student(String name, String classes, int score) {
        this.name = name;
        this.classes = classes;
        this.score = score;
    }
   //因为要打印学生的基本信息，所以在这里重写Object的抽象方法
    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", classes='" + classes + '\'' +
                ", score=" + score +
                '}';
    }
}
public class TestDemo {
    public static void main(String[] args) {
        ArrayList<Student>list = new ArrayList<>();
        list.add(new Student("张三","2",99));
        list.add(new Student("李四","3",100));
        list.add(new Student("王五","1",98));
        for(Student student : list){
            System.out.println(student);
        }
    }
}
//运行结果：
//Student{name='张三', classes='2', score=99}
//Student{name='李四', classes='3', score=100}
//Student{name='王五', classes='1', score=98}

题目三：有一个List中存放的是整型数据，现在使用Collection.sort()方法进行对list排序。

 public static void main(String[] args) {
        ArrayList<Integer>list = new ArrayList<>();
        list.add(1);
        list.add(-1);
        list.add(5);
        list.add(78);
        Collections.sort(list);
        System.out.println(list);
    }
//运行结果：[-1,1,5,78]
//如果要对学生的基本信息进行排序，就要重写Comparator接口中的competeto方法。

题目四：有两个字符串String str1 = “welcome to bit”,String str2 = “come”，现在要在str1中其删除str2中所具有的所有字符。

//代码思想：遍历str1字符串中的每个字符，如果str2中不存在这个字符，那么就把这个字符加入到list中
public static void main(String[] args) {
        String str1 = "welcome to bit";
        String str2 = "come";
        ArrayList<Character>list = new ArrayList<>();
        for(int i = 0;i<str1.length();i++){
            if(!str2.contains(str1.charAt(i) + "")){
                list.add(str1.charAt(i));
            }
        }
        for(char ch : list){
            System.out.print(ch);
        }
    }

题目五：杨辉三角

让我们康康什么是杨辉三角！

//如上图所示：杨辉三角相当与一个二维的list，每一行的第一列和最后一列都是1，中间元素等于中间与中间元素正对着上一行的元素和斜上角的一个元素之和。
public List<List<Integer>> generate(int numRows) {
        List<List<Integer>>ret = new ArrayList