数据结构:计算机中用来存储或者管理数据的方式
链表底层实现的代码:
package demo3.lianxi1;
public class MyLink {
private int data;//存储链表的值
private MyLink next;//指针指向下一个数据
public MyLink(int i) {
data=i;
}
//向链表中拼接值
private void append(MyLink myLink) {
MyLink s=this;
while(s.next!=null){
s=s.next;
}
s.next=myLink;
}
//向链表中增加值,每当增加一个值,都在第一个值的后面
private void add(MyLink myLink) {
myLink.next=next;
next=myLink;
}
//把链表中的数据显示出来
private void show() {
MyLink s = this;
while (s != null) {
System.out.println(s.data);
s = s.next;
}
}
public static void main(String[] args) {
MyLink link=new MyLink(1);
link.append(new MyLink(10));
link.append(new MyLink(20));
link.append(new MyLink(30));
link.add(new MyLink(3));
link.show();
}
}
数组的特点:
1.长度一旦被定义,就不允许被改变
2.在内存中开辟连续的空间
3.便于查询,但是插入和删除麻烦
例子:
如果我们创建一个容量为30的数组,用来存储学生信息
1.一个班的学生如果不够30,造成资源浪费
2.一个班的学生如果大于30,内存不够
集合框架: 父接口Collection
Collections一些方法来操作集合类
Collections 所有集合类的工具类
@test
public void test01{
List<String> list=new ArrayList<>();
list.add("z");
list.add("a");
list.add("v");
list.add("b");
System.out.println("没有排序"+list);
//1.升序--->sort
Collections.sort(list);
System.out.println("升序"+list);
//2.降序-->reverse
Collections.reverse(list);
System.out.println("降序"+list);
//3.查询某个元素在集合中的位置,必须先升序排序-->binarySearch
Collections.sort(list);
int index=Collections.binarySearch(list,"z");
System.out.println("元素z存在的位置是:"+index);
//4.随机排序---->shuffle
Collections.shuffle(list);
System.out.println("随机排序"+list);
}
实现对对象的排序 只有实现Comparable接口的类才能被排序
//只有实现Comparable接口的类 才能被 排序！
public class Student implements Comparable {
private int id; // 学生编号
private String name;
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Student() {
super();
}
@Override
public String toString() {
return "Student [id=" + id + ", name=" + name + "]";
}
public Student(int id, String name) {
super();
this.id = id;
this.name = name;
}
// 按照自己的规则 去进行 排序
@Override
public int compareTo(Object o) {
if (o instanceof Student) {
Student stu = (Student) o;
if (stu.getId() == this.id) {
return 0;
} else if (stu.getId() < this.id) {
return -1;//降序
} else {
return 1;
}
} else {
return 0;
}
}
}
@test
public void test02{
List<Student> list=new ArrayList<>();
list.add(new Student(50,"小黑50"));
list.add(new Student(10,"小黑10"));
list.add(new Student(80,"小黑80"));
list.add(new Student(20,"小黑20"));
list.add(new Student(60,"小黑60"));
Collections.sort(list);
for(Student student:list){
System.out.println(student);
}
}
把数组转换成集合
@Test
public void test03() {
String[] words = { "a", "b", "c", "d" };
List<String> list = Arrays.asList(words);
Collections.rotate(list, 2);//后移两位,把后面的两位移到前面
System.out.println(list);
}
中文排序
@Test
public void test04() {
List<String> list = new ArrayList();
list.add("啊");
list.add("在");
list.add("把");
list.add("好");
list.add("是");
Comparator<Object> c = Collator.getInstance(Locale.CHINA);
Collections.sort(list, c);
for (String s : list) {
System.out.println(s);
}
}
数组和...的区别以及用法
/**
* 01.可以传递0 或者 N个 int类型的数据
* 02.怎么操作数组 怎么操作...
* 03.必须位于参数列表中的最后一个位置
*/
public static void main(String[] args) {
String[] sales = { "啤酒", "饮料", "矿泉水" };
slaeSometing("小粉");
}
/**
* @param name 谁 在 出售 什么 东西
* @param something 出售的东西
*/
private static void slaeSometing(String name, String... something) {
System.out.println(name + "在出售");
for (int i = 0; i < something.length; i++) {
System.out.print(something[i] + ",");
}
}
public interface List<E> extends Collection<E>
public interface Set<E> extends Collection<E>
public interface Map<k.v>
Vector 线程安全,但是性能低
List接口常用的实现类
存储的都是不唯一(可以重复),有序(插入顺序)的数据
ArrayList底层就是一个动态数组,自动扩容
List lis=new ArrayList();
public ArrayList() {
this.elementData = EMPTY_ELEMENTDATA;
}
private static final Object[] EMPTY_ELEMENTDATA = {};
private transient Object[] elementData;
我们在执行add();的时候,底层默认初始化了一个长度为10的数组,可以自动扩容1.5 倍
Object[] elementData=new Object[10];
s.size();集合中元素的个数
s.add();
s.add(0,"");
s.remove();
s.remove(1,"");
新增和删除的效率低,遍历效率快
LinkedList底层就是一个链表,有自己特有而父类没有的方法
有单链表和双链表(含有前驱和后继)之分
LinkdeList lis=new LinkedList();
新增和删除的效率高,查询效率低
Set接口常用的实现类 散列表 Hash 以空间换时间
存储的都是唯一(不可以重复),无序的数据
HashSet
HashSet set = new HashSet();
1.add新增数据
2.其实是使用了map.put(key,value)
3.map.put(key,value)决定了key是唯一的
两个数据内容一致,Hash值肯定一致
Hash值一致,数据内容不一定相同
比较步骤:1.比较Hash,
2.比较内存地址,
3.equals比较内容
TreeSet 自带排序 树型结构
只有实现Comparable接口的类才能被排序
Map 单独的接口
keySet:所有key的集合
HashMap
//使用for加强 遍历keySet
Set<String> keySet=map.keySet();
for (String key : keySet) {
System.out.print(key+" ");
}
//使用Iterator遍历
Set<String> keySet=map.keySet();
Iterator<String> iterator = keySet.iterator();//获取迭代器对象
while(iterator.hasNext()){//证明集合中存在数据
String key = iterator.next();
//根据key获取value
String value=(String) map.get(key);
System.out.print(key+" "+value+" ");
}
//entry Set<Map.Entry<k.v>> entrySet()
Set<Entry<String, Object>> entrySet = map.entrySet();
Iterator<Entry<String, Object>> iterator = entrySet.iterator();
while(iterator.hasNext()){//证明集合中存在数据
Entry<String, Object> entry = iterator.next();
System.out.println(entry.getKey()+"-------"+entry.getValue());
}
HashMap与HashTable的区别:
1.HashMap线程不安全,但是性能高
HashTable线程安全,但是性能低
2.HashTable从1.0的版本就开始使用
HashMap从1.2的版本就开始使用
3.HashMap底层就是Hash表来实现的 key和value都可以是null
HashTablekey和value不可以为null
Hashtable<String,String> table=new Hashtable<>();
table.put(null, null);//运行时异常
所有的集合中都有一个Iterator接口,用来遍历集合中的数据,返回Iterator迭代器
在Iterator接口中有三个方法:
1.hasNext() 判断集合中是否存在下一个元素,返回boolean类型
2.next() 获取集合中的下一个元素
3.remove() 删除元素
TreeMap
泛型集合:在创建集合的时候,规定了集合中能存放的数据类型
List<String> lis=new ArrayList<String>();