手撕Java集合（一）——List集合-阿里云开发者社区

一、集合

集合主要分为两组（单列集合，双列集合）

单列集合：存放单个元素

Collection：两个重要的接口 List Set

ArrayList<String>arrayList=newArrayList<>();
arrayList.add("jack");
arrayList.add("tom");

双列集合：键值对的形式存元素K-V

Map

HashMap<String, Object>hashMap=newHashMap<>(64);
hashMap.put("NO1", "北京");
hashMap.put("NO2", "上海");

1.2、Conllection接口和常用方法

1.2.1、常用方法

add:添加单个元素
remove:删除指定元素
contains:查找元素是否存在
size:获取元素的个数
isEmpty:判断集合是否为空
clear:清空集合
addAll:添加多个元素
containsAll:查找多个元素是否都存在
removeAll:删除多个元素

/*** @author java小豪* @date 2022/6/8*/publicclassCollectionMethod {
publicstaticvoidmain(String[] args) {
List<Object>list=newArrayList<>();
// add:添加单个元素list.add("jack");
// list.add(new Integer(10))list.add(10);
list.add(true);
System.out.println("List="+list);
// remove:删除指定元素// 通过下标删除元素list.remove(0);
// 指定删除的元素list.remove(true);
System.out.println("List="+list);
// contains:查找元素是否存在System.out.println(list.contains("jack"));
// size:获取元素的个数System.out.println(list.size());
// isEmpty:判断集合是否为空System.out.println(list.isEmpty());
// clear:清空集合//list.clear();//System.out.println(list);// addAll:添加多个元素ArrayList<Object>arrayList=newArrayList<>();
arrayList.add("红楼梦");
arrayList.add("三国演义");
list.addAll(arrayList);
System.out.println(list);
// containsAll:查找多个元素是否都存在System.out.println(list.containsAll(arrayList));
// removeAll:删除多个元素list.add("聊斋");
list.removeAll(arrayList);
System.out.println(list);
    }
}

1.2.2、Conllection接口遍历元素方式

使用Iterator(迭代器)

/*** @author java小豪* @date 2022/6/8*/publicclassCollectionIterator {
publicstaticvoidmain(String[] args) {
Collection<Object>collection=newArrayList<>();
collection.add(newBook("三国演义", "罗贯中", 50));
collection.add(newBook("小李飞刀", "古龙", 70.0));
collection.add(newBook("红楼梦", "曹雪芹", 60.0));
//        System.out.println("collection = " + collection);// 得到迭代器Iterator<Object>iterator=collection.iterator();
// 使用while循环遍历集合while (iterator.hasNext()) {
Objectobj=iterator.next();
System.out.println("obj = "+obj);
        }
// 重置迭代器iterator=collection.iterator();
while (iterator.hasNext()) {
Objectobj=iterator.next();
System.out.println("obj = "+obj);
        }
    }
}
classBook {
privateStringname;
privateStringauthor;
privatedoubleprice;
publicBook(Stringname, Stringauthor, doubleprice) {
this.name=name;
this.author=author;
this.price=price;
    }
publicStringgetName() {
returnname;
    }
publicvoidsetName(Stringname) {
this.name=name;
    }
publicStringgetAuthor() {
returnauthor;
    }
publicvoidsetAuthor(Stringauthor) {
this.author=author;
    }
publicdoublegetPrice() {
returnprice;
    }
publicvoidsetPrice(doubleprice) {
this.price=price;
    }
@OverridepublicStringtoString() {
return"Book{"+"name='"+name+'\''+", author='"+author+'\''+", price="+price+'}';
    }
}

增强for循环：只能用来遍历集合和数组

基本语法：for(元素类型元素名 : 集合名或数组名) { 访问元素 }

/*** @author java小豪* @date 2022/6/8*/publicclassCollectionFor {
publicstaticvoidmain(String[] args) {
Collection<Object>collection=newArrayList<>();
collection.add(newBook("三国演义", "罗贯中", 50));
collection.add(newBook("小李飞刀", "古龙", 70.0));
collection.add(newBook("红楼梦", "曹雪芹", 60.0));
// 增强for// 增强for底层仍然是迭代器for (Objectbook : collection) {
System.out.println("book = "+book);
        }
// 增强for用在数组上int[] nums= {1, 6, 7, 9, 10};
for (inti : nums) {
System.out.println("i = "+i);
        }
    }
}

1.3、List接口和常用方法

1.3.1、介绍

1) List集合类中元素有序、且可重复

