Java集合-数据结构之栈、队列、数组、链表和红黑树

数据结构部分，复习栈，队列，数组，链表和红黑树，参考博客和资料学习后记录到这里方便以后查看，感谢被引用的博主。

栈

栈(stack)又称为堆栈，是线性表，它只能从栈顶进入和取出元素，有先进后出，后进先出(LIFO, last in first out)的原则，并且不允许在除了栈顶以外任何位置进行添加、查找和删除等操作。栈就相当如手枪的弹夹，先进入栈的数据被压入栈底(bottom)，而后入栈的数据存放在栈顶(top)。当需要出栈时，是先让栈顶的数据出去后，下面的数据才能出去，这就是先进后出的特点。插入数据一般称为进栈或压栈(push)，删除数据则称为出栈或弹栈(pop)。

下面参考博文，地址：https://www.cnblogs.com/ysocean/p/7911910.html，底层使用数组来模拟一个栈的功能，具有push，pop，peek等常用方法，原生的stack是继承自vector类的子类，其具备父类的所有方法，这里模拟除了前面三种方法外，还写了判断自定义栈是否为空，以判断自定义栈是否满等方法。

自定义栈，底层采用数组模拟

package dataStructure;
/**
 * 自定义栈，使用数组来实现
 */
public class MyStack {
    
    private int size;//数组大小
    private String[] arr;//数组
    private int top=-1;//默认栈顶位置
    
    //构造方法
    public MyStack(int size) {
        this.size = size;
        arr=new String[size];
    }
    
    //压栈
    public void push(String value){
        //top范围0到size-1
        if(top<=size-2){
            arr[++top]=value;
        }
    }
    
    //出栈
    public String pop(){
        //原栈顶元素设置为null，等待gc自动回收
        return arr[top--];
    }
    
    //查看栈顶
    public String peek(){
        if(top>-1){
            return arr[top];
        }else{
            return null;
        }
    }
    
    //检查栈是否为空
    public boolean Empty(){
        return top<0;
    }
    
    //检查栈是否满
    public boolean Full(){
        return top==size-1;
    }
    
    //检查栈中元素数量
    public String size(){
        int count=top+1;
        return "栈中元素:"+count+" | 栈容量"+size;
    }    
            
}

测试代码，验证自定义栈中的方法。

package dataStructure;

public class TestMyStack {

    public static void main(String[] args) {
        //测试自定义Stack
        MyStack stack=new MyStack(3);
        //压入栈顶
        stack.push("Messi");
        stack.push("Ronald");
        stack.push("Herry");
        
        //查看栈中元素数量
        System.out.println(stack.size());
        
        //查看栈顶元素
        System.out.println(stack.peek());
        
        //循环遍历栈中元素
        while(!stack.Empty()){
            System.out.println(stack.pop());
        }
        
        //判断栈是否为空
        System.out.println(stack.Empty()); //true
        System.out.println(stack.size());

    }

}

控制台输出情况。

自定义一个栈，实现数组自动扩容并能储存不同的数据类型

在上面例子的基础上，依然参考上述博文，自定义一个栈并能实现栈容量自动扩容，以及栈中可以存储不同的数据类型。

package dataStructure;

import java.util.Arrays;
import java.util.EmptyStackException;

/**
 * 自定义栈，使用数组来实现，可以实现数组自动扩容，以及存储不同的数据类型
 */
public class MyArrayStack {
    //定义属性
    private int size;//容量
    private Object[] arr;//对象数组
    private int top;//栈顶位置
    
    //默认构造方法
    public MyArrayStack() {
        this.size=10;
        this.arr=new Object[10];
        this.top=-1;
    }

    //自定义数组容量的构造方法
    public MyArrayStack(int size) {
        if(size<0){
            throw new IllegalArgumentException("栈容量不能小于0"+size);
        }
        this.size = size;
        this.arr=new Object[size];
        this.top=-1;
    }
    
    //压栈
    public Object push(Object value){
        //压栈之前欠判断数组容量是否足够，不够就扩容
        getNewCapacity(top+1);
        arr[++top]=value;
        return value;        
    }
    
    //出栈
    public Object pop(){
        if(top==-1){
            throw new EmptyStackException();
        }
        Object obj=arr[top];
        //删除原来栈顶的位置，默认设置为null，等待gc自动回收
        arr[top--]=null;
        return obj;
    }
    
    //查找栈顶的元素
    public Object peek(){
        return arr[top];
    }
    
    //判断栈是否为空
    public boolean Empty(){
        return top==-1;
    }
    
    //检查栈中元素
    public String size(){
        int count=top+1;
        return "栈中元素:"+count+" | 栈容量"+size;
    }
    
    //返回栈顶到数组末端内容
    public void printWaitPosition(){
        if(top<arr.length-1){
            for(int i=top+1;i<arr.length;i++){
                System.out.println("空闲位置数值为："+arr[i]);
            }            
        }else{
            System.out.println("没有空闲位置");
        }
    }
    
    
    //写一个方法判断数组是否需要自动扩容
    public boolean getNewCapacity(int index){
        //判断压入后的数组下标，是否超过了数组容量限制，超出就扩容
        if(index>size-1){
            //扩容2倍
            int newSize=0;
            if((size<<1)-Integer.MAX_VALUE>0){
                newSize=Integer.MAX_VALUE;
            }else{
                newSize=size<<1;
            }
            //数组扩容后复制原数组数据，扩容的部分，默认为Object初始值
            this.size=newSize;
            arr=Arrays.copyOf(arr, newSize);
            return true;
        }else{
            return false;
        }
    }
}

