集合
1 Collection接口
1.1 集合概述
集合是一个装对象的容器。集合中只能存放引用数据类型的对象。集合中有一些大小是固定的，有一些是不固定的。有一些是有序的，有些是无序的。
有些可以有重复元素，有一些不可以有重复元素
1.2 集合常用方法
public static void main(String[] args) {// 创建集合对象Collection<String> coll = new ArrayList<>();// 添加元素coll.add("吴京");coll.add("王源");coll.add("丁真");coll.add("迪丽热巴");coll.add("刘浩存");coll.add("田晓威");// 清空集合
// coll.clear();boolean contains = coll.contains("刘浩存");System.out.println(contains);// 判断集合是否为空boolean empty = coll.isEmpty();System.out.println(empty);// 移除指定的元素boolean remove = coll.remove("田晓威");System.out.println(remove);// 获取集合的实际元素个数int size = coll.size();System.out.println(size);// 把集合转换成数组String[] array = coll.toArray(new String[0]);for (String o : array) {System.out.println(o);}System.out.println(coll);}1.3 List接口
1.3.1 List接口的特点
有序的集合
方法具有索引
允许重复的元素
1.3.2 List接口带有索引的方法
public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("郭靖");list.add("洪七公");list.add("黄蓉");list.add("欧阳锋");list.add("欧阳克");list.add("黄蓉");// 插入元素list.add(3,"黄药师");list.add(6,"周伯通");// IndexOutOfBoundsException: 索引越界// ArrayIndexOutOfBoundsException: 数组越界
// StringIndexOutOfBoundsException: 字符串越界
// list.add(9,"王重阳");list.add("黄蓉");// 获取指定索引处的元素String s = list.get(4);System.out.println(s);// 获取指定元素首次出现的索引 找不到返回-1int index = list.indexOf("杨过");System.out.println(index);// 获取指定元素最后一次出现的索引 找不到返回-1int indexOf = list.lastIndexOf("黄蓉");System.out.println(indexOf);// 删除指定索引处的元素String remove = list.remove(5);System.out.println(remove);// 替换指定索引处的元素String set = list.set(6, "杨康");System.out.println(set);// 截取子列表 包头不包尾List<String> strings = list.subList(2, 6);System.out.println(strings);System.out.println(list);}1.3.3 ArrayList的特点
内部数据结构是数组
内存是连续的,具有索引
查询速度相对快
增删速度相对慢
异步线程不安全的集合
可以存放null
默认无参构造的初始容量是0
默认的初始容量是10
扩容是原来容量 + 原来容量 / 2
public static void main(String[] args) {ArrayList<String> arrayList = new ArrayList<>(14);arrayList.add("阿珍");// 把ArrayList长度变成实际元素个数的长度arrayList.trimToSize();}1.3.4 实现ArrayList练习
package cn.javasm.demo;
import java.util.Arrays;
import java.util.Objects;
/*** 模拟实现ArrayList*/
public class ArrayListDemo {// 存储数据的数组private String[] data;// 实际元素个数private int size;
// 定义无参构造public ArrayListDemo(){// 默认长度是10data = new String[10];}
// 定义有参构造,用户可以根据参数选择初始默认容量public ArrayListDemo(int len){if (len < 0) throw new IllegalArgumentException();data = new String[len];}
// 添加元素public void add(String str){// 判断是否需要扩容if (size >= data.length){grow();}data[size++] = str;}
/*** 扩容数组*/private void grow() {if (data.length >= 1)data = Arrays.copyOf(data,data.length + (data.length >> 1));elsedata = Arrays.copyOf(data,data.length + 1);}
// 插入元素方法public void add(int index,String str){// 判断索引是否越界if (index < 0 || index > size) throw new IndexOutOfBoundsException("数组越界了");
// 判断是否需要扩容if (size >= data.length){grow();}
// 插入元素其实就是将数据向后挪动一位，然后腾出来的那一位赋值为要插入的数据// 方式一:
// for (int i = size - 1;i >= index;i--){
// data[i + 1] = data[i];
// }// 方式二:System.arraycopy(data,index,data,index + 1,size - index);
data[index] = str;// 实际元素+1size++;}
/*** 删除指定索引处的元素* @param index*/public void remove(int index){// 判断索引是否越界out(index);
// 删除元素就是将后面的元素依次向前移动一位// 方式一:
// for (int i = index;i < size - 1;i++){
// data[i] = data[i + 1];
// }// 方式二:System.arraycopy(data,index + 1, data,index,size - index - 1);
// 实际元素个数-1size--;}
private void out(int index) {if (index >= size || index < 0) throw new IndexOutOfBoundsException();}
/*** 查找指定元素首次出现的索引,找不到返回-1*/public int indexOf(String str){for (int i = 0; i < size; i++) {
// if (str == data[i] || str != null && str.equals(data[i])){
// return i;
// }if (Objects.equals(str,data[i])){return i;}}return -1;}
/*** 删除指定元素*/public void remove(String str){// 查找str首次出现的位置int index = indexOf(str);if (index != -1) remove(index);}
/*** 清空集合*/public void clear(){data = new String[10];size = 0;}
/*** 判断是否包含某个元素*/public boolean contains(String str){return indexOf(str) != -1;}
/*** 获取指定索引处的元素*/public String get(int index){// 判断是否越界out(index);return data[index];}
/*** 判断集合是否为空*/public boolean isEmpty(){return size == 0;}
/*** 替换元素*/public void set(int index,String str){out(index);data[index] = str;}/*** 获取元素个数*/public int size(){return size;}
/*** 截取子列表* @return*/public ArrayListDemo sublist(int fromIndex,int toIndex){// 判断索引是否越界out(fromIndex);out(toIndex);
// 判断参数是否合法if (fromIndex > toIndex) throw new IllegalArgumentException();
// 创建新的列表ArrayListDemo sublist = new ArrayListDemo(toIndex - fromIndex);// 拷贝数据System.arraycopy(data,fromIndex,sublist.data,0,toIndex - fromIndex);// 设置实际元素个数sublist.size = toIndex - fromIndex;return sublist;}
// [元素1, 元素2, 元素3]@Overridepublic String toString() {StringBuilder stringBuilder = new StringBuilder();stringBuilder.append("[");for (int i = 0; i < size; i++) {if (i != size - 1){stringBuilder.append(data[i]).append(", ");}else {stringBuilder.append(data[i]);}}stringBuilder.append("]");return stringBuilder.toString();
}
}1.3.5 LinkedList的特点
底层数据结构是双向链表
内存是不连续的
增删速度快
查询速度慢
异步线程不安全的集合
1.3.6 实现LinkedList
package cn.javasm.demo;
import java.util.Objects;
public class LinkedListDemo {/*** 实际元素个数*/private int size;
/*** 头结点*/private Node first;
/*** 尾结点*/private Node last;
// 结点private class Node{// 数据String item;
// 上一个结点Node prev;
// 下一个结点Node next;
public Node(String item, Node prev, Node next) {this.item = item;this.prev = prev;this.next = next;}}
/*** 添加元素* @param str 数据*/public void add(String str){// 创建新结点Node node = new Node(str,null,null);// 添加元素分为两种情况// 1.添加的是第一个结点 要求头尾相同if (size == 0){this.first = node;}else {// 2.不是第一个结点this.last.next = node;node.prev = this.last;}this.last = node;size++;}
/*** 插入元素* @param index 插入的索引* @param str 数据*/public void add(int index,String str){// 判断索引是否越界if (index > size || index < 0) throw new IndexOutOfBoundsException();// 插入元素分为三种情况// 1.插入到尾部 2.插入到中间 3.插入到头部// 插入到尾部就是添加元素if (index == size){add(str);return;}
// 创建新结点Node node = new Node(str,null,null);if (index == 0){// 插入到头部node.next = this.first;this.first.prev = node;this.first = node;}else {// 插入到中间
// 先查询要插入索引的元素Node no = getNode(index);no.prev.next = node;node.prev = no.prev;node.next = no;no.prev = node;}size++;}
/*** 根据索引查找结点* @param index* @return*/private Node getNode(int index) {Node no = first;for (int i = 0; i < index; i++) {no = no.next;}return no;}
/*** 删除指定索引处的元素* @param index*/public void remove(int index){
// 判断索引是否越界out(index);
// 删除元素分为: 1.删除头结点 2.删除尾结点 3.删除中间结点if (index == 0){// 删除头结点this.first = this.first.next;this.first.prev = null;}else if (index == size - 1){//删除尾结点this.last = this.last.prev;this.last.next = null;}else {// 删除中间结点Node node = getNode(index);node.prev.next = node.next;node.next.prev = node.prev;}size--;}
private void out(int index) {if (index >= size || index < 0) throw new IndexOutOfBoundsException();}
/*** 查询指定元素首次出现的索引* @param str 指定的元素* @return 索引*/public int indexOf(String str){// 获取头结点Node node = this.first;for (int i = 0; i < size; i++) {if (Objects.equals(str,node.item)){return i;}node = node.next;}return -1;}
/*** 删除指定元素的结点*/public void remove(String str){// 查找出现的索引int index = indexOf(str);if (index != -1) this.remove(index);}
/*** 清空链表*/public void clear(){this.first = this.last = null;size = 0;}
/*** 判断是否包含指定的元素* @return*/public boolean contains(String str){return indexOf(str) != -1;}
/*** 获取元素* @return*/public String get(int index){//判断是否越界out(index);return getNode(index).item;}
/*** 判断链表是否为空* @return*/public boolean isEmpty(){return size == 0;}
/*** 替换元素* @return*/public void set(int index,String str){// 判断是否越界out(index);getNode(index).item = str;}
/*** 获取元素个数* @return*/public int size(){return size;}
/*** 截取子链表*/public LinkedListDemo sublist(int fromIndex,int toIndex){// 判断是否越界out(fromIndex);out(toIndex);// 判断参数是否合法if (fromIndex > toIndex) throw new IllegalArgumentException();
// 创建新链表LinkedListDemo sublist = new LinkedListDemo();// 获取开始的结点Node node = getNode(fromIndex);for (int i = fromIndex;i < toIndex;i++){sublist.add(node.item);node = node.next;}return sublist;}
@Overridepublic String toString() {StringBuilder stringBuilder = new StringBuilder();stringBuilder.append("[");Node node = this.first;for (int i = 0; i < size; i++) {if (i != size - 1){stringBuilder.append(node.item).append(", ");}else {stringBuilder.append(node.item);}node = node.next;}stringBuilder.append("]");return stringBuilder.toString();}
public Node getFirst() {return first;}
public Node getLast() {return last;}
}
