Java 算法常用数据结构实现

目录

• 线性表
• • 数组
  • • 排序
    • 查找
  • List
  • • 排序
• 队列
• • 示例
  • 基本方法
• 栈
• • 示例
• 树
• • 说明
  • 堆（完全二叉树）
• 图
• • 实现一： HashMap + List
  • 实现二：二维数组
• 散列
• • 示例

线性表 数组 排序

基础类型排序（升序） Arrays.sort(int[] arr)
自定义排序

//students 按照age升序排序
Arrays.sort(students, new Comparator<Student>() {
     @Override
     public int compare(Student o1, Student o2) {
         return o1.getAge()-o2.getAge();
     }
 });

查找

int index = Arrays.binarySearch(numsArr, 3);

List

+ ArrayList
+ LinkedList 

排序

排序一： 实现Comparable接口

	public class Student implements Comparable{
	  	···
	    @Override
	    public int compareTo(Object o) {
	        return this.getAge()-((Student)o).getAge();
	    }
	}
    //studentList = studentList.stream().sorted().collect(Collectors.toList());
    Collections.sort(studentList);

排序二 ：实现Comparator接口

 Collections.sort(studentList, new Comparator<Student>() {
        @Override
        public int compare(Student o1, Student o2) {
            return o1.getAge()-o2.getAge();
        }
    });

队列 示例

LinkedList

 Queue<Student> studentQueue = new LinkedList();
 for (int i=0;i<10;i++){
 	 //入队
     studentQueue.offer( new Student(Math.abs(random.nextInt()%100),"name"+i));
 }
 //判断队列是否为空
 while (studentQueue.isEmpty()){
 	//出队
     Student stu = studentQueue.poll();
     System.out.println(" "+ stu);
 }

基本方法

*** 作	方法	返回值	说明
队尾添加	add	true： 添加成功	超出容量限制时抛出异常
队尾添加	offer	true：添加成功；false：添加失败	超出容量限制时返回false
删除并返回队头元素	remove	移除的元素	队列为空抛异常
删除并返回队头元素	poll	队列为空返回null
返回队头元素	element		队列为空抛异常
返回队头元素	peek		队列为空返回null
判断队列是否为空	isEmpty	true:空 false:非空

栈 示例

  Stack<Student> studentStack = new Stack();
    for (int i=0;i<10;i++){
    	//压栈
        studentStack.push( new Student(Math.abs(random.nextInt()%100),"name"+i));
    }
    //判断栈是否为空
    while (!studentStack.isEmpty()){
    	//出栈
        Student stu = studentStack.pop();
        System.out.println(" "+ stu);
    }

树 说明

自定义数据对象

堆（完全二叉树）

数组

图 实现一： HashMap + List

HashMap key：结点唯一标识
HashMap val: 结点信息，包含路径链表

实现二：二维数组

a[i][j] ： i、j标识节点，对应的值表示 i->j权重（或是否联通）

散列

HashMap
LinkedHashMap

示例

Map<String,Integer> map = new HashMap<>();
//添加元素
map.put("a",100);
//判断是否包含key
if(map.containsKey("a")){
	//根据key获取元素
	Integer a = map.get("a");
}
//根据key获取元素，不包含返回默认值
Integer b = map.getOrDefault("b",0);
//根据key删除元素
map.remove("a");