测试代码，验证自动扩容，空闲位置是什么。

package dataStructure;

public class TestMyArrayStack {

    public static void main(String[] args) {
        // 测试自定义MyArrayStack
        MyArrayStack stack=new MyArrayStack(2);
        stack.push("Messi");
        stack.push("Ronald");
        System.out.println(stack.size());
        System.out.println(stack.peek());
        //超出容量后继续压栈
        stack.push("boy you will have a good future");
        System.out.println(stack.size());
        System.out.println(stack.peek());
        //打印stack中空闲位置内容
        stack.printWaitPosition();
        //压入数字
        stack.push(8848);
        System.out.println(stack.size());
        System.out.println(stack.peek());
        stack.printWaitPosition();
        //压入布尔类型
        stack.push(true);
        System.out.println(stack.size());
        System.out.println(stack.peek());
        stack.printWaitPosition();    
    }
}

控制台输出情况。

在参考博文中，栈除了以上用途外，还可以巧妙用在将字符串反转，还有验证分隔符是否匹配，以后如果有需要可以参考引用的博文。

队列

队列(queue)，跟堆栈类似，也是线性表，它是仅允许在尾部(tail)进行插入，在头部(head)进行删除，满足先进先出(FIFO)的原则，类似火车头进入山洞，先进入山洞的车厢就先出来山洞，后进入山洞的火车头后出来山洞。查看队列源码，可以看到接口有如下方法。

简单的整理一下如下。

（1）插入元素到tail尾部：add(e)，offer(e)，前者为执行失败时抛出异常，后者不会抛出但返回特殊值(null或false)。

（2）移除head头部元素：remove()，poll()，前者为执行失败时抛出异常，后者不会抛出但返回特殊值(null或false)。

（3）查看列头head元素：element()，peek()，前者为执行失败时抛出异常，后者不会抛出但返回特殊值(null或false)。

下面分别使用两种类型的方法进行queue操作。

使用会抛出异常的方法

package DataCompose;

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 测试队列，队列Queue具有先进先出的特点
 */
public class QueueTest {

    public static void main(String[] args) {
        //创建一个队列，使用LinkedList来创建对象，并被接口指向
        Queue<String> queue=new LinkedList<String>();
        //Queue<String> queue=new PriorityQueue<String>();
        //使用会抛出异常的方法，添加元素到尾部，删除头部元素，以及查看头部元素操作

        //1 添加元素 add方法
        queue.add("Messi");
        queue.add("Herry");
        queue.add(null);
        System.out.println(queue);

        //2 删除头部元素 remove方法
        String str=queue.remove();
        System.out.println(str);
        System.out.println(queue);

        //3 查看头部元素 element方法
        System.out.println(queue.element());

    }
}

控制台输出结果，可以看出如果实现类为LinkedList时可以插入null，并且看出先加入的Messi，如果执行remove方法后也是先移除，执行element方法也是先查询得到头部元素，因此遵循先进先出原则。

如果不往集合中add元素，直接执行remove方法会发生如下报错，提示没有元素异常，并发现执行remove方法，会执行LinkedList底层的removeFirst方法，说明其移除的就是第一个元素。

同样如果不往集合中添加元素，直接执行element方法会报如下错，也提示没有元素异常，并发现执行element方法时会调用底层的getFirst方法，说明它取得是第一个元素。

可以看出当队列的实现类为LinkedList时，是可以插入null的，如果把实现类更换为PriorityQueue，会发生什么呢？发现会报空指针异常，原因是优先队列不允许插入null。

以上是使用queue的add，remove和element方法，上述同样的情况下，如果更换成offer，poll和peek方法后会是什么情况，看如下代码测试。

package DataCompose;

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 测试队列，队列Queue具有先进先出的特点
 */
public class QueueTest1 {

    public static void main(String[] args) {
        //创建一个队列，使用LinkedList来创建对象，并被接口指向
        Queue<String> queue=new LinkedList<String>();
        //Queue<String> queue=new PriorityQueue<String>();
        //使用会抛出异常的方法，添加元素到尾部，删除头部元素，以及查看头部元素操作

        //1 添加元素 offer方法
        queue.offer("Messi");
        queue.offer("Herry");
        queue.offer(null);
        System.out.println(queue);

        //2 删除头部元素 poll方法
        String str=queue.poll();
        System.out.println(str);
        System.out.println(queue);

        //3 查看头部元素 peek方法
        System.out.println(queue.peek());

    }
}

以上代码正常情况下执行跟第一种情况一模一样的结果，如果集合为空，直接调用poll方法和peek方法，查看执行结果如下，发现输出均为null，说明在集合为空的情况下这两种方法不会抛出异常。

同样如果将实现类更换为PriorityQueue，往里面添加null，会是什么结果呢？发现依然抛出异常，主要原因查看offer源码发现，如果实现类不支持null就会抛出异常。

另外还有一个deque，是queue的子接口，为双向队列，可以有效的在头部和尾部同时添加或删除元素，其实现类为ArrayDeque和LinkedList类，如果需要一个循环数组队列，选择ArrayDeque，如果需要一个链表队列，使用实现了Queue接口的LinkedList类。

由于Deque实现了Queue接口，因此其可以表现为完全的Queue特征，同时也可以当做栈来使用，具体是Queue还是栈，根据执行的方法来选择，一般来说如果添加元素和删除元素都是在同一端执行(方法后面都为First)，就表现为栈的特性，否则就是Queue的特性，以下是Deque接口的方法。

