集合
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);
// 获取指定元素首次出现的索引 找不到返回-1
int index = list.indexOf("杨过");
System.out.println(index);
// 获取指定元素最后一次出现的索引 找不到返回-1
int 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(){
// 默认长度是10
data = 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));
else
data = 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;
// 实际元素+1
size++;
}
/**
* 删除指定索引处的元素
* @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);
// 实际元素个数-1
size--;
}
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]
@Override
public 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;
}
@Override
public 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;
}
}