一、认识数据结构
1.数据结构有什么用?
合理的使用数据结构,可以更方便的查找存储数据。
2.常见的数据结构
数据存储常用结构有:栈、队列、数组、链表和红黑树。
- 栈:堆栈(stack),它是运算受限的线性表,限制只允许在表(栈顶)的一端进行插入和删除操作。特点是先进后出,栈的入口和出口都在栈的顶端。
- 队列:简称队(queue),它和堆栈一样都是运算受限的线性表,限制只允许在表一端插入,一端删除。特点是先进先出,队列出口和入口各占一侧。
- 数组:Array,是有序的元素序列。数组是在内存中开辟一段连续的空间,并在此存放元素。特点是查找元素快(通过数组索引,可以快速定位元素),增删元素慢(每次增删元素都会创建新的数组)。
- 链表:linked list,由一系列节点(链表中每个元素都被称为节点)node组成,结点在运行时动态生成。每个节点包括两部分:存储数据的数据域和指向下一个节点的指针域。特点查找慢(只能通过节点依次往后查找),增删元素快(只需修改链接下个节点的内存地址即可)。
- 红黑树:属于二叉树的一种。二叉树,binary tree,是每个结点不超过2的有序树。红黑树的特点是根节点为黑色,叶子节点是黑色的,每个红色节点的子节点都是黑色,任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同。
二、集合
认识集合
集合是Java中提供的一种容器,可以用来存储多个数据。
集合和数组的区别:
- 数组长度固定,集合长度可变。
- 数组只能存储同一类型元素。集合存储的是对象,对象的类型可以不一致。
1. Collection集合
Collection是单列集合类的根接口,用于存储一系列符合某种规则的元素。
它有两个重要的子接口,分别是java.util.List
和java.util.Set
。
-
List
的特点是元素有序、元素可重复。 -
Set
的特点是元素无序,而且不可重复。
单列集合通用方法 | 功能 |
public boolean add(E e) | 添加指定对象到集合中 |
public void clear() | 清空集合中的所有元素 |
public boolean remove(E e) | 删除当前集合中的指定对象 |
public boolean contains(E e) | 判断当前集合中是否包含指定对象 |
public boolean isEmpty() | 判断集合是否为空 |
public int size() | 返回集合中元素个数 |
public Object[] toArray() | 集合转换数组 |
1.1 List 集合
List 接口常用方法 | 功能 |
public void add(int index, E element) | 将指定的元素,添加到该集合中的指定位置上 |
public E get(int index) | 返回集合中指定位置的元素 |
public E remove(int index) | 移除列表中指定位置的元素, 返回的是被移除的元素 |
public E set(int index, E element) |
用指定元素替换集合中指定位置的元素,返回值的更新前的元素。 |
List
接口的主要实现类有java.util.ArrayList
和java.util.LinkedList。
public class TestList {
public static void main(String[] args) {
// 创建List集合对象
List<String> list = new ArrayList<String>();
// 尾部添加
list.add("1");
list.add("2");
list.add("3");
// 指定位置添加
list.add(1,"没头脑");
// 删除索引位置为2的元素
System.out.println(list.remove(1));
// 修改指定位置元素
list.set(0, "5"); }
1.11 ArrayList 集合
java.util.ArrayList
集合数据存储的结构是数组结构。(见 https://www.cnblogs.com/lyxdw/p/11649759.html 第三节)
1.12 LinkedList集合
java.util.LinkedList
集合数据存储的结构是链表结构。
LinkedList 方法 | 功能 |
public void addFirst(E e) | 将指定元素插入此列表的开头 |
public void addLast(E e) | 将指定元素添加到此列表的结尾 |
public E getFirst() | 返回此列表的第一个元素 |
public E getLast() | 返回此列表的最后一个元素 |
public E removeFirst() | 移除并返回此列表的第一个元素 |
public E removeLast() | 移除并返回此列表的最后一个元素 |
public E pop() | 从此列表所表示的堆栈处弹出一个元素 |
public void push(E e) | 将元素推入此列表所表示的堆栈 |
public boolean isEmpty() | 如果列表不包含元素,则返回true |
在开发时,LinkedList集合也可以作为堆栈,队列的结构使用。(了解即可)
public class LinkedListDemo {
public static void main(String[] args) {
LinkedList<String> link = new LinkedList<String>();
//添加元素
link.addFirst("1");
link.addFirst("2");
link.addFirst("3");
System.out.println(link);
// 获取元素
System.out.println(link.getFirst());
System.out.println(link.getLast());
// 删除元素
System.out.println(link.removeFirst());
System.out.println(link.removeLast()); while (!link.isEmpty()) { //判断集合是否为空
System.out.println(link.pop()); //弹出栈顶元素
}
System.out.println(link);
}
}
1.2 set 集合
Set
接口的主要实现类有java.util.HashSet
。LinkedHashSet是HashSet子类。
区别:
HashSet存储元素无序。
LinkedHashSet
存储元素有序。HashSet集合存储数据的结构是哈希表,LinkedHashSet是链表和哈希表组合的一个数据存储结构。
什么是哈希表?
在JDK1.8之前,哈希表底层采用数组+链表实现,即使用链表处理冲突,同一hash值的链表都存储在一个链表里。但是当一个桶中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。而JDK1.8中,哈希表存储采用数组+链表+红黑树实现,当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间。
public class TestHashSet{
public static void main(String[] args) {
//创建 Set集合
HashSet<String> set = new HashSet<String>();
//添加元素
set.add(new String("1"));
set.add("1");
set.add("2");
//遍历
for (String name : set) {
System.out.println(name);
}
}
}
public class TestLinkedHashSet {
public static void main(String[] args) {
Set<String> set = new LinkedHashSet<String>();
set.add("1");
set.add("2");
set.add("3");
set.add("4");
//迭代器
Iterator<String> it = set.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
}
}
2 . Collections 集合工具类
public static <T> boolean addAll(Collection<T> c, T... elements) | 往集合中添加一些元素 |
public static void shuffle(List<?> list) | 打乱集合顺序 |
public static <T> void sort(List<T> list) | 将集合中元素按照默认规则排序 |
public static <T> void sort(List<T> list,Comparator<? super T> ) | 将集合中元素按照指定规则排序 |
java.utils.Collections
是集合工具类,用来对集合进行操作。
public class TestCollections {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<Integer>();
//添加元素
Collections.addAll(list, 1, 2, 3,4);
//排序
Collections.sort(list);
}
}
//Comparator
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator; public class TestCollections {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("cbae");
list.add("abafaa");
list.add("sba");
list.add("nb");
//排序方法 按照长度排序
Collections.sort(list, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o2.length() - o1.length();
}
});
System.out.println(list);
}
}
//Comparable
public class TestStudent implements Comparable<Student>{
@Override
public int compareTo(Student o) {
return this.age-o.age;//升序
}
}
- Comparable:强行对实现它的每个类的对象进行整体排序。通过实现类 重写 compareTo 方法实现,直接使用Collections.sort(list)即可。
- Comparator:强行对某个对象进行整体排序。可以将Comparator 传递给sort方法(如Collections.sort或 Arrays.sort),从而允许在排序顺序上实现精确控制。还可以使用Comparator来控制某些数据结构(如有序set或有序映射)的顺序,或者为那些没有自然顺序的对象collection提供排序。
3. Map集合
map 集合属于双列集合。存储的数据是多个键值对,并且键不可以重复,值可以。
常用方法 | 功能 |
public V put(K key, V value) | 把指定的键与指定的值添加到Map集合中。 |
public V remove(Object key) | 把指定的键 所对应的键值对元素 在Map集合中删除,返回被删除元素的值。 |
public V get(Object key) | 根据指定的键,在Map集合中获取对应的值。 |
boolean containsKey(Object key) | 判断集合中是否包含指定的键。 |
public Set<K> keySet() | 获取Map集合中所有的键,存储到Set集合中。 |
public Set<Map.Entry<K,V>> entrySet() | 获取到Map集合中所有的键值对对象的集合(Set集合)。 |
HashMap集合
HashMap集合是无序的,存储数据采用的哈希表结构,元素的存取顺序不能保证一致。由于要保证键的唯一、不重复,需要重写键的hashCode()方法、equals()方法。
在HashMap下面有一个子类LinkedHashMap,它是链表和哈希表组合的一个数据存储结构。可以实现有序存取。
import java.util.HashMap;
public class TestMap {
public static void main(String[] args){
//创建HashMap
HashMap<String, String> map = new HashMap<String, String>();
//添加键值对
map.put("1","张三");
map.put("2","李四");
map.put("3","张三");
//获取键对应值
System.out.println(map.get("3"));
//删除键,返回删除键的值
System.out.println(map.remove("2"));
}
}
Map中存在两种对象,key和value,Entry(项)将键值对封装成了对象。
public K getKey()
:获取Entry对象中的键。public V getValue()
:获取Entry对象中的值。
public Set<Map.Entry<K,V>> entrySet()
: 获取到Map集合中所有的键值对对象的集合(Set集合)。
遍历Map集合
import java.util.HashMap;
import java.util.Map.Entry;
public class TestMap {
public static void main(String[] args){
//创建HashMap
HashMap<String, String> map = new HashMap<String, String>();
//添加键值对
map.put("1","张三");
map.put("2","李四");
map.put("3","张三"); for (Entry<String, String> entry : map.entrySet()) {
// 解析
String key = entry.getKey();
String value = entry.getValue();
System.out.println(key+"的值:"+value);
}
}
}
温馨提示
- 如果您对本文有疑问,请在评论部分留言,我会在最短时间回复。
- 如果本文帮助了您,也请评论关注,作为对我的一份鼓励。
- 如果您感觉我写的有问题,也请批评指正,我会尽量修改。