2) List集合中的每个元素有其对应的顺序索引，即支持索引。

3) List容器中的元素对应一个整数的序号记载在容器中的位置，可以根据序号取出容器中的元素.

/*** @author java小豪* @date 2022/6/9*/publicclassList_ {
publicstaticvoidmain(String[] args) {
// List集合类中元素有序、且可重复List<Object>list=newArrayList<>();
list.add("jack");
list.add("mary");
list.add("tom");
list.add("chen");
System.out.println("list = "+list);
// List集合中的每个元素有其对应的顺序索引，即支持索引。System.out.println(list.get(2));
    }
}

1.3.2、常用方法

void add(int index, Object ele):在index位置插入ele元素
boolean addAll(int index, Collection eles):从index位置开始将eles中的元素插入
Object get(int index):获取指定index位置的元素
int indexOf(Object obj):返回obj在当前集合中首次出现的位置
int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置
Object remove(int index):移除指定index位置的元素，并返回此元素
Object set(int index, Object ele):设置指定index位置元素为ele
List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的子集合

/*** @author java小豪* @date 2022/6/9*/publicclassListMethod {
publicstaticvoidmain(String[] args) {
List<Object>list=newArrayList<>();
//void add(int index, Object ele):在index位置插入ele元素list.add("张三丰");
list.add("李小龙");
// 在index = 1 的位置插入一个对象list.add(1, "宋江");
System.out.println("list = "+list);
//boolean addAll(int index, Collection eles):从index位置开始将eles中的元素插入List<Object>list2=newArrayList<>();
list2.add("jack");
list2.add("tom");
list.addAll(1, list2);
System.out.println("list = "+list);
//Object get(int index):获取指定index位置的元素System.out.println(list.get(3));
//int indexOf(Object obj):返回obj在当前集合中首次出现的位置System.out.println(list.indexOf("tom"));
//int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置list.add("tom");
System.out.println("list = "+list);
System.out.println(list.lastIndexOf("tom"));
//Object remove(int index):移除指定index位置的元素，并返回此元素list.remove(0);
System.out.println("List = "+list);
//Object set(int index, Object ele):设置指定index位置元素为ele,相当于是替换list.set(1, "玛丽");
System.out.println("List = "+list);
// List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的子集合// 返回子集合范围[fromIndex, toIndex)ListreturnList=list.subList(0, 2);
System.out.println("returnList = "+returnList);
    }
}

1.3.3、练习

添加十个以上的 String "hello"
在2号位插入一个元素
获取第6个元素
删除第7个元素
修改第8个元素
使用迭代器遍历集合

/*** @author java小豪* @date 2022/6/10*/publicclassListExercise {
publicstaticvoidmain(String[] args) {
List<Object>list=newArrayList<>();
// 添加十个以上的 String "hello"for (inti=0; i<12; i++) {
list.add("hello"+i);
        }
System.out.println("list = "+list);
// 在2号位插入一个元素"chen"list.add(1, "chen");
System.out.println("list = "+list);
// 获取第6个元素System.out.println("第6个元素 = "+list.get(5));
// 删除第7个元素list.remove(6);
System.out.println("list = "+list);
// 修改第8个元素list.set(7, "三国演义");
System.out.println("list = "+list);
// 使用迭代器遍历集合Iterator<Object>iterator=list.iterator();
while (iterator.hasNext()) {
Objectobj=iterator.next();
System.out.println("obj = "+obj);
        }
    }
}

1.3.4、List集合的三种遍历方式

迭代器Iterator
增强for
普通for

/*** @author java小豪* @date 2022/6/10*/publicclassListFor {
publicstaticvoidmain(String[] args) {
// List 接口的实现子类 Vector LinkedList// List<Object> list = new ArrayList<>();List<Object>list=newLinkedList<>();
// List<Object> list = new Vector<>();list.add("jack");
list.add("tom");
list.add("天龙八部");
list.add("北京烤鸭");
// 遍历// 1.迭代器Iterator<Object>iterator=list.iterator();
while (iterator.hasNext()) {
Objectobj=iterator.next();
System.out.println("obj = "+obj);
        }
System.out.println("=================");
//2.增强for循环for (Objectx : list) {
System.out.println(x);
        }
System.out.println("================");
//3.普通for循环for (inti=0; i<list.size(); i++) {
System.out.println(list.get(i));
        }
    }
}

1.3.5、List排序练习

Book类

