[数据结构与算法]day_10

1 链表

链表通常是由一连串的结点组成，每一个节点包含任意的实例数据和一个或两个用来指向上一个或下一个节点位置的链接

链表是一种线性表，但是并不会按照线性的顺序存储数据，而在每一个结点里存放下一个节点的指针

1.1 分类

单向链表 ：
一个单链表的节点分为两部分，第一部分保存节点的数据，第二部分保存下一个结点的地址，最后一个节点存储地址的部分指向空值

public class SingleLinkedList {
    // 链表的结点的个数
    private int size;
    //头结点
    private Node head;
    public  SingleLinkedList(){
        size = 0;
        head= null;
    }
    // 链表的结点类
    private class Node{
        private Object data;//结点的数据域
        private Node next;//下一个结点的指针
        public Node(Object data){
            this.data = data;
        }
    }
    // 给链表添加元素  C->B->A
    public Object addHead(Object data){
        Node newHead = new Node(data);// 创建一个新的结点
        if(size == 0 ){
            head = newHead;
        }else{
            newHead.next = head;//新结点的指针指向原来的头结点
            head = newHead;//头结点指向新的结点
        }
        size++;
        return data;
    }
    // 删除结点  在链表头不删除结点
    public  Object deleteHead(){
        Object obj = head.data;
        head = head.next;
        size--;
        return obj;
    }
    //在链表中查找指定的元素，找到了返回结点Node，没找到则返回null
    public Node find(Object data){
        Node current = head;//定义一个指针，指向当前比较的结点
        int tempSize = size;// 获取当前链表中元素的个数
        while(tempSize > 0 ){
            if(data.equals(current.data)){
                return  current;
            }else{
                current = current.next;
            }
            tempSize--;
        }
        return  null;
    }
    // 删除指定的元素  删除成功返回true   否则返回false
    public  boolean delete(Object data){
        if(size == 0 ){
            return  false;
        }
        // 获取删除结点的前一个结点和他的后一个结点
        Node current = head;
        Node previous = head;
        while(!current.data.equals(data)){
            if (current.next == null){// 判断是否到达链表的结尾
                return  false;
            }else{// 当前结点不是我们要删除的结点 并且没有到达结点的末尾
                previous = current;//移动前一个结点的指针
                current = current.next;//移动当前结点的指针指向下一个
            }
        }
        // 此时表明找到了要删除的结点， 判断 删除的结点是否是头结点
        if(current == head){
            head = current.next;
            size--;
        }else{//不是头结点
            previous.next =current.next;
            size--;
        }
        return  true;
    }
    // 判断结点是否为空
    public  boolean isEmpty(){
        return  size==0;
    }
    // 遍历链表
    public  void  display(){
        if(size > 0 ){
            Node node = head;
            int tempSize = size;
            if(tempSize == 1){// 如果当前链表只有一个头结点
                System.out.println("[" + node.data+"]");
                return;
            }
            while(tempSize >0 ){
                if(node.equals(head)){
                    System.out.print("[" + node.data+"->");
                }else if(node.next == null){
                    System.out.print( node.data+"]");
                }else{
                    System.out.print(node.data+"->");
                }
                node= node.next;
                tempSize--;
            }
            System.out.println();
        }else{// 链表没有结点
            System.out.println("[]");
        }
    }
}

1.2 栈 队列 链表 的区别

栈 队列是线性表 操作受限
区别 在于运算规则不同
链表和数组：

1. 占用的内存空间 链表存放的空间可以是连续的，也可以是不连续的，数组一定是连续的。
2. 长度的可变性 ，链表的长度可根据需要自定伸缩 ，数组长度一旦定义就不能更改
3. 数据的访问，链表需要移动访问，不便 数组方便更加便捷
4. 使用场景
   数据量大而且需要进行频繁访问元素，数组更合适
   删除 插入等操作链表更加合适

链表的特点：
逻辑结构 一对一
存储结果 顺序表 链表
运算规则：随机 顺序存放
栈
逻辑结构 一对一
存储结果 顺序栈 链栈
运算规则：先进后出 后进先出
队列
逻辑结构 一对一
存储结果 顺序队 链队
运算规则：先进先出 后进后出

双向链表

循环链表

2 非线性结构（树结构）

2.1 二叉树

每一个元素称为节点 | A—根节点 | B C D----父节点 | H E F G-----叶子节点
叶子节点：没有字节的节点
树的高度： 最大的层数

森林 多棵子树构成森林

每个结点最多只有两个子节点的形式的树称为二叉树

如果所有的二叉树的叶子结点都在最后一次。节点数 = 2^n - 1 ， n就是他的层数 将这样的二叉树称为满二叉树

2.2 二叉树的遍历

前序遍历：先输出父节点 再遍历左子树和右子树

中序遍历：先遍历左子树 在输出父节点 最后遍历右子树

后序遍历：先遍历左子树 再遍历右子树 最后输出父节点

层序遍历：按照层级逐层遍历

2.3 红黑树

红黑树是一种含有红黑结点并能自平衡的二叉树。他必须满足一下的性质：

1 每个结点要么是黑色 要么是红色