从以上的方法列表中，大概可以总结出以下几个特点：

（1）凡是以add，remove和get开头的方法，都可能在执行的过程中抛出异常，而以offer，poll和peek的方法往往返回null或者其他。

（2）凡是方法后面有Queue接口标志的方法，说明其是继承自接口Queue的方法，有Collection标志的说明是继承自Collection接口的通用方法。

Deque方法参考博文，分类总结如下：

deque和栈的方法对照表

deque和queue的方法对照表

deque中抛出异常和返回其他值的方法

 下面简单的用deque的方法来实现集合操作，从队列两端添加，删除和查看元素，和栈以及queue的相关方法不在这里测试了，未来工作中继续感受。

package DataCompose;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 测试双向队列，其可以表现为Queue，也可以表现为Stack，这里测试双向列队
 */
public class DequeTest {

    public static void main(String[] args) {
        //使用链表实现
        Deque<String> deque=new LinkedList<>();

        //先在head插入元素
        deque.offerFirst("Messi");
        deque.offerFirst("Ronald");
        deque.offerFirst("Herry");
        System.out.println(deque);

        //在tail插入元素
        deque.offerLast("clyang");
        System.out.println(deque);

        //在head查看元素
        System.out.println(deque.peekFirst());

        //在tail查看元素
        System.out.println(deque.peekLast());

        //在head删除元素
        deque.pollFirst();
        System.out.println(deque);

        //在tail删除元素
        deque.pollLast();
        System.out.println(deque);

    }
}

控制台输出结果，可以看出deque可以在head和tail两端进行插入、删除和查看操作。

数组

数组(Array)，是一种有序的元素序列，数组在内存中开辟一段连续的空间，并在连续的空间存放数据，查找数组可以通过数组索引来查找，因此查找速度快，但是增删元素慢。数组创建以后在程序运行期间长度是不变的，如果要增加一个元素，会创建一个新的数组，将新元素存储到索引位置，并将原数组根据索引一一复制到新数组，原来的数组被gc回收，新数组的内存地址赋值给数组变量。

关于数组部分，直接可以从自己写的博客查看具体内容，博客地址：https://www.cnblogs.com/youngchaolin/p/10987960.html，另外参考了大牛博客，进行一些知识面的扩展。

底层利用数组，也可以实现数据结构的基本功能，简单概括一下，就是需要具备增删改查循环遍历的功能，这样才能算实现基本的数据结构，下面参考博客，进行这些功能的封装，实现一个基于数组的简单数据结构。

package DataCompose;

/**
 * 数组测试，理解最基本数据结构，利用数组封装一个简单的数据结构，实现增删改查和循环遍历
 */
public class ArrayTest {
    //底层数组，使用Object类型
    private Object[] arr;
    //数组占用长度
    private int length;
    //数组容量
    private int maxSize;

    //默认构造方法，仿造ArrayList，默认长度为10
    public ArrayTest() {
        this.length=0;
        this.maxSize=10;
        arr=new Object[maxSize];
    }

    //自定义数组长度
    public ArrayTest(int maxSize) {
        this.maxSize = maxSize;
        this.length=0;
        arr=new Object[maxSize];
    }
    //增加元素
    public boolean add(Object obj){
        //增加元素暂时不使用底层再创建一个新的数组，进行数组内容复制，参考博客直接添加
        if(length==maxSize){
            System.out.println("数组容量达到极限，无法自动扩容");
            return false;
        }
        //原数组后面再添加一个元素，否则就是初始值null
        arr[length++]=obj;
        return true;
    }
    //查找元素，本来先要写删，但是删元素之前需要先查是否存在，因此先写查询方法
    public int find(Object obj){
        int n=-1;
        for (int i= 0; i< length; i++) {
            if(obj.equals(arr[i])){
                n=i;
                break;
            }
        }
        return n;
    }
    //删除元素
    public boolean remove(Object obj){

        if(obj==null){
            System.out.println("不能删除null，请输入正常内容");
            return false;
        }
        int index=find(obj);
        if(index==-1){
            System.out.println("不存在的元素:"+obj);
            return false;
        }
        //数组元素覆盖操作
        if(index==length-1){
            length--;
        }else{
            for(int i=index;i<length-1;i++){
                arr[i]=arr[i+1];
            }
            length--;
        }
        return true;
    }
    //修改元素，直接修改数组索引上的元素
    public boolean modify(int index,Object obj){
        if(index<0||index>length-1){
            System.out.println("数组下标越界");
            return false;
        }else{
            arr[index]=obj;
            return true;
        }
    }
    //遍历输出内容
    public void toArrayString() {
        System.out.print("[");
        for (int i = 0; i < length; i++) {
            if(i<length-1){
                System.out.print(arr[i] + ",");
            }else{
                System.out.print(arr[i]);
            }
        }
        System.out.print("]");
        //换行
        System.out.println();
    }

}

测试类来测试上面写的数据结构。

package DataCompose;

/**
 * 测试自己底层用数组写的数据结构
 */
public class TestArrayTest {

    public static void main(String[] args) {
        ArrayTest arr=new ArrayTest(5);
        //添加元素
        arr.add("boy you will have girl");
        arr.add(true);
        arr.add("how many would you like");
        arr.add(1);

        //打印数组
        arr.toArrayString();

        //查询为1的元素
        System.out.println(arr.find(1));

        //查询'你好'
        System.out.println(arr.find("你好"));

        //修改下标为3的数组为100
        arr.modify(3,100);
        arr.toArrayString();

        //再添加一个元素
        arr.add("哈哈哈");
        arr.toArrayString();

        //继续添加
        arr.add("ok?");

        //删除最后的元素
        boolean result=arr.remove("哈哈哈");
        System.out.println(result);
        arr.toArrayString();

    }
}

