java -数据结构，List相关基础知识，ArrayList的基本使用，泛型的简单、包装类介绍

一、 预备知识-泛型(Generic)

1.1、泛型的引入

比如：我们实现一个简单的顺序表

class MyArrayList{public int[] elem;public int usedSize;public MyArrayList(){this.elem = new int[10];}public void add(int key){this.elem[usedSize] = key;usedSize++;}public int getPos(int pos){return this.elem[pos];}
}

问题：此时我么发现我们实现的顺序表，只能保存 int 类型的元素，如果现在需要保存 指向 Person 类型对象的引用的顺序表，请问应该如何解决？如果又需要保存指向 Book 对象类型的引用呢？

泛型的意义

1、当我们指定数据类型之后，它会在编译器编译的时候，就帮你检查存储的数据类型是否匹配。自动对数据类型进行检查。
2、在我们获取元素的时候，发现数据类型不匹配，此时就会自动的将类型转换成相同类的数据。自动对类型进行强转类型转换。

下面顺序表的写法是不对的，只是为了暂时的用起来

class MyArrayList<E>{public E[] elem;public int usedSize;public MyArrayList(){this.elem = (E[])new Object[10];}public void add(E key){this.elem[usedSize] = key;usedSize++;}public E getPos(int pos){return  this.elem[pos];}
}

面试问题:泛型是怎么编译的?

1.泛型是编译期的一种机制（擦除机制)。
擦除机制:它会把尖括号这些内容擦除掉，也就说程序运行的时候，就没有这些东西了。所以说程序运行起来，再去获取它的类型是不可能的，因为都被擦掉了。

然后我们再来看一下细节

1.2、泛型的总结

1. 泛型是为了解决某些容器、算法等代码的通用性而引入，并且能在编译期间做类型检查。
2. 泛型利用的是 Object 是所有类的祖先类，并且父类的引用可以指向子类对象的特定而工作。
3. 泛型是一种编译期间的机制，即 MyArrayList< Person > 和 MyArrayList< Book > 在运行期间是一个类型。
4. 泛型是 java 中的一种合法语法，标志就是尖括号 <>

二、预备知识-包装类(Wrapper Class)

Object 引用可以指向任意类型的对象，但有例外出现了，8 种基本数据类型不是对象，那岂不是刚才的泛型机制要
失效了？
实际上也确实如此，为了解决这个问题，java 引入了一类特殊的类，即这 8 种基本数据类型的包装类，在使用过程
中，会将类似 int 这样的值包装到一个对象中去。

2.1、基本数据类型和包装类直接的对应关系

基本就是类型的首字母大写，除了 Integer 和 Character

2.2、包装类的使用，装箱(boxing)和拆箱(unboxing)

例如：此时我们将一个字符串类型的数据转换成int类型的数据

public static void main(String[] args) {String str = "123";int b =  Integer.valueOf(str);System.out.println(b + 11);}

什么是装包和拆包

• 装箱，装包： 就是将基本数据类型的数据转换成包装类类型 的数据
• 拆箱，拆包：就是将包装类类型的数据转换成基本数据类型的数据

阿里面试题，和装包和拆包有关

下面执行结果为什么会不相等？？？

public static void main(String[] args) {Integer a = 129;Integer b = 129;System.out.println("是否相等: " + (a == b));}

为什么？？？

三、List的使用

3.1、ArrayList 和 顺序表

List是一个接口，不能实例化，但是可以实例一个就提的对象，也可以通过具体的类来实例具体的对象

public static void main(String[] args) {List<String> list = new ArrayList<>();ArrayList<String> arrayList = new ArrayList<>();}

下面的这张图是ArrayList实现的接口和继承的抽象类，但是这张图并不具体

下面这张图才是ArrayList具体实现的接口和类

【说明】

