主要讲的是collection arraylist  linkedlist

 

   

Collection:

集合的*接口

java.util

接口定义：

public interface Collection<E> extends Iterable<E>{}

接口不能创建对象，间接的实现类ArrayList;

接口支持向上造型：

 Collection<Integer> ages = new ArrayList<Integer>();

创建ArrayList集合的对象 赋值给Collection接口类型的引用

<Integer>：泛型 表示当前集合只能存储整数类型的元素

方法：

1.boolean add(E e)

将元素添加到集合

E表示数据类型 需要和声明Collection时指定的元素的类型一致

2.boolean addAll(Collection<? extends E> c)

将参数集合中的元素添加到当前集合中

3.void clear()

清空集合

4.boolean contains(Object o)

判断集合中是否参数元素

5.boolean containsAll(Collection<?> c)

判断当前集合中是否包含参数集合的所有元素

6.boolean equals(Object o)

判断当前集合与参数元素是否相等

7.boolean isEmpty()

元素的个数=0，则返回true

8.boolean remove(Object o)

删除一个指定的元素

如果集合中有重复的元素 则只删除第一个指定的元素

9.boolean removeAll(Collection<?> c)

将参数集合中在当前集合中出现的所有元素都删除掉

10.int size()

获取集合中元素的个数

11.Object[] toArray()

将集合转为数组

 

集合的遍历：

1、将集合转为数组，遍历数组的方式来遍历集合

toArray()

2、foreach-增强for循环

3、迭代器来完成遍历

 

 

练习：

1、定义一个集合来存储字符串类型的元素 添加元素 删除 遍历

2、定义一个集合，每个元素都是一个Student对象，添加3个元素

来完成遍历操作

 

面试题：

集合和数组的区别：

1、集合长度可变，数组长度一旦定义不能修改

2、集合可以存储不同数据类型的元素，数组只能存储同一个数据类型的元素；但是通常集合再使用时会通过指定泛型来约束元素的数据类型；

3、集合只能存储引用数据类型

     数组可以存储引用数据类型也可以存储基本数据类型

JDK1.5开始支持自动装箱和自动拆箱

 

 

list

所属包：java.util

接口定义：

public interface List<E> extends Collection<E>{}

实现类：

ArrayList   LinkedList  Vector

特点：

有序的(保证元素的插入顺序)，通过索引位置

允许元素重复

List接口继承了Collection接口的部分方法，也增加了自己所特有的方法

索引：0=<index<size

方法：

void add(int index, E element)

在指定的位置插入数据

如果指定的为止已经有元素存在，则会先将该位置以及其之后的元素集体先后挪以为，再将要插入的元素放到该位置；

E get(int index)

获取指定位置出的元素值并返回

int indexOf(Object o)

返回此列表中第一次出现的指定元素的索引

equals比较相等

如果集合中没有o元素则返回-1

int lastIndexOf(Object o)

返回此列表中追后一次出现的指定元素的索引

equals比较相等

如果集合中没有o元素则返回-1

E remove(int index)

删除索引值处的元素

E set(int index,E element)

修改指定索引元素的值

List<E> subList(int fromIndex,

                int toIndex)

截取子集合

左闭右开

常见应用：

遍历List

1、通过索引来操作 普通循环for  while

2、foreach-增强循环

练习：

1、List存储Teacher类的对象 遍历打印

2、新插入一个元素，如果该元素已经存在，则不添加；不存在则新增该元素

contains--判断元素是否已经存在

底层时调用equals方法来判断对象是否相等

如果判断的对象是自定义数据类型，默认equals方法实从Object中继承过来，是比较对象地址值；

如果需要根据对象的属性来判断是否相等，需要重写equals方法

 

 

ArrayList:

类 实现了List接口，所以具备List和Collection接口的方法实现；

基于数组来实现，因为数组一旦创建，长度不可变；

所以ArrayList有容量的概念，这里的容量指的就是数组的长度；

随着不断向ArrayList中增加存储元素，会触发底层数组的扩容操作；

 

构造方法：

ArrayList()

          构造一个初始容量为 10 的空列表

ArrayList(int initialCapacity)

          构造一个具有指定初始容量的空列表

方法：

add(Obejct obj)

 public boolean add(E e) {

        //判断是否需要扩容

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

        elementData[size++] = e;//将当前添加的元素赋值给数组对应下表的元素

//size表示当前集合包含的元素的个数

        return true;

    }

扩容的方法

private void grow(int minCapacity) {

        // 原容量=10

        int oldCapacity = elementData.length;

//新容量=10+10>>1=10+5=15

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

        // 创建新的数组 完成数组扩容 并将新数组赋值给原数组

        elementData = Arrays.copyOf(elementData, newCapacity);

    }

 

扩容：

x<<y: x*2^y

x>>y:x/2^y

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

ArrayList每次扩容原容量的一半

第一次扩容： 原容量：10  扩容之后：15

第二次扩容： 原容量：15  扩容之后：22

第三次扩容： 原容量：22  扩容之后：33

…

 

数组实现ArrayList的原理：

数组的数据结构：连续的内存空间，长度不可变

增删操作，效率较低

查询操作，效率较高

 

问题：

1、什么时候不用指定初始化容量，什么时候最好在创建集合时来指定初始化容量？

当使用集合元素较多时，且大致元素个数的大致范围的情况下，建议使用有参构造指定初始化容量来创建列表；这样的话可以避免频繁扩容，提高效率；

如果不确定元素个数，可以使用无参构造来创建

练习：

年会，活动：

乒乓球：好老师  王老师

台球：肖老师  曹老师 朴老师

唱歌：李老师  好老师

统计所有参与活动老师的名单

 

LinkedList：

是List接口的实现类

是List接口的实现类

基于链表的数据结构，链表内存空间不连续；

 底层实现原理：

总结：

链表查询慢 增删快

单向链表：

只存储下一个元素的地址

单向查找

双向链表：

同时存储上一个元素的地址和下一个元素的地址

双向查找