控制台输出情况，发现可以正常的实现增删改查和循环遍历的功能。

链表

链表(linked list),是由一系列结点node组成，结点包含两个部分，一个是存储数据的数据域，一个是存储下一个节点地址以及自己地址的地址域，即链表是双向链接的(double linked)，多个节点通过地址进行连接，组成了链表，其特点是增删元素快，只要创建或删除一个新的节点，内存地址重新指向规划就行，但是查询元素慢，需要通过连接的节点从头开始依次向后查找。
链表有单向链表和双向链表之分。
单向链表：链表中只有一条'链子'，元素存储和取出的顺序可能不一样，不能保证元素的顺序。
双向链表：链表中除了有单向链表一条链子外，还有一条链子用于记录元素的顺序，因此它可以保证元素的顺序。

单向链表的实现

依然参考博主系列文章的链表，自己实现一个自定义的链表，并具有增加头部元素、删除指定元素、修改指定元素、查找元素以及展示链表内容等功能。

package DataCompose;

/**
 * 单向列表测试，
 */
public class SingleLinkTest {
    //定义链表大小
    private int size;
    //定义头节点，只需要定义一个头，其他元素都可以通过这个节点头来找到
    private Node head;

    public SingleLinkTest() {
        this.size = 0;
        this.head = null;
    }

    //在链表头部增加元素
    public Object addHead(Object obj) {
        //得到一个新的节点
        Node newNode = new Node(obj);
        //链表为空，将头元素数据设置为obj
        if (size == 0) {
            head = newNode;
        } else {
            newNode.next = head;
            head = newNode;
        }
        this.size++;
        return obj;
    }

    //在链表中删除元素
    public boolean delete(Object obj) {
        //要删除一个元素，需要首先找到这个元素，将这个元素前一个元素next属性指向这个元素的下一个元素
        if (size == 0) {
            System.out.println("链表为空，无法删除！");
            return false;
        }
        //都是从头部开始查询，有找到需要删除的节点就删除，删除后将这个节点前一个节点next属性指向删除节点的下一个节点
        //需要重新指向的话，需要删除节点数据，也需要删除节点前一个节点的数据，刚开始都使用头部节点数据
        Node previousNode = head;
        Node currentNode = head;
        //什么时候找到这个元素什么时候停止
        while (!currentNode.data.equals(obj)) {
            //节点往后遍历，寻找下一个节点数据
            if (currentNode.next == null) {
                System.out.println("已到链表末尾，无需要删除的元素");
                return false;
            } else {
                //重置当前结点和当前结点前一个结点
                previousNode = currentNode;
                currentNode = currentNode.next;
            }
        }

        //能执行到这里说明有需要删除的元素
        size--;
        if (currentNode == head) {
            head = currentNode.next;
        } else {
            previousNode.next = currentNode.next;
        }
        return true;
    }

    //修改元素
    public boolean modify(Object old, Object newObj) {
        if (size == 0) {
            System.out.println("链表为空，无法修改元素");
            return false;
        }
        Node currentNode = head;
        while (!currentNode.data.equals(old)) {
            if (currentNode.next == null) {
                System.out.println("已到链表末尾，无需要删除的元素");
                return false;
            } else {
                currentNode = currentNode.next;
            }
        }

        //能执行到这里说明有相同的元素
        currentNode.data = newObj;
        return true;

    }

    //查找元素
    public boolean find(Object obj) {
        if (size == 0) {
            System.out.println("链表为空");
        }
        Node currentNode = head;
        while (!currentNode.data.equals(obj)) {
            if (currentNode.next == null) {
                System.out.println("已到链表末尾，无查找的元素");
                return false;
            } else {
                currentNode = currentNode.next;
            }
        }

        //能执行到这里说明查找到了元素
        System.out.println("查找元素存在链表中");
        return true;
    }

    //遍历输出元素
    public void toLinkString() {
        if (size > 0) {
            if (size == 1) {
                System.out.println("[" + head.data + "]");
            }
            //结点先从头部开始
            Node currentNode = head;
            for (int i = 0; i < size; i++) {
                if (i == 0) {
                    System.out.print("[" + currentNode.data);
                } else if (i < size - 1) {
                    System.out.print("--->" + currentNode.data);
                } else{
                    System.out.print("--->"+currentNode.data+"]");
                }
                currentNode = currentNode.next;
            }
        } else {
            System.out.println("[]");
        }
        System.out.println();
    }

}

Node外部类，参考很多博客都是写成内部类，也可以写成外部类。

package DataCompose;

/**
 * 节点，外部类实现，自定义链表用
 */
public class Node {
    //数据部分
    public Object data;
    //指向下一个节点，没有修改其中值得情况下默认为null
    public Node next;

    public Node(Object data) {
        this.data = data;
    }

}

测试类代码。

package DataCompose;

/**
 * 测试自定义单向链表
 */
public class TestSingleLinkTest {

    public static void main(String[] args) {
        //默认容量为0的链表
        SingleLinkTest Link=new SingleLinkTest();
        //头部添加元素
        Link.addHead("clyang");
        Link.addHead(8848);
        Link.addHead(true);
        Link.toLinkString();

        //查找元素8848
        boolean r=Link.find(8848);
        System.out.println(r);

        //更新元素
        Link.modify(8848,"success people");
        Link.toLinkString();

        //删除元素
        Link.delete("Messi");
        Link.toLinkString();

    }
}

