1 List接口
相关文章
- 《数据结构与算法分析 java语言描述》-- java 表List的删除操作，时间复杂度对比
https://blog.csdn.net/LawssssCat/article/details/102932463
1.1 概述
<mark>有序的</mark> collection（也称为序列）。
此接口的用户可以对列表中每个元素的插入位置进行精确地控制。
用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。
1.2 特点
- 数据<mark>有序</mark>
- <mark>允许重复</mark>元素
- 元素都有索引
1.3 常用方法
- 返回此列表元素的<mark>列表</mark>迭代器（按适当顺序）。<mark>[可前可后]</mark>
ListIterator<E> listIterator()
- 返回列表中元素的列表迭代器（按适当顺序），<mark>从列表的指定位置开始</mark>。
ListIterator<E> listIterator(int index)
- 在列表的<mark>指定位置插入</mark>指定元素（可选操作）。
void add(int index, E element)
- 将指定 collection 中的所有元素都插入到列表中的指定位置（可选操作）。
boolean addAll(int index, Collection<? extends E> c)
- 返回列表中指定的 fromIndex（包括 ）和 toIndex（不包括）之间的部分视图。
List<E> subList(int fromIndex, int toIndex)
- 返回列表中指定位置的元素。
E get(int index)
- 返回此列表中第一次出现的指定元素的索引；如果此列表不包含该元素，则返回 -1。
int indexOf(Object o)
1.4 练习1：测试常用方法
创建day12工程
创建cn.tedu.list包
创建Test1_List.java
package cn.tedu.list;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
//这类用来测试List接口的常用方法
public class Test1_List {
public static void main(String[] args) {
//1、创建List对象
//特点1：List集合元素都有索引，可以根据索引直接定位元素
List list = new ArrayList();
//2、常用方法
list.add(111);
list.add(222);
list.add(333);
list.add(444);
list.add('a');
list.add("abc");
list.add(3,666);//在3的索引处添加指定元素
//特点2：元素有序， 怎么存就怎么放
System.out.println(list);//[111, 222, 333, 666, 444, a, abc]
Object obj = list.get(4);//get(m)-m是索引值，获取指定索引位置的元素
System.out.println(obj);
//3、迭代/遍历集合中的元素
//使用Collection接口提供的iterator()
Iterator it = list.iterator();
while(it.hasNext()) {//判断集合里有没有下个元素
Object o = it.next();
// System.out.println(o);
}
//使用List接口提供的listIterator()
//interfaceListIterator extends Iterator
//区别：可以使用父接口的功能，同时拥有自己的特有功能，不仅顺序向后迭代还可以逆向迭代
ListIterator it2 = list.listIterator();
while(it2.hasNext()) {
Object o = it2.next();
// System.out.println(o);
}
System.out.println();
List list2 = list.subList(1, 3);//subList(m,n)-m是开始索引，n是结束索引，其中含头不含尾类似于String.subString(m,n)
System.out.println(list2);
}
}
2 ArrayList
2.1 概述
- 存在于java.util包中。
- 内部用数组存放数据，封装了数组的操作，每个对象都有下标。
- 内部数组默认<mark>初始容量是10</mark>。如果不够<mark>会以1.5倍容量增长</mark>。
- 查询快，增删数据效率会降低。
2.2 创建对象
ArrayList()
构造一个初始容量为 10 的空列表。
ArrayList(int initialCapacity)
构造一个具有指定初始容量的空列表。
2.3 练习1：测试常用方法
下标遍历，迭代器遍历
package cn.tedu.list;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.ListIterator;
//这个类用来测试ArrayList的用法
public class Test2_ArrayList {
public static void main(String[] args) {
//1、创建ArrayList对象
ArrayList al = new ArrayList();//默认集合大小是10
//2、常用方法
al.add("a");
al.add("1");
al.add("中国");
al.add("123");
al.add(2,"0");
System.out.println(al);
System.out.println(al.size());
System.out.println(al.contains("a"));
System.out.println(al.get(2));
System.out.println(al.hashCode());
System.out.println(al.isEmpty());
System.out.println(al.indexOf("0"));
System.out.println(al.remove(2));
//迭代元素
//Collection.iterator()
Iterator it = al.iterator();
while(it.hasNext()) {
System.out.println(it.next());
}
//List.listIterator()
ListIterator it2 = al.listIterator();
while(it2.hasNext()) {
System.out.println(it2.next());
}
}
}
3 LinkedList
3.1 概述
<mark>双向</mark> <mark>链表</mark>，两端效率高。底层就是数组和链表实现的（<mark>看了源码，只有链表，没有数组把？</mark>）。
3.2 创建对象
构造一个空链表。
LinkedList()
3.3 常用方法
addFirst() addLast()
getFirst() getLast()
removeFirst() removeLast()
3.4 练习1：测试常用方法
双向链表：下标遍历效率低，迭代器遍历效率高
package cn.tedu.list;
import java.util.LinkedList;
//这个类用来测试LinkedList的常用方法
public class Test3_LinkedList {
public static void main(String[] args) {
//1、创建LinkedList对象
LinkedList ll = new LinkedList();
ll.add(1);
ll.add(2);
ll.add(3);
ll.add(4);
ll.add(5);
System.out.println(ll);
//2、常用方法：特有方法
ll.addFirst(0);//首位置添加元素
ll.addLast(9);
System.out.println(ll);//[0, 1, 2, 3, 4, 5, 9]
System.out.println(ll.getFirst());//获取首位置元素
System.out.println(ll.getLast());
System.out.println(ll.removeFirst());//移除首位置元素
System.out.println(ll.removeLast());
System.out.println(ll);//[1, 2, 3, 4, 5]
}
}
4 Set接口
4.1 概述
一个<mark>不包含重复</mark>元素的 collection。
数据无序(因为set集合没有下标)。
<mark>不根据用户输入顺序存储，会自动排序。如：HashSet根据HashCode排序，TreeSet根据Comparator排序</mark>
由于集合中的元素不可以重复。
常用于给数据去重。
4.2 特点
- 数据不允许重复
数据无序- HashSet：<mark>底层是哈希表</mark>（散列）
- TreeSet：底层是TreeMap，也是<mark>红黑树</mark>的形式，便于查找数据。
4.3 常用方法
- 如果 set 中尚未存在指定的元素，则添加此元素（可选操作）。
boolean add(E e)
- 如果 set 中没有指定 collection 中的所有元素，则将其添加到此 set 中（可选操作）。
boolean addAll(Collection<? extends E> c)
- 移除此 set 中的所有元素（可选操作）。
void clear()
- 如果 set 包含指定的元素，则返回 true。
boolean contains(Object o)
- 如果此 set 包含指定 collection 的所有元素，则返回 true。
boolean containsAll(Collection<?> c)
- 比较指定对象与此 set 的相等性。
boolean equals(Object o)
- 返回 set 的哈希码值。
int hashCode()
- 如果 set 不包含元素，则返回 true。
boolean isEmpty()
- 返回在此 set 中的元素上进行迭代的迭代器。
Iterator<E> iterator()
- 如果 set 中存在指定的元素，则将其移除（可选操作）。
boolean remove(Object o)
- 移除 set 中那些包含在指定 collection 中的元素（可选操作）。
boolean removeAll(Collection<?> c)
- 仅保留 set 中那些包含在指定 collection 中的元素（可选操作）。
boolean retainAll(Collection<?> c)
- 返回 set 中的元素数（其容量）。
int size()
- 返回一个包含 set 中所有元素的数组。
Object[] toArray()
- 返回一个包含此 set 中所有元素的数组；返回数组的运行时类型是指定数组的类型。
<T> T[] toArray(T[] a)
4.4 练习1：测试常用方法
package cn.tedu.set;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
//这个类用来测试Set接口的常用方法
public class Test4_Set {
public static void main(String[] args) {
//1、创建Set对象
Set set = new HashSet();
//2、常用方法
//特点1：set集合中不能存放重复的元素
set.add(1);//添加数据
set.add(1);
set.add(1);
set.add('x');
set.add("abc");
set.add("蔡徐坤");
//特点2：数据是无序的，[1, abc, x, 蔡徐坤]
System.out.println(set);
System.out.println(set.contains(1));
System.out.println(set.hashCode());
System.out.println(set.isEmpty());
System.out.println(set.remove('x'));
System.out.println(set.size());
System.out.println();
//TODO 迭代set集合
Iterator it = set.iterator();
while( it.hasNext() ) {//有下一个元素就遍历
System.out.println( it.next() );//next()-获取迭代到的元素
}
}
}
5 HashSet
5.1 概述
<mark>底层是哈希表/散列表</mark>， 包装了HashMap， 相当于向HashSet中存入数据时，会把数据作为K，存入内部的HashMap中。
5.2 练习1：测试常用方法
HashSet()：构造一个新的空 set，其底层 HashMap 实例的默认初始容量是 16，加载因子是 0.75。
6 Map接口
6.1 概述
java.util接口 Map<K,V>
类型参数： K - 此<mark>映射</mark>所维护的<mark>键的</mark>类型V - <mark>映射值的</mark>类型。
也叫<mark>哈希表、散列表</mark>。常用于存 键值对 结构的数据。其中的键不能重复，值可以重复.
6.2 特点
- 可以根据键 提取对应的值
- 键不允许重复，如果重复值会被覆盖
- 存放的都是无序数据
- <mark>初始容量是16，默认的加载因子是0.75</mark>
6.3 继承结构
6.4 常用方法
6.5 练习1：测试常用方法
package cn.tedu.map;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
//这个类用来测试Map接口
public class Test7_Map {
public static void main(String[] args) {
//1、创建Map对象
//特点1：map中存放的都是一对一对的键值对
Map map = new HashMap();
//2、常用方法
map.put("name", "韩梅梅");//put(m,n) - m是键，n是值
map.put("age", "20");
map.put("address", "中国人");
//特点3：map存放的数据是无序的
//{address=中国人, name=韩梅梅, age=20}
System.out.println(map);
//特点2：当key重复时，value会被覆盖
map.put("name", "李雷");
//{address=中国人, name=李雷, age=20}
System.out.println(map);
System.out.println(map.get("address"));
System.out.println(map.containsKey("name"));
System.out.println(map.containsValue("20"));
// System.out.println(map.remove("address"));
System.out.println(map.size());
//3、迭代map中元素
//keySet() -- 把map中的key都取出来放入set集合中
Set set = map.keySet();
Iterator it = set.iterator();//迭代set集合
while(it.hasNext()) {//set中是否有下一个元素
Object key = it.next();//获取set集合里的每个key
Object value = map.get(key);//根据key去map里找value
System.out.println(key+"="+value);
}
//entrySet() -- 把map中的key和value取出来，形成Entry[]
Set set2 = map.entrySet();
Iterator it2 = set2.iterator();//迭代set集合
while(it2.hasNext()) {//set中是否有下一个元素
Entry entry = (Entry) it2.next();//获取每个Entry对象
Object key = entry.getKey();//获取Entry 对象保存着的key
Object value = entry.getValue();//获取Entry 对象保存着的value
System.out.println(key+":::::"+value);
}
}
}
∗∗7.HashMap∗∗
HashMap的键要同时重写hashCode()和equals()
hashCode()用来判断确定hash值是否相同
equals()用来判断属性的值是否相同
原则：
- equals()判断数据如果相等，hashCode()必须相同
- equals()判断数据如果不等，hashCode()尽量不同
7.1 概述
<mark>HashMap底层是一个Entry数组</mark>，<mark>当存放数据时会根据hash算法计算数据的存放位置</mark>。<mark>算法：hash(key)%n，n就是数组的长度</mark>。
当计算的位置没有数据时，就直接存放，<mark>当计算的位置有数据时也就是发生hash冲突/hash碰撞时</mark>，<mark>采用链表的方式来解决的</mark>，在对应的数组位置存放链表的头结点。对链表而言，新加入的节点会从头结点加入。
<mark>（当碰撞数据大于8（默认）时，链表会变成红黑树结构）</mark>
7.2 练习1：获取HashMap的数据
HashMap()
构造一个具有默认初始容量 (16) 和默认加载因子 (0.75) 的空 HashMap。
package cn.tedu.map;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
//这个类用来测试HashMap的 用法
public class Test8_HashMap {
public static void main(String[] args) {
//1、创建HashMap对象
HashMap map = new HashMap();
//2、常用方法
map.put("9527", "唐伯虎");
map.put("9528", "秋香姐");
map.put("9529", "石榴姐");
map.put("9530", "如花");
map.put("9527", "孙悟空");
map.put("9528", "猪八戒");
//迭代map--keySet()--把map中的key放入set
Set set = map.keySet();
//迭代set集合
Iterator it = set.iterator();
while(it.hasNext()) {
Object key = it.next();
Object value = map.get(key);
System.out.println(key+"==="+value);
}
}
}
7.3 练习2：字符串中的字符统计
接收用户输入的一串字符串，
统计出现的每个字符的个数
package cn.tedu.map;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
//统计字符串中字符的出现次数
public class Test9_Count {
public static void main(String[] args) {
//1、接收用户输入的字符串
String str = new Scanner(System.in).nextLine();
Map map = new HashMap();//存数据，类似{a=3,b=2}
//2、遍历字符串，并获取每个字符
for(int i = 0 ; i < str.length() ; i++) {
//3、根据下标获取对应着的字符，即将作为key存入map
char c = str.charAt(i);
//4、字符作为key存入map,value需要判断
//拿着key去map中找，如果是默认值，之前就没存过，只要存入1就行
Integer sum = (Integer) map.get(c);
//5、判断，如果value是默认值null，就存入1，否则就+1
if(sum == null) {
map.put(c, 1);
}else {
map.put(c, sum+1);
}
}
System.out.println(map);
}
}
8 扩展
8.1 了解泛型
8.2 栈Stack
package seday12new;
import java.util.Stack;
public class tt {
public static void main(String[] args) {
Stack s = new Stack();
//push压栈
s.push("熊大");
s.push("熊二");
s.push("光头强");
for (Object obj : s) {
String ss = (String)obj;
System.out.println(ss);
}
//pop弹栈
System.out.println();
s.pop();//后进先出，栈顶元素先出栈
s.pop();
for (Object obj : s) {
String ss = (String)obj;
System.out.println(ss);
}
}
}
8.3 队列Queue
private static void q() {
Queue q = new LinkedList<>();
//offer入队
q.offer("a");
q.offer("b");
q.offer("c");
for (Object obj : q) {
String s = (String)obj;
System.out.println(s);
}
//poll出队
System.out.println();
System.out.println(q.poll());
System.out.println(q.poll());
}
∗∗注意：8.4Set存储属性相同的对象∗∗
需求：我们假设相同属性的两个人是同一个人
- 按照以前的经验，这种需求只需要重写equals()方法就可以实现。
- 但是我们提供以后，equals()根本就没有执行。问题出现在新增功能。
- <mark>查找新增的源码发现，其实在添加时只是计算对象的hash值</mark>。
- <mark>由于每次创建对象时hash值都不一样，所以每次都会当做新对象存起来。</mark>
- 所以，<mark>现在我们必须保证两个对象的hash值相同，重写hashCode()</mark>。
package cn.tedu.set;
import java.util.HashSet;
import java.util.Set;
//测试Set集合给相同属性的两个对象--去重
//总结：给类中同时重写hashCode()和equals()
public class Test6_Set3 {
public static void main(String[] args) {
Set set = new HashSet();
Student s1 = new Student("jack",20);
Student s2 = new Student("jack",20);
set.add(s1);
set.add(s2);
System.out.println(set);
//比较s1和s2是否相等，Object默认提供的是==比较，比较的就是对象的地址值
//需求：比较两个对象的属性值，如果都一样，equals()返回true
System.out.println(s1.equals(s2));
}
}
//创建Student类
class Student{
private String name;
private int age;
//构造方法
public Student() {}
public Student(String name, int age) {
this.name = name;
this.age = age;
}
//get()/set()
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
//重写toString()--为了查看对象的属性值而不是地址值
@Override
public String toString() {
return "Student [name=" + name + ", age=" + age + "]";
}
//重写hashCode()--默认是获取对象的hash值，
//如果是两个对象当然获取两个不同的hash值。
//需求：如果两个对象间的属性值完全一致，算出来hash值的结果必须一样
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + age;
result = prime * result + ((name == null) ? 0 : name.hashCode());
return result;
}
//重写equals()--默认实现是比较两个对象的地址值
//如果要比对象间的属性值，相同时，认为是同一个对象，返回true的话，就要重写。
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Student other = (Student) obj;
if (age != other.age)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
}
京公网安备 11010502036488号