1.Linkedlist
1.1概述
Linkedlist:底层是双向链表,因为不是连续存储,只是能找到下一个元素的地址,所以进行添加删除操作效率较高。但查询效率较低,因为只能从第一个挨个找。
1.2基本使用
public static void main(String[] args){
LinkedList list =new LinkedList();
//添加到尾部
list.add(1);
list.add(12);
list.add(15);
list.add(18);
list.add(3);
//添加到指定位置
list.add(2, 13);
//添加到头部
list.push(0);
list.addFirst(-1);
//尾部添加
list.addLast(20);
//个数
System.out.println(list.size());
//是否为空
System.out.println(list.isEmpty());
//根据下标删除
list.remove(3);
//根据数据删除
list.remove(new Integer(20));
//更改
list.set(2, 10);
//获取
System.out.println(list.get(2));
//遍历
for(Object object:list){
System.out.println(object);
}
//清空
list.clear();
System.out.println(list);
}
1.3底层实现
节点类:
链表由节点构成,双向链表,节点中有三个属性:
1.保存的数据:Object
2.下一个节点对象:节点类型
3.上一个节点对象:节点类型
为了首尾添加效率更高,LinkedList类中保存了首尾节点。
1.4LinkedList和ArrayList应用场景
LinkedList:用于首部或指定位置进行添加和删除较多的情况下。
ArrayList:用于查询更改,尾部添加删除较多的情况。
2.set
set特性:无序且不可重复,无序指添加顺序和取出顺序不保证一致。
HashSet:底层是散列表。
TreeSet:底层是红黑树,添加的元素必须按照一定的格式进行排序。
数字:从小到大
字符串:按每位的ASCII码进行排序
日期:自然日期:今明后。
2.1TreeSet
public static void main(String[] args){
//创建对象
TreeSet set =new TreeSet();
//添加
set.add(13);
set.add(2);
//因为TreeSet必须保证元素有序,意味着元素类型必须统一
//不统一就没可比性,不能排序
//set.add(“ad”);
set.add(5);
set.add(20);
set.add(18);
//不可重复,若重复就不添加
set.add(5);
System.out.println(set.size());//5
System.out.println(set);
//根据内容删除,不能根据索引删除,因为没有索引
set.remove(20);
//遍历
for(Object object:set){
System.out.println(object);
}
比较
set=new TreeSet();
//每一位按ASCII码进行比较
set.add(“acdad”);
set.add(“cde”);
set.add(“ace”);
set.add(“aaa”);
set.add(“da”);
set.add(“ee”);
System.out.println(set);//aaa acdad ace cde da ee
set=new TreeSet();
set.add("1");
set.add("7");
set.add("2");
set.add("4");
set.add("3");
set.add("5");
set.add("6");
set.add("8");
set.add("9");
set.add("10");
System.out.println(set);//1 10 2 3 4 5 6 7 8 9
3.排序
3.1Comparable
使用TreeSet的时候,元素必须实现了Comparable接口,因为在添加的时候,会自动调用该接口的compareTo方法进行比较
添加字符串,数字,日期的时候,会进行自动排序,是因为Integer,String,Date都实现了该接口和该方法
如果我们要存储自定类型的时候,就需要让该类去实现对应的接口和方法才能进行存储
class User implements Comparable{
int age;
public User(int age) {
super();
this.age = age;
}
public User() {
super();
}
@Override
public String toString() {
return “[” + age + “]”;
}
@Override
public int compareTo(Object o) {
//this是要添加的元素
//o是集合中的元素
if(o instanceof User){
User u=(User) o;
//return u.age-this.age;//降序
return this.age-u.age;//升序
}
//该方法 返回0说明重复,不添加
//返回 >0说明要添加的元素比集合中的大,就往后放
//返回<0说明要添加的元素比集合中的小,就往前放
return -1;
}
}
3.2Comparator
Comparator :比较类,Comparable也是做比较的,如果这两个同时存在,则Comparator优先级高
Comparable:如果TreeSet中保存的是自定义类型的时候,使用Comparable
Comparator:如果TreeSet中保存的不是自定义类型的时候,使用Comparator来指定排序规则
比如Integer中默认是升序排序,假如需降序排序的时候就只能用Comparator,因为我们不可更改Integer的源码
但Integer中是有Comparable接口的实现的,等于两个比较都存在,但Comparator优先级更高
所以会按照我们定义的规则进行排序
开闭原则:扩展开放,修改关闭
public static void main(String[] args) {
//把比较器类的对象传入
TreeSet set=new TreeSet(new A());
//匿名内部类写法
TreeSet set1=new TreeSet(new Comparator(){
@Override
public int compare(Object o1, Object o2) {
if(o1 instanceof Integer&&o2 instanceof Integer){
Integer i1=(Integer) o1;
Integer i2=(Integer) o2;
// 该方法 返回 0 说明重复,不添加
// 返回 大于0的值 说明要添加的元素比集合中的大,就往后放
// 返回 小于0的值 说明要添加的元素比集合中的元素小,就往前放
return i2-i1;
}
return -1;
}
});
set1.add(1);
set1.add(2);
set1.add(3);
set1.add(4);
//降序
System.out.println(set1);
}
}
//比较器类
class A implements Comparator{
@Override
public int compare(Object o1, Object o2) {
//o1是要添加的元素
//o2是集合中的元素
if(o1 instanceof Integer&&o2 instanceof Integer){
Integer i1=(Integer) o1;
Integer i2=(Integer) o2;
// 该方法 返回 0 说明重复,不添加
// 返回 大于0的值 说明要添加的元素比集合中的大,就往后放
// 返回 小于0的值 说明要添加的元素比集合中的元素小,就往前放
return i2-i1;
}
return -1;
}
}
3.3List排序
public static void main(String[] args){
List list=new ArrayList();
list.add(1);
list.add(22);
list.add(3);
list.add(11);
//该方法会调用对象的Comparable中的compareTo方法或者是Comparator中的compare方法
//因为Integer中有CompareTo方法,而且是升序,所以才可使用sort方法
//若想降序就可sort重载
//Collections.sort(list);
Collections.sort(list,new Comparator(){
@Override
public int compare(Object o1, Object o2) {
// o1 是要添加的元素
// o2 是集合中的元素
Integer i1 = (Integer) o1;
Integer i2 = (Integer) o2;
// 该方法 返回 0 说明重复,不添加
// 返回 大于0的值 说明要添加的元素比集合中的大,就往后放
// 返回 小于0的值 说明要添加的元素比集合中的元素小,就往前放
return i2 - i1;
}
});
System.out.println(list);
list=new ArrayList();
list.add(new Student1(18));
list.add(new Student1(11));
list.add(new Student1(15));
list.add(new Student1(4));
//因为Student1没有实现comparable接口,所以不能使用sort方法
//Collections.sort(list);
Collections.sort(list,new Comparator(){
@Override
public int compare(Object o1, Object o2) {
if(o1 instanceof Student1&&o2 instanceof Student1){
Student1 u1=(Student1) o1;
Student1 u2=(Student1) o2;
return u2.age-u1.age;//降序
}
return -1;
}
});
System.out.println(list);
}
}
class Student1 {
int age;
public Student1(int age) {
super();
this.age = age;
}
@Override
public String toString() {
// TODO Auto-generated method stub
return “[”+age+"]";
}
}