控制台输出结果，发现可以正常表现为链表的功能。

双向链表的实现

参考博客，以及自己的理解，实现一个双向链表，同时可以保持链表的有序，可以根据索引来查找链表内容。

package DataCompose;

import java.util.Random;

/**
 * 双向链表，自定义一个双向列表，具备增删改查和循环遍历的功能
 */
public class DoubleLinkTest {
    //属性
    private int size;
    private Node head;
    private Node tail;


    //内部类，里面定义一个属性保存数据，再定义两个属性分别指向上一个节点以及下一个节点
    private class Node {
        //数据部分
        private Object data;
        //上一个节点和下一个节点的引用
        private Node prev;
        private Node next;
        //序号部分
        private int number;

        //构造方法
        public Node(Object data) {
            this.data = data;
        }

        public Node(Object data, int number) {
            this.data = data;
            this.number = number;
        }
    }

    //默认构造方法
    public DoubleLinkTest() {
        this.size = 0;
        this.head = null;
        this.tail = null;
    }

    //往头增加节点
    public void addHead(Object obj) {
        //往头部增加节点，默认索引号为-1
        Node myNode = new Node(obj, -1);
        //链表为空
        if (size == 0) {
            head = myNode;
            tail = myNode;
            head.number = 0;
            tail.number = 0;
        } else {
            head.prev = myNode;
            myNode.next = head;
            //头节点重新赋值
            head = myNode;
        }
        size++;
        //刷新编号，所有索引号往后面移动一位
        flushNumber(1);
        //System.out.println("头部增加一个结点成功");
    }

    //往尾部添加节点
    public void addTail(Object obj) {
        Node myNode = new Node(obj);
        //链表为空
        if (size == 0) {
            tail = myNode;
            head = myNode;
            head.number = 0;
            tail.number = 0;
        } else {
            tail.next = myNode;
            myNode.prev = tail;
            //尾部节点重新赋值
            tail = myNode;
        }
        size++;
        //尾部序号直接赋值，相比头部序号操作简单很多
        tail.number = size - 1;
        //System.out.println("尾部增加一个结点成功");
    }

    //往链表内部，除了头部节点之前的任意一个结点插入新节点
    public void add(Object obj) {
        if (size == 0) {
            addHead(obj);
        } else if (size == 1) {
            addTail(obj);
        } else if (size >= 2) {
            //根据链表中的现有长度，获取0~长度-1之间的随机数，将这个随机数作为要插入结点的前一个索引号
            Random ran = new Random();
            int insertIndex = ran.nextInt(size);
            //得到要插入位置的前后索引编号
            int before = insertIndex;
            int after = insertIndex + 1;
            //如果before的索引已经达到链表末尾
            if (before == size - 1) {
                //尾部添加即可
                addTail(obj);
            } else {
                //获取插入结点的前后结点
                Node beforeNode = getNodeByIndexAndStartNode(before, head);
                Node afterNode = getNodeByIndexAndStartNode(after, head);
                Node startNode = afterNode;
                //获取要插入的结点
                Node currentNode = new Node(obj, after);
                //重新连接前后结点
                beforeNode.next = currentNode;
                currentNode.prev = beforeNode;
                afterNode.prev = currentNode;
                currentNode.next = afterNode;
                //序号更新，将后面一个结点的所有索引号+1
                int startIndex = after;
                while (startIndex <= size - 1) {
                    int newIndex = startNode.number + 1;
                    startNode.number = newIndex;
                    startNode = startNode.next;
                    startIndex++;
                }
                size++;
            }
            System.out.println("当元素大于或等于2个时，随机插入结点成功");
        }
    }

    //通过索引位置，找到对应的节点，另外第二个参数代表从头开始找还是从尾开始找
    public Node getNodeByIndexAndStartNode(int index, Node node) {
        if (index < 0 || index > size - 1) {
            System.out.println("索引越界，无效索引");
            return null;
        } else {
            //当前结点
            Node currentNode = node;
            int count = size;
            while (count > 0) {
                if (currentNode.number != index) {
                    //区分node是从头开始还是从尾开始
                    if (node.equals(head)) {
                        currentNode = currentNode.next;
                    } else if (node.equals(tail)) {
                        currentNode = currentNode.prev;
                    }
                } else {
                    break;
                }
                count--;
            }
            return currentNode;
        }
    }

    //查找一个节点，可以使用二分查找，调用上面写的底层查找方法
    public Node findNodeByIndex(int index) {
        Node deleteNode=null;
        if (size == 0) {
            System.out.println("链表为空");
            return null;
        } else {
            if (index < size / 2) {
                //从头开始寻找
                Node node = getNodeByIndexAndStartNode(index, head);
                //System.out.println(node.data);
                deleteNode=node;
            } else {
                //从尾开始寻找
                Node node = getNodeByIndexAndStartNode(index, tail);
                //System.out.println(node.data);
                deleteNode=node;
            }
        }
        System.out.println(deleteNode.data);
        return deleteNode;
    }