1. ArrayList实现了RandomAccess接口，表明ArrayList支持随机访问
2. ArrayList实现了Cloneable接口，表明ArrayList是可以clone的
3. ArrayList实现了Serializable接口，表明ArrayList是支持序列化的
4. 和Vector不同，ArrayList不是线程安全的，在单线程下可以使用，在多线程中可以选择Vector或者CopyOnWriteArrayList
5. ArrayList底层是一段连续的空间，并且可以动态扩容，是一个动态类型的顺序表

3.2、ArrayList 的构造方法

在只用java中的类库时，一定要先看一下类库中的构造方法

public static void main(String[] args) {//不带参数的构造方法，默认大小为0List<String> list1 = new ArrayList<>();//带一个参数的构造方法，大小为10List<String> list2 = new ArrayList<>(10);//将list2作为参数传递，但是list2和list3里面存储的数据类型必须一致List<String> list3 = new ArrayList<>(list2);}

ArrAyList的三种打印方式

1. 直接打印

public static void main(String[] args) {List<String> list1 = new ArrayList<>();list1.add("hello");list1.add("word");list1.add("!!!");System.out.println(list1);}

2. 使用for和for-each循环打印

ArrayList本质上是一个数组，所以可以使用for循环打印，当然也可以使用for-each打印

public static void main(String[] args) {List<String> list1 = new ArrayList<>();list1.add("hello");list1.add("word");list1.add("!!!");for (String str : list1) {System.out.println(str + " ");}}

3. 迭代器打印

public static void main(String[] args) {List<String> list = new ArrayList<String>();list.add("123");list.add("hello");list.add("baidu");Iterator<String> iterator = list.iterator();while(iterator.hasNext()){System.out.println(iterator.next() + " ");}}

4、用于List相关的迭代器打印

List<String> list = new ArrayList<String>();list.add("123");list.add("hello");list.add("baidu");ListIterator<String> it = list.listIterator();while (it.hasNext()){System.out.println(it.next() + " ");}

3.3、ArrayList的常用方法

3.3.1、boolean add(E e) - 添加元素

public static void main(String[] args) {List<String> list = new ArrayList<String>();list.add("123");list.add("hello");list.add("baidu");System.out.println(list);}

3.3.2、void add(int index, E element) - 在index位置添加元素E

public static void main(String[] args) {List<String> list = new ArrayList<String>();list.add("123");list.add("hello");list.add("baidu");list.add(1,"++++");System.out.println(list);}

3.3.3、boolean addAll(Collection<? extends E> c) - 尾插对象e（e是和ArrayList一样的对象）

相当于在顺序表后面在插入一个顺序表

public static void main(String[] args) {List<String> list = new ArrayList<String>();list.add("123");list.add("hello");list.add("baidu");List<String> list1 = new ArrayList<String>();list1.add("*****");list1.add("888");list.addAll(list1);System.out.println(list);}

3.3.4、E remove(int index) - 删除index位置的元素

public static void main(String[] args) {List<String> list = new ArrayList<String>();list.add("123");list.add("hello");list.add("baidu");System.out.println(list);list.remove(1);System.out.println(list);}

3.3.5、boolean remove(Object o) - 删除第一次遇见的元素

public static void main(String[] args) {List<String> list = new ArrayList<String>();list.add("a");list.add("b");list.add("b");list.add("c");boolean b = list.remove("b");System.out.println(list);}

3.3.6、E get(int index) - 获取index位置的元素

public static void main(String[] args) {List<String> list = new ArrayList<String>();list.add("a");list.add("b");list.add("b");list.add("c");String str = list.get(2);System.out.println(str);System.out.println(list);}

3.3.7、E set(int index, E element) - 将index位置的元素设置成element

public static void main(String[] args) {List<String> list = new ArrayList<String>();list.add("a");list.add("b");list.add("b");list.add("c");String str = list.set(2,"***");System.out.println(str);System.out.println(list);}

3.3.8、void clear() - 清空ArrayList

public static void main(String[] args) {List<String> list = new ArrayList<String>();list.add("a");list.add("b");list.add("b");list.add("c");System.out.println(list);list.clear();System.out.println(list);}

3.3.9、boolean contains(Object o) - 判断一个元素是否存在

public static void main(String[] args) {List<String> list = new ArrayList<String>();list.add("a");list.add("b");list.add("b");list.add("c");boolean ret = list.contains("b");System.out.println(ret);System.out.println(list);}

3.3.10、int indexOf(Object o) - 返回第一个o 的下表

public static void main(String[] args) {List<String> list = new ArrayList<String>();list.add("a");list.add("b");list.add("b");list.add("b");list.add("c");int ret = list.indexOf("b");System.out.println(ret);System.out.println(list);}

3.3.11、int lastIndexOf(Object o) - 返回最后一个o 的下表

public static void main(String[] args) {List<String> list = new ArrayList<String>();list.add("a");list.add("b");list.add("b");list.add("b");list.add("c");int ret = list.lastIndexOf("b");System.out.println(ret);System.out.println(list);}

3.3.11、List subList(int fromIndex, int toIndex) - 截取部分list

public static void main(String[] args) {List<String> list = new ArrayList<String>();list.add("a");list.add("b");list.add("A");list.add("M");list.add("c");List<String> sub = list.subList(1,3);System.out.println(sub);}

在截取的时候注意使用事项

四、ArrayList底层的扩容机制

得出结论：
1、如果ArrayList调用不带参数的构造方法，那么顺序表的大小为0，当第一次 add 的时候，整个数组的大小为10，当这10个放满的时候，开始扩容，以15倍的方式进行扩容。
2、如果调用指定容量大小的构造方法，那顺序表的大小就是指定的容量，如果放满了，还是以1.5倍的方式进行扩容。

五、模拟实现ArrayList

这次的实现就会比上次的更好一点，模拟源代码的实现

当创建好之后，顺序表里面的操作就按照下面的操作来写

add

在使用add函数的时候要注意，调用的 时候不带参数的构造方法，还是调用带参数的构造方法，如果满了就要扩容

public class MyArrayList<E> {private Object[] elementData;private int size;//代表有效的数据个数private static final int DEFAULT_CAPACITY = 10;private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE-8;public MyArrayList(){this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}public MyArrayList(int capacity) {//对参数进行判断if(capacity > 0){this.elementData = new Object[capacity];}else if(capacity == 0){this.elementData = new Object[0];}else {throw new IllegalArgumentException("初始化容量不能为负数");}}/*** 添加元素,添加的元素在数组的最后面，尾插* @param e* @return*/public boolean add(E e){//ensureCapacityInternal(size+1);elementData[size+1] = e;size++;return true;}private void ensureCapacityInternal(int minCapacity) {//计算出需要的容量int capacity = calculateCapacity(elementData,minCapacity);//拿着计算的容量，满了扩容，空的分配内存ensureExplicitCapacity(capacity);}private void ensureExplicitCapacity(int minCapacity) {if (minCapacity - elementData.length > 0)grow(minCapacity);}private void grow(int minCapacity) {int oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity);}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0)throw new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ? (Integer.MAX_VALUE) : (MAX_ARRAY_SIZE);}private static int calculateCapacity(Object[] elementData, int minCapacity) {//1、是否之前的elemenData 数组分配内存if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){return Math.max(DEFAULT_CAPACITY,minCapacity);}//2、分配过就返回+1的值return minCapacity;}
}

add(int index, E e) - 在指定位置插入元素

/*** 在index位置添加元素* @param index* @param e*/public void add(int index, E e) {//判断index位置是否合法rangeCheckForAdd(index);ensureCapacityInternal(size + 1);  // Increments modCount!!System.arraycopy(elementData, index, elementData, index + 1,size - index);elementData[index] = e;size++;}/*** 判断index位置是否合法* @param index*/private void rangeCheckForAdd(int index){if(index < 0 || index > size){throw new IndexOutOfBoundsException("index位置不合法");}}

remove（object o） - 删除第一次遇到的元素 o

/*** 删除第一次遇见的元素 0* @param o* @return*/public boolean remove(Object o) {if (o == null) {for (int index = 0; index < size; index++)if (elementData[index] == null) {fastRemove(index);return true;}} else {for (int index = 0; index < size; index++)if (o.equals(elementData[index])) {fastRemove(index);return true;}}return false;}/*** 移动元素* @param index*/private void fastRemove(int index) {int numMoved = size - index - 1;if (numMoved > 0)System.arraycopy(elementData, index+1, elementData, index,numMoved);elementData[--size] = null; // clear to let GC do its work}

就简单的实现几个功能

面试题 - CVTE 删除第一个字符串中出现的第二个字符串中的字符

删除第一个字符串中出现的第二个字符串中的字符
例如 ：
String str1= “welcome to cvte”
String str2= “come”
输出结果：wl t vte

我们遍历str1 ，看str2的字符是否在str1中，如果不在那就将这个字符放入ArrayList中，如果在那就不放进去

public static void main(String[] args) {String str1 = "welcome to cvte";String str2 = "come";ArrayList<Character> list = new ArrayList<>();for (int i = 0; i < str1.length(); i++) {char ch = str1.charAt(i);if(!str2.contains(ch+"")){list.add(ch);}}for (char ch : list) {System.out.print(ch);}}

ArrayList 实践案例 - 扑克牌

目的：
1.构造一副扑克牌
2.揭牌

class Card{private int rank;//数字private String suit;//花色public Card(String suit, int rank) {this.rank = rank;this.suit = suit;}public int getRank() {return rank;}public String getSuit() {return suit;}@Overridepublic String toString() {return "[ 花色 "+ this.suit +  " " + this.rank + " ]";}
}public class Dome {//构造一副牌，这副牌里面没有大小王//四个花色private static String[] suits = {"♥","♠","♣","♦"};private static ArrayList<Card> byCard(){ArrayList<Card> cards = new ArrayList<>();//每个花色匹配不同的数字，这样就创建好了一副牌for (int i = 0; i < 4; i++) {for (int j = 1; j <=13; j++) {
//                String suit = suits[i];
//                Card card = new Card(suit,j);
//                cards.add(card);cards.add(new Card(suits[i],j));}}return cards;}//牌创建好之后就要洗牌private static void shuFfle(ArrayList<Card> cards){// 牌数是52，数组下标就是51// 从最后一张牌开始，随机与 本身 或者 本身前面的任意一张牌 交换位置。// 这样的做交换性 比 从开头洗  的 打乱顺序的 效率 高。for (int i = cards.size()-1; i > 0 ; i--) {Random random = new Random();// 通过 Random的引用 random 去调用 nextInt() 方法。// random.nextInt() 方法，根据括号中的值，随机生成 0 ~ 括号中的值int rand = random.nextInt(i);swap(cards,i,rand);}}private static void swap(ArrayList<Card> cards,int i, int j){// 我们现在是面向对象，ArrayList虽然底层是一个数组，但是需要使用方法，才能操作数组的元素// 并不能像数组一样，直接操作// Card tmp = list[i];Card tmp = cards.get(i);// 获取 顺序表中，对应下标的元素// list[i] = list[j];cards.set(i,cards.get(j));// 将 j下标的元素，赋给 i 下标的元素，// list[j] = tmp;cards.set(j,tmp);}public static void main(String[] args) {ArrayList<Card> car = byCard();//创建牌System.out.println(car);shuFfle(car);//洗牌System.out.println(car);System.out.println("三个人轮流揭牌5张牌");ArrayList<ArrayList<Card>> hand = new ArrayList<>();ArrayList<Card> hand1 = new ArrayList<>();ArrayList<Card> hand2 = new ArrayList<>();ArrayList<Card> hand3 = 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++) {Card card = car.remove(0);hand.get(j).add(card);}}System.out.println("第一个人的牌：" + hand1);System.out.println("第二个人的牌：" + hand2);System.out.println("第三个人的牌：" + hand3);System.out.println("剩下的牌：" + car);}
}