/*** @author java小豪* @date 2022/6/10*/publicclassBook {
privateStringname;
privateStringauthor;
privateintprice;
publicBook(Stringname, Stringauthor, intprice) {
this.name=name;
this.author=author;
this.price=price;
    }
publicStringgetName() {
returnname;
    }
publicvoidsetName(Stringname) {
this.name=name;
    }
publicStringgetAuthor() {
returnauthor;
    }
publicvoidsetAuthor(Stringauthor) {
this.author=author;
    }
publicintgetPrice() {
returnprice;
    }
publicvoidsetPrice(intprice) {
this.price=price;
    }
@OverridepublicStringtoString() {
return"名称："+name+"\t\t价格："+price+"\t\t作者："+author;
    }
}

main:

/*** @author java小豪* @date 2022/6/10*/publicclassListExercise2 {
publicstaticvoidmain(String[] args) {
// List<Object> list = new Vector<>();List<Object>list=newArrayList<>();
// List<Object> list = new LinkedList<>();list.add(newBook("红楼梦", "曹雪芹", 70));
list.add(newBook("西游记", "吴承恩", 10));
list.add(newBook("水浒传", "施耐庵", 90));
list.add(newBook("三国志", "罗贯中", 80));
// 遍历for (Objecto : list) {
System.out.println(o);
        }
// 冒泡排序sort(list);
System.out.println("=========");
// 排序后遍历for (Objecto : list) {
System.out.println(o);
        }
    }
publicstaticvoidsort(List<Object>list) {
for (inti=0; i<list.size() -1; i++) {
for (intj=0; j<list.size() -1-i; j++) {
// 取出对象BookBookbook1= (Book) list.get(j);
Bookbook2= (Book) list.get(j+1);
if (book1.getPrice() >book2.getPrice()) {
list.set(j, book2);
list.set(j+1, book1);
                }
            }
        }
    }
}

1.4、ArrayList底层结构和源码分析

1.4.1、注意事项

ArrayList可以存放空值null
ArrayList是由数组来实现数据存储的
ArrayList是线程不安全的(执行效率高),多线程情况下，不建议使用ArrayList

/*** @author java小豪* @date 2022/6/10*/publicclassArrayListDetail {
publicstaticvoidmain(String[] args) {
ArrayList<String>arrayList=newArrayList<>();
arrayList.add(null);
arrayList.add("jack");
arrayList.add(null);
System.out.println("arrayList = "+arrayList);
    }
}

1.4.2、ArrayList扩容机制

ArrayList中维护一个Object类型的数组elementData transient Object[] elementData;
transient ：表示瞬间，短暂的

当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0，第一次添加，则扩容elementData为10，如需再次扩容，则扩容elementData为1.5倍。

如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如需扩容，则直接扩容elementData为1.5倍。

1.4.3、ArrayList源码

一、当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData容量为0，第一次添加，则扩容elementData为10，如需再次扩容，则扩容elementData为1.5倍。

演示代码

/*** @author java小豪* @date 2022/6/10*/publicclassArrayListSource {
publicstaticvoidmain(String[] args) {
// 使用午餐构造器创建ArrayList对象ArrayList<Integer>list=newArrayList<>();
// ArrayList<Integer> list = new ArrayList<>(8);// 使用for给list集合添加 1-10数据for (inti=1; i<=10; i++) {
list.add(i);
        }
// 使用for给list集合添加11-15数据for (inti=11; i<=15; i++) {
list.add(i);
        }
list.add(200);
list.add(100);
    }
}

1.5、Vector底层结构和源码分析

1.5.1、基本介绍

Vector类的定义说明

Vector底层也是一个对象数组，protected Object[] elementData;
Vector是线程同步的，即线程安全，Vector类的操作方法带有synchronized

1.5.2、Vector底层和ArrayList的比较

	底层结构	版本	线程安全（同步）效率	扩容倍数
ArrayList	可变数组	JDK1.2	不安全，效率高	如果有参构造1.5倍如果是无参1.第一次102.从第二次开始按照1.5倍
Vector	可变数组	JDK1.0	安全效率高	如果是无参，默认10，满后直接按2倍扩容如果指定大小，则每次直接按2倍扩容

1.5.3、源码解读

一、创建Vector对象时使用无参构造器源码