    //删除一个节点，根据链表中索引来删除
    public boolean deleteNodeByIndex(int index) {
        if (index < 0 || index > size - 1) {
            System.out.println("下标越界，无法删除");
            return false;
        } else {
            //判断是否是首尾节点
            if (index == 0) {
                head = head.next;
                size--;
                //序号重置
                flushNumber(-1);
            } else if (index == size - 1) {
                tail = tail.prev;
                size--;
                //依然从0开始，无需重置序号
            } else {
                //中间位置删除
                Node beforeNode = findNodeByIndex(index - 1);
                Node afterNode = findNodeByIndex(index + 1);
                Node currentNode = findNodeByIndex(index);
                //当前位置节点赋值为null，等待gc自动回收
                currentNode = null;
                //前后结点重新连接
                beforeNode.next = afterNode;
                afterNode.prev = beforeNode;
                //重新设置后一个结点后面的索引号
                Node startNode=afterNode;
                int startIndex=startNode.number;
                while(startIndex<=size-1){
                    int newIndex=startNode.number-1;
                    startNode.number=newIndex;
                    startNode=startNode.next;
                    startIndex++;
                }
                size--;
            }
            return true;
        }
    }

    //修改一个节点内容
    public boolean modify(int index, Object obj) {
        if (index < 0 || index > size - 1) {
            System.out.println("索引越界，无效索引");
            return false;
        } else {
            Node currentNode = findNodeByIndex(index);
            currentNode.data = obj;
            System.out.println("修改成功");
            return true;
        }
    }

    //遍历节点
    public void toDoubleLinkArray() {
        if (size > 0) {
            if (size == 1) {
                System.out.println("[" + "(" + head.data + ":" + head.number + ")" + "]");
                return;
            }
            //依然从头部开始遍历
            Node currentNode = head;
            int count = size;//需要遍历的次数
            while (count > 0) {
                if (currentNode.equals(head)) {
                    System.out.print("[" + "(" + currentNode.data + ":" + currentNode.number + ")");
                } else if (currentNode.next == null) {
                    System.out.print("--->" + "(" + currentNode.data + ":" + currentNode.number + ")" + "]");
                } else {
                    System.out.print("--->" + "(" + currentNode.data + ":" + currentNode.number + ")");
                }
                //每输出一个往后移动一个节点
                currentNode = currentNode.next;
                count--;
            }
            //换行
            System.out.println();
        } else {
            System.out.println("[]");
        }
    }

    //更新所有节点顺序编号，往前或者后移动一位
    public void flushNumber(int number) {
        if (size > 1) {
            int count = size;
            Node currentNode = head;
            while (count > 0) {
                if (number != 1&&number != -1) {
                    System.out.println("移动数字非法");
                    return;
                } else {
                    if (number == 1) {
                        int newNumber = currentNode.number + 1;
                        currentNode.number = newNumber;
                    } else if(number==-1){
                        int newNumber = currentNode.number - 1;
                        currentNode.number = newNumber;
                    }
                    currentNode = currentNode.next;
                    count--;
                }
            }
            System.out.println("链表序号刷新完成");
        } else {
            System.out.println("链表为空，或者无需刷新节点编号");
        }
    }

}

测试代码

package DataCompose;

public class TestDoubleLinkTest {

    public static void main(String[] args) {
        //测试双向链表
        DoubleLinkTest Link=new DoubleLinkTest();
        //添加
        System.out.println("----------开始增加操作----------");
        Link.addHead("Messi");
        Link.toDoubleLinkArray();

        Link.addHead("clyang");
        Link.toDoubleLinkArray();

        Link.addHead("Ronald");
        Link.toDoubleLinkArray();

        Link.addTail("KaKa");
        Link.toDoubleLinkArray();

        System.out.println("----------开始修改操作----------");
        //修改位置1的元素
        Link.modify(1,"Kane");
        Link.toDoubleLinkArray();

        System.out.println("----------开始随机插入操作----------");
        //随机插入一个结点
        Link.add("random");
        Link.toDoubleLinkArray();

        //再次随机插入一个结点
        Link.add("Jodan");
        Link.toDoubleLinkArray();

        System.out.println("----------开始查找操作----------");
        //查找位置为2的节点
        Link.findNodeByIndex(2);

        System.out.println("----------开始删除操作----------");
        //删除节点2的位置
        Link.deleteNodeByIndex(2);
        Link.toDoubleLinkArray();
    }

}

控制台输出情况，可以正常的实现增删改查循环遍历的功能，并且插入删除后依然可以保证节点的顺序。

红黑树

树型数据结构

树形结构名词介绍，比较形象，类似于现实中的树，只是计算机中的树其根部在上面，叶子在下面。

结点：树中的一个元素

结点的度：结点拥有的子树的个数，二叉树的话，度不能大于2

高度：叶子节点的高度为1，逐渐往上越来越高，根节点高度是最高的

叶子：高度为0的结点，也是终端结点

层：以根开始是第一层，往下面开始逐一增加

父结点：若一个结点包含若干个子结点，则这个结点就是子结点的父结点

子结点：子结点就是父节点的下一个节点

结点的层次：以根节点开始，根节点为第一层，根的子结点为第二层，逐一类推

兄弟结点：拥有共同父结点的结点称为兄弟结点

平衡因子：该结点左子树的高度-该结点右子树的高度，即平衡因子

二叉树(binary tree)

是每个结点不超过2个子结点的有序树(tree)，每个结点上最多只能有两个子结点，顶上的结点叫做根结点，两边的分支分别叫做左子树和右子树。

平衡树

也是基于二叉树，平衡因子的绝对值不能超过1，即左右子树高度差不能达到2。当往父结点上添加一个子结点后破坏了平衡条件，就会进行平衡旋转，有LL、LR、RR和RL四种类型的平衡旋转，为了想看动画演示旋转，可以登录后面参考的网址（https://www.cs.usfca.edu/~galles/visualization/AVLtree.html）即可。