2 根节点是黑色

3 每个叶子结点是NIL是黑色

4 每个红色结点的两个子节点一定是黑色

5 任意一个结点到叶子结点的路径都包含数量相同的黑结点

3 集合

数组本身存在一些不可避免地弊端

数组在存储方面的特点：

1. 初始化以后长度确定，不可改变
2. 数组生命的类型就决定了进行元素初始化时地类型

弊端：

1. 初始化之后 长度不可改变 不便于拓展
2. 数组中提供的属性和方法较少，不便于对元素的添加删除从插入等操做，且效率不高，同时无法直接获取存储元素地个数
3. 数组存储的数据是有序的，可以重复

Java 针对存储提供了一种新得结构----集合，可以把动态地把多个对象引用放入到容器中
Java集合可以存储数量不等的多个对象，还可以保存具有映射关系的数据

3.1 集合地体系结构

集合的特点
提供一种存储空间可变的存储模型，存储的数据的容量可随时发生改变

public interface Collection<E>  extends Iterable<E>

集合层次结构中的跟接口，只能存储对象，而其他集合不允许。有的集合石有序的，而有些集合是无序的。JDK不提供此接口的任何直接实现：它提供了更具体的子接口的实现，如Set和List 。 该接口通常用于传递集合，并在需要最大的通用性的情况下对其进行操作。（多态性）

3.2 Collection 接口的使用

Collection 是单列集合的顶层接口，表示一组对象，这些对象也称为元素

JDK不提供此接口的直接实现 但是可以通过的子接口的实现来创建集合对象

    public static void main(String[] args) {
        //创建一个Collection对象
        Collection collection = new ArrayList();
        //Collection接口中的方法 添加元素
        collection.add("Hello");
        collection.add(123);//自动装箱 对应的基本类型的包装类
        collection.add(true);
        System.out.println(collection);
    }

    public static void main(String[] args) {
        //创建一个Collection对象
        Collection collection = new ArrayList();
        //Collection接口中的方法 添加元素
        collection.add("Hello");
        collection.add(123);//自动装箱 对应的基本类型的包装类
        collection.add(true);
       // collection.clear();//清除集合中的元素
        // 判断集合中是否包含某一个对象
        System.out.println(collection.contains(123));
        // 移除集合中的某一个元素
        System.out.println(collection.remove(123));
        // 判断集合是否为空
        System.out.println(collection.isEmpty());
        //获取集合中元素的个数
        System.out.println(collection.size());
        //将一个集合转换为数组
        Object[] arr = collection.toArray();
        System.out.println(arr.length);
        System.out.println(collection);
    }

public class CollectionTest {
    public static void main(String[] args) {
        //创建一个Collection对象
        Collection collection = new ArrayList();
        //Collection接口中的方法 添加元素
        collection.add("Hello");
        collection.add(123);//自动装箱 对应的基本类型的包装类
        collection.add(true);
        Collection c1 = new ArrayList();
        c1.add("world");
        c1.add("hello");
        c1.add(false);
        Student stu1 = new Student("张三",18);
        c1.add(stu1);
        // addAll
        collection.addAll(c1);
        System.out.println(collection);
        //判断集合中是否包含另一个集合中的所有元素
        System.out.println(collection.containsAll(c1));
        // 取两个集合的交集  存放在当前集合中
        collection.retainAll(c1);
        System.out.println(collection);
        //删除此集合中的另一个集合
//        collection.removeAll(c1);
//        System.out.println(collection);
    }

3.2.1 Iterator

迭代集合的迭代器

| `E`       | `next()`  返回迭代中的下一个元素。                  |

    public static void main(String[] args) {
        //创建一个Collection对象
        Collection collection = new ArrayList();
        //Collection接口中的方法 添加元素
        collection.add("Hello");
        collection.add(123);//自动装箱 对应的基本类型的包装类
        collection.add(true);
        collection.add("world");
        collection.add("hello");
        collection.add(false);
        Student stu1 = new Student("张三",18);
        collection.add(stu1);
        // 迭代器迭代集合
       Iterator iter =  collection.iterator();
       // 使用迭代器来迭代集合
       while(iter.hasNext()){
         Object obj =   iter.next();
           System.out.println(obj);
       }
    }

    public static void main(String[] args) {
        //创建一个Collection对象
        Collection collection = new ArrayList();
        //Collection接口中的方法 添加元素
        collection.add("Hello");
        collection.add(123);//自动装箱 对应的基本类型的包装类
        collection.add(true);
        collection.add("world");
        collection.add("hello");
        collection.add(false);
        Student stu1 = new Student("张三",18);
        collection.add(stu1);
        // 迭代器迭代集合
       Iterator iter =  collection.iterator();
       // 使用迭代器来迭代集合
       while(iter.hasNext()){
         Object obj =   iter.next();
           System.out.println(obj);
       }
    }

3.3 List

3.3.1 List集合的特点

• 有序集合（也称为 序列 ）
  可以精确控制列表中每个元素的插入位置。 用户可以通过整数索引（列表中的位置）访问元素，并搜索列表中的元素。

• 列表通常允许重复的元素

• 可以存储null 并且可以存储多个

