Java 算法常用数据结构实现

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

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

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

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

+ 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() {
        @Override
        public int compare(Student o1, Student o2) {
            return o1.getAge()-o2.getAge();
        }
    });

LinkedList

 Queue 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);
 }

  Stack 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 key：结点唯一标识
HashMap val: 结点信息，包含路径链表

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

HashMap
LinkedHashMap

Map 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");