/*** @author java小豪* @date 2022/6/11*/publicclassVector_ {
publicstaticvoidmain(String[] args) {
// 无参构造器Vector<Integer>vector=newVector<>();
for (inti=0; i<10; i++) {
vector.add(i);
        }
vector.add(100);
System.out.println("vector = "+vector);
// 源码解读// 1. new Vector() 底层/*public Vector() {this(10);}2. vector.add(i)2.1 // 添加数据到Vector集合public synchronized boolean add(E e) {modCount++;ensureCapacityHelper(elementCount + 1);elementData[elementCount++] = e;return true;}2.2  // 确定是否需要扩容 条件： minCapacity - elementData.length > 0private void ensureCapacityHelper(int minCapacity) {// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);}2.3 // 如果需要的数组大小 不够用， 就扩容 扩容算法// int newCapacity = oldCapacity + ((capacityIncrement > 0) ?//                                   capacityIncrement : oldCapacity);private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + ((capacityIncrement > 0) ?capacityIncrement : oldCapacity);if (newCapacity - minCapacity < 0)newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);elementData = Arrays.copyOf(elementData, newCapacity);}*/    }
}

二、分析图

1.6、LinkedList底层结构

1.6.1、说明

LinkedList实现了双向链表和双端队列特点
可以添加任意元素(元素可以重复),包括null
线程不安全，没有实现同步

1.6.2、LinkedList的底层操作机制

LinkedList底层维护了一个双向链表
LinkedList中维护了两个属性first和last分别指向首节点和尾节点
每个节点（Node对象），里面有维护了prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个节点。最终实现双向链表
LinkedList的元素添加和删除，不是通过数组完成的，相对来说效率较高
模拟简单的双向链表

/*** @author java小豪* @date 2022/6/11*/publicclassLinkedList01 {
publicstaticvoidmain(String[] args) {
// 模拟简单的双向链表Nodejack=newNode("jack");
Nodetom=newNode("tom");
Nodechen=newNode("chen");
// 连接三个节点，形成双向链表// jack -> tom -> chenjack.next=tom;
tom.next=chen;
// chen -> tom -> jackchen.prev=tom;
tom.prev=jack;
// 让first引用指向jack，就是双向链表的头节点Nodefirst=jack;
// 让last引用指向chen，就是双向链表的尾节点Nodelast=chen;
// 遍历 从头到尾遍历while (true) {
if (first==null) {
break;
            }
// 输出信息System.out.println(first);
first=first.next;
        }
// 遍历 从尾到头遍历System.out.println("===从尾到头遍历===");
while (true) {
if (last==null) {
break;
            }
// 输出信息System.out.println(last);
last=last.prev;
        }
// 添加元素// 1.创建一个Node结点， name 是张飞Nodezf=newNode("张飞");
zf.next=chen;
zf.prev=tom;
chen.prev=zf;
tom.next=zf;
// 让first 再次指向jackfirst=jack;
System.out.println("===从头到尾遍历===");
while (true) {
if (first==null) {
break;
            }
// 输出信息System.out.println(first);
first=first.next;
        }
    }
}
/*** 定义一个Node类*/classNode {
/**存放数据*/publicObjectitem;
/**指向下一个节点*/publicNodenext;
/**指向前一个节点*/publicNodeprev;
publicNode(Objectname) {
this.item=name;
    }
publicStringtoString() {
return"Node name = "+item;
    }
}

1.6.3、LinkedList底层源码

1.6.3.1、添加元素

linkedList.add(1);

// 1、LinkedList<Integer> linkedList = new LinkedList<>();publicLinkedList() {}
// 2、这是LinkedList 的属性first = null last = null// 3、执行add方法publicbooleanadd(Ee) {
linkLast(e);
returntrue;
   }
// 4、将新的结点，加入到双向链表的最后voidlinkLast(Ee) {
finalNode<E>l=last;
finalNode<E>newNode=newNode<>(l, e, null);
last=newNode;
if (l==null)
first=newNode;
elsel.next=newNode;
size++;
modCount++;
    }

流程图

执行 add 方法

执行 linkList

1.6.3.2、删除元素

linkedList.remove();

// 1、linkedList.remove();// 默认删除第一个元素// 2、执行 removeFirst() 方法publicEremove() {
returnremoveFirst();
    }
// 3、执行publicEremoveFirst() {
finalNode<E>f=first;
if (f==null)
thrownewNoSuchElementException();
returnunlinkFirst(f);
    }
// 4、执行  unlinkFirst, 将 f 指向的双向链表的第一个结点拿掉privateEunlinkFirst(Node<E>f) {
// assert f == first && f != null;finalEelement=f.item;
finalNode<E>next=f.next;
f.item=null;
f.next=null; // help GCfirst=next;
if (next==null)
last=null;
elsenext.prev=null;
size--;
modCount++;
returnelement;
    }