（1）LL型平衡旋转

如果往如图所示的结点6下面再添加一个子结点4，可以分析一下各个结点的平衡因子，叶子结点4的平衡因此为0，父结点6的平衡因子为1，根结点8的平衡因子为2，破坏了二叉树的平衡条件，因此需要右旋，即6上升到根结点，8移动到根结点的右边，作为子结点。

 旋转后

（2）LR型平衡旋转

同样在结点6的下面增加一个子结点7，添加后在6子结点的右边，其平衡依然被破坏，因此也需要旋转，首先7结点的位置会移动到6的位置，6的位置移动到7的左子结点，这个过程为左旋，变成6-7-8的LL型，然后再右旋转，将7上升到根节点，8变成根结点的右结点。

旋转后

（3）RR型平衡旋转

在父节点10的下面添加一个子结点12，也破坏了平衡性，因此需要左旋，即10上升到根结点的位置，8变成根节点的左子结点。

左旋转 

（4）RL型平衡旋转

在父节点10下面添加子结点9，发现比10小因此为左子结点，与上面情况类似，添加子结点后依然破坏了平衡性，因此需要旋转，首先需要右旋转将9上升到父节点10的位置，将10变成9的右子结点，即变成10-9-8的RR型，这样还需要进行一次左旋转，将9上升到根结点的位置，原根结点8变成9的左子结点。

旋转后

旋转实战演练，先在左子树添加元素，先调整成LL型，然后右旋

往下面平衡树下添加子结点4，可以分析一下，4比20小，往左边子树走，然后比5小，依然往左边子树走，最后到了字结点2，发现比2大因此挂在了2的右子结点，这样显然是破坏了二叉树的平衡的。因此随后需要对2-4-5三个结点进行LR平衡型旋转，首先2左旋，将4移动到2结点的位置，2变成4结点的左子结点，这样就变成了2-4-5的LL型，然后右旋，将4上升到父结点5的位置，而5变成4的右子结点。

添加4后先左旋后右旋

如果继续在上面二叉树的基础上在添加字结点1，显然会破坏平衡，因此4需要上升为根节点，将20进行右旋，20右旋会跟4的右结点5发生碰撞，这种情况就将5挂到20的左边，达到平衡。

右旋转

如果要在如图所示的树上增加结点6，需要先左旋变成LL型，将7移动到父节点5的位置，5移动到7的左节点，这个时候5和6会发生碰撞，将6挂到5结点的右边，变成LL型，然后将7上升到根结点，然后进行右旋，将20和30都挂到7的右边。

先左旋后右旋

如果在如图所示的树上添加8，依然先需要进行左旋变成LL型，将7上升到父结点5的位置，5和2变成7的左子树，8变成7的的右结点，然后进行右旋，将7上升到根结点的位置，这样20和8都为7的右结点会发生碰撞，将8挂到20的下面。

先左旋后右旋

旋转实战演练，在右子树添加元素，先调整成RR型，然后左旋

如果在二叉树中添加结点60，破坏了二叉树的平衡，由于右子树已经是RR型，因此需要左旋就行，30左旋变成50的子结点，50上升到原先30的位置。

左旋

继续在上面的二叉树上添加结点70，发现右边也已经是RR型，无需调整，只要将50上升到根结点，将20结点进行左旋即可，左旋后20和30会发生碰撞，由于30比20大因此及会挂在20的右边。

已经是RR型，直接左旋

如果不在50结点上添加子结点，在25结点上添加一个右子节点，会稍微复杂一点，首先需要将右子树变成RR型，需要先右旋一次，将25上升到30父节点的位置，30变成25的右边子结点，这样30和28会发生碰撞，由于28比30小因此变成其左子结点，这样右边变成RR型，然后将20根结点进行一次左旋，就达到平衡。

先右旋变成RR型，然后左旋

如果不在50结点上添加子结点，在25结点上添加一个左子节点，依然需要先将右子树进行右旋，这样25上升到30的位置，25父节点下面左子结点为23，右子树为30和50，这样变成RR型，然后将20左旋，这样20和23会发生碰撞，由于23比20大因此会挂到20的右边，达到平衡。

先右旋变成RR型，然后左旋

不平衡树

基于二叉树，左子树和右子树数量不相等，在极端情况下可能导致查询变成类似查询链表的情况。

排序树/查找树

排序树是基于二叉树，左子树数值小，右子树数值大，查找数字会很快。

红黑树

红黑树（Red Black Tree）是一种自平衡二叉查找树，在1972年由Rudolf Bayer发明，称为平衡二叉B树，后面被修改为红黑树，红黑树是一种特殊的二叉查找树，其每个节点不是红就是黑。其查找叶子节点的最大次数和最小次数不能超过2倍，跟平衡二叉树不太一样的是，它不需要满足平衡因子绝对值<=1。
红黑树还有以下约束：
1 节点可以是红色或者黑色的
2 根节点是黑色的
3 叶子节点(NIL节点，空节点)是黑色的
4 每个红色节点的子节点都是黑色，即每个叶子到根的路径上不会存在两个连续的红色节点
5 任何节点，到其下面每一个叶子节点的路径上，黑色节点数是相同的

黑红树的主要用途就是使用在HashMap，TreeMap中。

红黑树左旋右旋

红黑树的左旋和右旋，可以参考上面平衡二叉树的左旋和右旋规律，基本一样。