  典型实现ArrayList LinkedList Vector

3.3.2 List接口特有方法

add(int index, Object element) 将指定的元素插入此列表中的指定位置（可选操作）。

3.3.3. List的使用

public class ListTest {
    public static void main(String[] args) {
        Student stu1 = new Student("张三",18);
        Student stu2 = new Student("李四",21);
        Student stu3 = new Student("王五",20);
        Student stu4 = new Student("赵六",22);
        List list = new ArrayList();
        list.add(stu4);
        list.add(stu3);
        list.add(stu2);
        list.add(stu1);
        list.add(stu1);
        list.add(stu2);
        list.add(stu3);
        list.add(stu4);
       Iterator iter =  list.iterator();
       while(iter.hasNext()){
           Object obj = iter.next();
           System.out.println(obj);
       }
        System.out.println("------------------------------");
       for(int i = 0 ; i < list.size();i++){
            Object obj = list.get(i);
           System.out.println(obj);
       }
    }
}

List集合的有序：这里的有序指的是元素的存入顺序和迭代的顺序是一致的

集合的迭代方式

   public static void main(String[] args) {
        Student stu1 = new Student("张三",18);
        Student stu2 = new Student("李四",21);
        Student stu3 = new Student("王五",20);
        Student stu4 = new Student("赵六",22);
        List list = new ArrayList();
        list.add(stu4);
        list.add(stu3);
        list.add(stu2);
        list.add(stu1);
        list.add(stu1);
        list.add(stu2);
        list.add(stu3);
        list.add(stu4);
       Iterator iter =  list.iterator();
       while(iter.hasNext()){
           Object obj = iter.next();
           System.out.println(obj);
       }
        System.out.println("------------------------------");
       for(int i = 0 ; i < list.size();i++){
            Object obj = list.get(i);
           System.out.println(obj);
       }
        System.out.println("------------------------------");
       for(Object obj : list){
           System.out.println(obj);
       }
        System.out.println("------------------------------");
       for(  Iterator itr =  list.iterator();itr.hasNext();){
           Object obj = itr.next();//在使用迭代器迭代的时候  在一个循环中  next方法只能在一处调用
           System.out.println(obj);
       }
        System.out.println("------------------------------");
        Iterator itr1 =  list.iterator();
        for(;itr1.hasNext();){
            Object obj = itr1.next();//在使用迭代器迭代的时候  在一个循环中  next方法只能在一处调用
            System.out.println(obj);
        }
    }

迭代器使用while和for那个更好：

• for循环更利于空间的释放 但是在开发中 普遍使用while

3.3.4 并发修改异常

    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("hello");
        list.add("world");
        list.add("java");
        Iterator iter =  list.iterator();
        while(iter.hasNext()){
            Object obj = iter.next();
            String str = (String) obj;
            if(str.equals("world")){
                list.add("hadoop");
            }
        }
    }

ConcurrentModificationException ： 并发修改异常

产生原因：

? 迭代器在迭代集合的过程中，通过集合对象修改了集合的元素，造成迭代器获取园中判断预期修改值和实际修改值不一致

解决方案：通过集合本身来进行遍历集合，有集合自己修改

for(int i = 0 ; i < list.size();i++){
    String str = (String)list.get(i);
    if(str.equals("world")){
      //  list.add("hadoop");//新增  新增到集合的末尾
        list.set(i,"hadoop");// 修改元素
    }
}
System.out.println(list);

3.3.5 ListIteator

public class ListDemo {
    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("hello");
        list.add("world");
        list.add("java");
        // 获取列表迭代器
       ListIterator iterator =  list.listIterator();
       // 遍历同时天剑
        while(iterator.hasNext()){
            Object obj = iterator.next();
            // 当遇到元素为world的时候  给列表追加元素spring
            if(obj.equals("world")){
                iterator.add("spring");
                iterator.previous();//是的指针指向前一个元素
            }
            System.out.println(obj);
        }
        System.out.println(list);
        System.out.println("-----------------------");
        //迭代的同时删除元素
        ListIterator iterator1 =  list.listIterator();
        while(iterator1.hasNext()){
            Object obj = iterator1.next();
            if(obj.equals("world")){
                iterator1.remove();
            }else{
                System.out.println(obj);
            }
        }
        System.out.println("-----------------------");
        //修改
        ListIterator iterator2 =  list.listIterator();
        while(iterator2.hasNext()){
            Object obj = iterator2.next();
            if(obj.equals("hello")){
                iterator2.set("mybatis");
                iterator2.previous();

            }else{
                System.out.println(obj);
            }
        }
    }
}

    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("hello");
        list.add("world");
        list.add("java");
        ListIterator iter = list.listIterator();
        while(iter.hasNext()){
            Object obj = iter.next();
            System.out.println(obj);
        }
        System.out.println("----------------------");//在逆序之前必须先正序遍历  
        while(iter.hasPrevious()){
            Object obj = iter.previous();
            System.out.println(obj);
        }
    }

       List sub =  list.subList(1,2);//获取子集  包含1  不包含2
        System.out.println(sub);