红黑树的插入操作

红黑树如果做插入结点操作，会改变原始红黑树的结构，一般插入的是红色结点，并且有相应的恢复策略，参考了哔哩哔哩视频（https://www.bilibili.com/video/av53772633/?p=3&t=275），大致上可以按照以下的规则来，但是红黑树还有自己的约束，因此个人感觉可以将下面的规则做为参考，但是不一定实际中完全适用，如约束中的第5条，就会导致下面部分规则不完全适用。

（1）插入的是根结点

原始树是空树，因此根节点为红色，违反上面约束条件第二条

策略：将结点涂成黑色

（2）插入结点父结点是黑色

策略：红黑树没有破坏，不需要修复

（3）插入结点后，当前结点的父结点是红色，并且叔叔结点也是红色。

策略：当前结点'4'的父结点'5'和叔叔结点'8'全部变成黑色，祖父结点'7'变成红色。

变化后

（4）当前结点的父结点是红色，叔叔结点是黑色，并且当前结点是父结点的右结点。

策略：当前结点'7'的父结点'2'为支点左旋，当前结点'7'上移动。如果当前结点是父结点的左结点，后面再补充。如图'2'和'5'的结点左旋会发生碰撞，由于'5'比'2'大因此将'5'结点对应的子树挂在结点'2'的右子树。

左旋

（5）当前结点的父结点是红色，叔叔结点是黑色，当前结点是父结点的左结点

策略：当前结点'2'的父结点'7'变成黑色，祖父结点'11'变成红色，以祖父结点'11'为支点进行右旋。右旋时'11'和'8'会发生碰撞，由于'8'比'11'小因此'8'结点对应子树挂在'11'结点的左边作为左子树。

变色以及右旋

红黑树添加结点实战演练 

如图在红黑树的结点上添加20，刚开始作为50的左子结点，这样不符合红黑树的规则，并且这样的情况满足上面说的情况5，因此50结点会变成黑色，根结点右旋。根据动画可以看出来，先完成右旋，再完成变色。

旋转变色

继续添加结点200，首先会作为100的右结点添加，这种符合上面说的情况3，因此父结点和叔叔结点都变成黑色，祖父结点50变成红色，然后根节点不能为红色，因此继续变色，最后根节点变成黑色。需要注意的是红色节点的子结点必须为黑色节点，但是没有规定黑色节点的子结点必须为红色，说明黑色节点下面子结点什么颜色都可以。

变色继续变色

继续添加结点300，首先会作为子结点添加到200的右子结点，这种符合上面说的情况5，因此首先以插入结点的祖父结点100为支点发生左旋，然后变色，父结点200变成黑色，原祖父结点变成红色。

左旋变色

继续添加结点150，首先会作为子结点添加到100的右子结点，这种符合上面的情况3，因此父结点和叔叔结点变成黑色，祖父结点200变成红色，变完色后发现符合黑红树规则，无需再旋转或变色。

变色

继续添加元素160，会先作为右结点挂在150下面，然后这种情况符合上面第五种，因此先按照祖父结点100为支点左旋，然后父结点变成黑色，原祖父结点变成红色，完后发现符合黑红树规则，无需再选择或变色。

左旋变色

添加320到子结点，会首先挂在350下面，然后这种符合第四种情况，父结点是红色，叔叔结点（null）为黑色，由于当前结点在父结点的左边，因此先以父结点350为支点右旋，右旋后变成上面的第五种情况，因此先以祖父结点300左旋，然后父结点320变色为黑色，原祖父结点300变色为红色。

右旋左旋变色

最后添加180到结点中，这个添加会将上面说的第三四五种情况都包含，首先添加到160的右子结点，这种符合第三种情况，因此父结点和叔叔结点都变色为黑色，祖父结点150变成红色。

变色右旋

变成红色后，这种为第四种情况，即150结点的父结点是红色，叔叔结点是黑色，因此本例中需要右旋，由于右旋后200和160会碰撞，因此160结点的子树将作为200结点的左子树。

左旋

然后变成了第五种情况，只是在右边，因此需要以200结点的祖父结点50为支点左旋，由于左旋后，50和100会发生碰撞，因此100将挂在50结点的右边。并且父结点150变成黑色，祖父结点50会变成红色。

变色

关于红黑树的删除结点后面再添加，后续完善。

总结

以上是对数据结构基础的复习和理解，包括栈、队列、数组、链表和红黑树，还有很多理解不到位的地方，后续工作和学习中再补充添加，感谢引用的各位博文博主。

 

参考博文：

 （1）《Java核心技术卷》第8版

（2）https://www.cnblogs.com/ysocean/p/7911910.html 栈

（3）https://www.cnblogs.com/youngchaolin/p/10463887.html 二进制

（4）https://segmentfault.com/a/1190000016524796 队列

（5）https://www.cnblogs.com/ysocean/p/7894448.html 数组

（6）https://www.cnblogs.com/ysocean/p/7928988.html 链表

（7）https://www.cnblogs.com/shamo89/p/6774080.html 队列

（8）https://www.cnblogs.com/ChenD/p/7814906.html 双向链表

（9）https://segmentfault.com/a/1190000014037447?utm_source=tag-newest  红黑树

（10）https://www.cs.usfca.edu/~galles/visualization/AVLtree.html 生成平衡二叉树动画

（11）https://www.cs.usfca.edu/~galles/visualization/RedBlack.html 生成红黑树动画

（12）https://www.cnblogs.com/lezhifang/p/6632355.html 平衡二叉树旋转