数据结构与算法

一、数据结构

1.1、数据结构基本属性

程序 = 数据结构 + 算法

• 数据元素是数据的基本单元，数据元素也称结点
• 逻辑结构：数据元素之间的逻辑关系
• 数据存储结构：数据元素与存储之间的关系
• 集合
• 数据元素都属于同一个集合，且数据元素之间没有任何关系
• 线性结构
  • 线性结构是一种前后关联的结构体，数据元素之间存在着一对一的关系
• 树形结构
  • 一个结点下面可以连接多个子节点，也称孩子结点，数据元素之间存在着一对多的关系
• 图形结构
  • 图形结构也称网状结构，多个结点之间相互连接，数据元素之间存在着多对多阿关系

1.2、数据结构存储结构

• 数据逻辑结构和存储结构的关系：
  • 存储结构是逻辑关系的映像和元素的映像，是数据结构的实现
  • 逻辑结构是数据结构的抽象表达方式
• 存储结构的分类
  • 顺序结构
    • 作用于内存相对位置表示数据元素的逻辑结构
    • 一般便于查询和随机访问数据元素
    • 不利于数据的修改、删除、插入和移动
  • 链式结构
    • 作用于存储地址的指针表示数据元素的逻辑关系
    • 一般便于数据的修改、删除、插入和移动
    • 不能对元素进行随机访问和查询
  • 索引结构
    • 在原有的存储结构上加索引表，索引表由关键字和存储地址组成
    • 提高随机访问及查询效率
  • 散列结构
    • 提高构造函数来确定数据存储地址或查询地址
    • 提高随机访问及查询效率

1.3、算法简介

• 算法的特征
  • 确定性，计算或预测的数据指令一定是确切的，不会产生异议性
  • 可行性，算法可以实现逻辑或问题的真实处理
  • 有穷性，必须要在有限的时间和空间完成并输出结果
  • 输入/输出，可以有零个或多个输入/输出
• 算法的目的
  • 正确性，能够正确执行预先设定好的功能达到预期要求
  • 可读性，便于理解、修改、拓展
  • 健壮性，执行过程中不会因自身或外界元素而打断执行或出现意外错误
  • 高效性，算法一定要高效才符合程序设计的初心
  • 低存储量，算法体量不宜臃肿，不能再执行后增加存储

二、探究复杂度

2.1、斐波那契数列

• 斐波那契数列简单理解，第三项 = 前一项 + 前二项

• 实现方法

  • 方法一

    //方法一实现斐波那契数
    public static int fib(int n){
      //要考虑n=0、n=1的情况
      if(n<=1){
          return n;
      }
      //第三项=前一项+前二项
      return fib(n-1)+fib(n-2);
    }
    /*
    *复杂度=n^2
    */
    @Test
    public void fibTest(){
      System.out.println("n=3:"+fib(3));
      System.out.println("n=20:"+fib(20));
      System.out.println("n=40:"+fib(40));
    }

    
    

  • 方法二

    //方法二实现斐波那契数
    public static int fib2(int n){
      //要考虑n=0、n=1的情况
      if(n<=1){
          return n;
      }
      int fisrt = 0;
      int second = 1;
      //
      for (int i = 0; i < n-1 ; i++) {
          int sum = fisrt + second;
          //每次执行的结果都是第二次执行的首项
          fisrt =second;
          //每次执行的第二项都是第一次执行的结果
          second = sum;
      }
      return second;
    }
    /*
    * 时间复杂度=n
    */
      @Test
    public void fib2Test(){
      System.out.println("n=30:"+fib2(30));
      System.out.println("n=60:"+fib2(60));
      System.out.println("n=90:"+fib2(90));
    }

    
    

  • 时间计算 ```java //时间计算类 public class TimeTool { private static final SimpleDateFormat fmt = new SimpleDateFormat(“HH:mm:ss.SSSS”);

    public interface Task{ void execute(); }

    public static void check(String title,Task task){ if(task ==null){

      return;

    } title = (title == null) ? “”:(“【”+title+”】”); System.out.println(title); System.out.println(“开始：” + fmt.format(new Date())); long begin =System.currentTimeMillis(); task.execute(); long end =System.currentTimeMillis(); System.out.println(“结束：” + fmt.format(new Date())); double delta =(end - begin)/1000.0; System.out.println(“耗时：” + delta + “秒”); System.out.println(“————————————“);

    } }

//测试 @Test public void timeTest(){ int n=46; TimeTool.check(“fib”, new TimeTool.Task() { @Override public void execute() { System.out.println(fib(n)); } });

    TimeTool.check("fib2", new TimeTool.Task() {
        @Override
        public void execute() {
            System.out.println(fib2(n));
        }
    });
}

<br />![](https://gitee.com/hg14150/blogiamges/raw/master/img/image-20210609215046296.png#crop=0&crop=0&crop=1&crop=1&id=oAsTQ&originHeight=379&originWidth=724&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 
-  **特征方程解决斐波那契数列**<br />![](https://gitee.com/hg14150/blogiamges/raw/master/img/image-20210610192515990.png#crop=0&crop=0&crop=1&crop=1&id=XkzfJ&originHeight=437&originWidth=1239&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 
<a name="31297a97"></a>
### 2.2、时间复杂度
-  时间复杂度是衡量一个程序性能好坏的重要指标之一，也是衡量一个算法好坏的重要指标之一 
-  时间复杂度的计算 
   - **一个分号执行1次 O(1)**
   - for循环执行次数取决于n值大小 
      - **单层for循环一般为3n次 O(n)**
      - **双重for循环一般为9n^2+6n+1 O(n^2)**
      - **n = m /2的情况 Ologm(n)——>Ologn**
-  **时间复杂度大小对比** 
   -  **O(1) < O(logn) <  O(n) < O(n^2) < O(n^3) < O(2^n) <O(n!) < O(n^n)** ![](https://gitee.com/hg14150/blogiamges/raw/master/img/image-20210609230526918.png#crop=0&crop=0&crop=1&crop=1&id=vsk2v&originHeight=656&originWidth=1099&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 
<a name="f9608952"></a>
### 2.3、空间复杂读
-  算法对内存资源的消耗，一般运行不消耗内存不会增加就算优质算法了 
-  在程序设计中，一个优质的算法 = 时间复杂度 + 空间复杂度 
-  在解决算法调优时，一般选择以空间复杂度换时间复杂度 
<a name="f91df17a"></a>
## 三、线性数据结构
<a name="38fdfce3"></a>
#### 3.1、线性表
<a name="c5bb71ee"></a>
##### 3.1.1、什么是线性表
![](https://gitee.com/hg14150/blogiamges/raw/master/img/image-20210610145733469.png#crop=0&crop=0&crop=1&crop=1&id=dzPBy&originHeight=358&originWidth=1429&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
- 线性表是一种线性结构，它是由零个或多个数据元素构成的**有限序列**。
- 线性表的特征是在一个序列中，除了头尾元素，每个元素都有且**只有一个直接前驱**，**有且只有一个直接后继**，而序列头元素没有直接前驱，序列尾元素没有直接后继。
- 线性表中的元素是相同的抽象数据类型。
<a name="1e604ff8"></a>
##### 3.1.2、线性表的分类
-  常用的数组、链表、栈、队列等都是线性结构的数据结构 
-  **数组中的战斗机** 
   -  **vector和array、数组** 
   -  相同点： 
      - 三者均可以使用下表运算符对元素进行操作，即vector和array都针对下标运算符[]进行了重载
      - 三者在内存的方面都使用连续内存，即在vector和array的底层存储结构均使用数组
      - 都在java.util包下
   -  不同点： 
      - vector属于变长容器，即可以根据数据的插入删除重新构建容器容量（1.5倍或者2倍）；但array和数组属于定长容量
      - vector和array提供了更好的数据访问机制，即可以使用front和back以及at访问方式，使得访问更加安全。
      - vector和array提供了更好的遍历机制，即有正向迭代器和反向迭代器两种
      - array提供了初始化所有成员的方法fill
      - vector提供了可以动态插入和删除元素的机制，而array和数组则无法做到，或者说array和数组需要完成该功能则需要自己实现完成
   -  **vector和arrayList** 
      -  vector是线程同步（Synchronized）的，所以它也是线程安全的 
      -  Arraylist是线程异步（ASynchronized）的，是不安全的 
      -  正因vetor线程同步，所以在执行中多了获取锁资源的过程，效率比arrayList慢 
      -  ArrayList和Vector都采用线性连续存储空间，当存储空间不足的时候，ArrayList默认增加为原来的50%，Vector默认增加为原来的一倍； 
<a name="04dc329f"></a>
#### 3.2、动态数组
<a name="1fe7f3ed"></a>
##### 3.2.1、深入了解数组
![](https://gitee.com/hg14150/blogiamges/raw/master/img/image-20210610145908686.png#crop=0&crop=0&crop=1&crop=1&id=knmyR&originHeight=400&originWidth=562&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
-  `int[] array = new int []{}`，向栈空间申请一段可使用内存放在int类型的array数组里 
-  数组无法动态修改容量，创建时申请多少，使用过程中就是多少 
<a name="2ac6bc8d"></a>
##### 3.2.2、动态数组
-  **接口参数设计** ![](https://gitee.com/hg14150/blogiamges/raw/master/img/image-20210610151650652.png#crop=0&crop=0&crop=1&crop=1&id=Jne9C&originHeight=299&originWidth=557&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 
-  **对象数组** 
   -  数组元素可以是任何类型（只要所有元素具有相同的类型） 
   -  数组元素可以是基本数据类型 
   -  数组元素也可以是类对象，称这样的数组为对象数组。在这种情况下，数组的每一个元素都是一个对象的引用。 
   -  先申请堆内存，再创建数组对象，可以减少一定程度的内存资源浪费 
```java
//创建数组对象，申请堆内存空间
Object[i] list = new Object[10];
//创建数组对象
object[0] = new Person(1,"java");
object[1] = new Person(2,"python");
object[2] = new Person(3,"C++");

• 数组扩容
  • 按倍数增加，但存在线程风险且效率不高

    //数组扩容处理
    private void ensureCapacity(int capcity){
      //定义为扩容前的数组长度
      int oldCapacity =elements.length;
      //判断容量大小
      if(oldCapacity >= capcity){
          return;
      }
      //定义数组扩容的大小,1+0.5
      int newCapacity = oldCapacity + (oldCapacity >> 1);
      E[] newElements = (E[]) new Object[newCapacity];
      for (int i = 0; i < size; i++) {
          newElements[i] = elements[i];
      }
      elements = newElements;
      System.out.println(oldCapacity+"扩容："+newCapacity);
    }

• 系统内置函数，成倍增加

  public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);
  //src 原始数组
  //srcPos 原始数组中的起始位置
  //dest 目标数组
  //destPos 目标数据中的起始位置
  //length 要复制的数组元素的数量

3.2.3、动态数组的实现

/**
 * @author hguo
 * @date2021/6/10 15:14
 * @title 动态数组接口设计
 */
public class ArrayList<E>{
    private int size;
    private E[] elements;
    /**
     * 数组的默认容量
     */
    private static final int DEFAULT_CAPACITY = 5;
    /**
     * 找不到元素返回-1
     */
    private static final int ELEMENT_NOT_FOUND = -1;
    public ArrayList(int capacity) {
        // 设置默认容量为 10
        capacity = Math.max(capacity, DEFAULT_CAPACITY);
        // 因为泛型(所以传一个Object数组,然后通过强转)
        elements = (E[]) new Object[capacity];
    }
    public ArrayList() {
        // 默认容量
        this(DEFAULT_CAPACITY); // 调用下面的构造器
    }
    //数组越界，异常处理
    private void OutOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size+":数组越界，请正确输入！");
    }
    //限定CRUD操作范围
    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            OutOfBounds(index);
        }
    }
    //插入操作的范围限定
    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            OutOfBounds(index);
        }
    }
    //数组扩容处理
    private void ensureCapacity(int capcity){
        //定义为扩容前的数组长度
        int oldCapacity =elements.length;
        //判断容量大小
        if(oldCapacity >= capcity){
            return;
        }
        //定义数组扩容的大小,1+0.5
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        elements = newElements;
        System.out.println(oldCapacity+"扩容："+newCapacity);
    }
      /**
     * 数组缩容
     */
    public void trim() {
        // 获取当前数组的容量
        int oldcapacity = elements.length;
        // 计算新的容量 = 原有容量的一半
        int newCapacity = oldcapacity >> 1;
        // 当size大于等于容量的一半, 或则容量已经小于默认容量(10)时, 直接返回
        if (size >= newCapacity >> 1 || oldcapacity < DEFAULT_CAPACITY) return;
        // 创建新数组
        E[] newElements = (E[]) new Object[newCapacity];
        // 将原数组元素存入新数组
        for (int i = 0; i < size; i++) {
            newElements[i] = elements[i];
        }
        // 引用新数组
        elements = newElements;
        System.out.println(oldcapacity+"缩容："+newCapacity);
    }
    // 元素的数量
    public int size() {
        return size;
    }
    // 是否为空
    public boolean isEmpty() {
        return size == 0;
    }
    // 是否包含某个元素
    public boolean contains(E element) {
        return indexOf(element)!= ELEMENT_NOT_FOUND;
    }
    // 添加元素到最后面
    public void add(E element) {
        add(size,element);
    }
    // 返回index位置对应的元素
    public E get(int index) {
        rangeCheck(index);
        return elements[index];
    }
    // 设置index位置的元素
    public E  set(int index, E element) {
        rangeCheck(index);
        E old =  elements[index];
        elements[index] = element;
        return old;
    }
    // 往index位置添加元素
    public void add(int index, E element) {
        //插入值为空时
        if(element == null){
            return;
        }
        //处理数组越界
        rangeCheckForAdd(index);
        //数组扩容
        ensureCapacity(size+1);
        //从后往前开始操作
        for (int i = size - 1; i >=index ; i--) {
            elements[i + 1] =elements[i];
        }
        elements[index]  = element;
        size++;
    }
    // 删除index位置对应的元素
    public E remove(int index) {
        rangeCheck(index);
        E old =  elements[index];
        // 当删除一个元素时,需要挪动后面元素的范围
        for (int i = index + 1; i <= size - 1; i++) {
            elements[i - 1] = elements[i];
        }
        // 同clear的细节,当从后往前以后时,最后一个的地址需要释放
        //清空最后一个元素，先把位置减一再清空
        elements[--size] = null;
        //缩容操作
          trim();
        return old;
    }
    // 查看元素的位置
    public int indexOf(E element) {
        for (int i = 0; i < size; i++) {
            // 因为element肯定不为null了,所以放在前面;避免空指针异常
            if (elements[i].equals(element)) //比较数组即可，不用比较内存地址
            {
                return i;
            }
        }
        return ELEMENT_NOT_FOUND;
    }
    // 清除所有元素
    public void clear() {
        for (int i = 0; i <size; i++) {
            //清空数组
            elements[i] = null;
        }
        size = 0;
    }
    @Override
    public String toString() {
        //使用StringBuilder进行字符串拼接
        StringBuilder string = new StringBuilder();
        //定义拼接格式
        string.append("size=").append(size).append(",[");
        //循环遍历数组内容
        for (int i = 0; i < size; i++) {
            if(i != 0 ){
                string.append(",");
            }
            string.append(elements[i]);
            //元素用,隔开，但要判断元素是否为最后一个，最后一个不破解分隔符
        }
        string.append("]");
        //打印数组内容
        return string.toString();
    }
}

• 扩容操作 ```java

  //数组扩容处理 private void ensureCapacity(int capcity){

   //定义为扩容前的数组长度
   int oldCapacity =elements.length;
   //判断容量大小
   if(oldCapacity >= capcity){
       return;
   }
   //定义数组扩容的大小,1+0.5
   int newCapacity = oldCapacity + (oldCapacity >> 1);
   E[] newElements = (E[]) new Object[newCapacity];
   for (int i = 0; i < size; i++) {
       newElements[i] = elements[i];
   }
   elements = newElements;
   System.out.println(oldCapacity+"扩容："+newCapacity);

  }

// 往index位置添加元素 public void add(int index, E element) { //插入值为空时 if(element == null){ return; } //处理数组越界 rangeCheckForAdd(index); //数组扩容 ensureCapacity(size+1); //从后往前开始操作 for (int i = size - 1; i >=index ; i—) { elements[i + 1] =elements[i]; } elements[index] = element; size++; }

-  **测试** 
```java
 @Test
   public void arrayList2() {
        ArrayList<Integer> list = new ArrayList<>();
        list.add(12);
        list.add(13);
        list.add(14);
        list.add(15);
        list.add(16);
        list.add(17);
        list.add(19);
        list.add(20);
        list.add(21);
        list.add(22);
        list.add(5,18);
        System.out.println(list);
    }

• 缩容操作 ```java

   /**

  • 数组缩容 */ public void trim() { // 获取当前数组的容量 int oldcapacity = elements.length; // 计算新的容量 = 原有容量的一半 int newCapacity = oldcapacity >> 1; // 当size大于等于容量的一半, 或则容量已经小于默认容量(10)时, 直接返回 if (size >= newCapacity >> 1 || oldcapacity < DEFAULT_CAPACITY) return; // 创建新数组 E[] newElements = (E[]) new Object[newCapacity]; // 将原数组元素存入新数组 for (int i = 0; i < size; i++) {

     newElements[i] = elements[i];

    } // 引用新数组 elements = newElements; System.out.println(oldcapacity+”缩容：”+newCapacity); }

/**
 * 删除index位置的元素
 * @param index
 * @return 被删除的元素
 */
public E remove(int index) {
    rangeCheck(index);
    E delEle = elements[index];
    // 当删除一个元素时,需要挪动后面元素的范围
    for (int i = index + 1; i <= size - 1; i++) {
        elements[i - 1] = elements[i];
    }
    size--;
    // 同clear的细节,当从后往前以后时,最后一个的地址需要释放
    elements[size] = null;
    // 判断数组是否需要缩容
    trim();
    return delEle;
}

-  **测试** 
```java
  @Test
    public void arrayList3(){
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < 50; i++) {
            list.add(i);
        }
        for (int i = 0; i < 50; i++) {
            list.remove(0);
        }
        System.out.println(list);
    }

3.3、链表

3.3.1、什么链表

• 链表和数组是同一级别的数据结构，链表在进行循环遍历时效率不高，但是插入和删除时优势明显。
• 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的
• 链表由一个个子节点构成，每个节点有两个部分：数据域和指针域
  • 数据域就是实际存储数据的，指针域可以有一个和两个，单链表就是单个指针域指向后一个节点，双链表就是节点有两个指针域，分别指向前一个和后一个节点。

3.3.2、链表的实现原理

• 创建一个节点类，其中节点类包含两个部分，第一个是数据域（你到时候要往节点里面储存的信息），第二个是引用域（相当于指针，单向链表有一个指针，指向下一个节点；双向链表有两个指针，分别指向下一个和上一个节点）
• 创建一个链表类，其中链表类包含三个属性：头结点、尾节点和大小，方法包含添加、删除、插入等等方法

3.3.3、链表的分类

• 单向链表：链表中的元素的指向只能指向链表中的下一个元素或者为空，元素之间不能相互指向，也就是一种线性链表
• 双向链表：个有序的结点序列，每个链表元素既有指向下一个元素的指针，又有指向前一个元素的指针，其中每个结点都有两种指针，即front和tail，front指针指向左边结点，tail指针指向右边结点

3.3.4、链表接口设计

• 定义公共接口

  /**
  * @author hguo
  * @date2021/6/11 11:14
  * @title List公共接口的设计
  */
  public interface List<E> {
   public static final int ELEMENT_NOT_FOUND = -1;
   /**
    * 清除所有元素
    */
   public void clear();
   /**
    * 元素的数量
    * @return
    */
   public int size();
   /**
    * 是否为空
    * @return
    */
   boolean isEmpty();
   /**
    * 是否包含某个元素
    * @param element
    * @return
    */
   boolean contains(E element);
   /**
    * 添加元素到尾部
    * @param element
    */
   void add(E element);
   /**
    * 获取index位置的元素
    * @param index
    * @return
    */
   E get(int index);
   /**
    * 设置index位置的元素
    * @param index
    * @param element
    * @return 原来的元素ֵ
    */
   E set(int index, E element);
   /**
    * 在index位置插入一个元素
    * @param index
    * @param element
    */
   void add(int index, E element);
   /**
    * 删除index位置的元素
    * @param index
    * @return
    */
   E remove(int index);
   /**
    * 查看元素的索引
    * @param element
    * @return
    */
   int indexOf(E element);
  }

• 定义公共抽象类，使用时，不论是数组还是链表只需要基础该抽象类即可实现定义的功能

  /**
  * @author hguo
  * @date2021/6/11 11:22
  * @title 定义公共抽象类
  */
  public abstract class AbstractList<E> implements List<E>{
   protected int size;
   // 下标越界抛出的异常
   protected void outOfBounds(int index) {
       throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size+":数组越界，请正确输入！");
   }
   // 检查下标越界(不可访问或删除size位置)
   protected void rangeCheck(int index){
       if(index < 0 || index >= size){
           outOfBounds(index);
       }
   }
   // 检查add()的下标越界(可以在size位置添加元素)
   protected void rangeCheckForAdd(int index) {
       if (index < 0 || index > size) {
           outOfBounds(index);
       }
   }
   @Override
   public boolean contains(E element) {
       return indexOf(element)!=ELEMENT_NOT_FOUND;
   }
   @Override
   public int size() {
       return size;
   }
   @Override
   public boolean isEmpty() {
       return size == 0;
   }
   @Override
   public void add(E element) {
       add(size, element);
   }
  }

3.3.5、单向链表的实现

1、单向链表的操作

2、接口设计分析

• 链表和数组接口大致相同，数组为ArrayList，链表为LinkList，因此在设计共用接口时，可以定义一个公共父类接口让数组和链表调用

• 单向链表一 ```java /**

  • @author hguo
  • @date2021/6/11 11:26

  • @title 单链表操作 */ public class SingleLinkedList extends AbstractList{

    //定义初始结点 private Node first;

    // 链表中的节点 private static class Node { E element; // 节点元素 Node next; // 节点指向下一个节点

    public Node(E element, Node next) {

       this.element = element;
       this.next = next;

    } }

    /**

    • 根据索引找到节点对象
    • @param index
    • @return */ private Node node(int index) { rangeCheck(index); Node node = first; for (int i = 0; i < index; i++) {

       node = node.next;

      } return node; }

    @Override public void clear() { // size = 0; first = null; }

    @Override public E get(int index) { /*

    * 最好:O(1)
    * 最坏:O(n)
    * 平均:O(n)
    */

    return node(index).element; }

@Override
public E set(int index, E element) {
    /*
     * 最好:O(1)
     * 最坏:O(n)
     * 平均:O(n)
     */
    E old = node(index).element;
    node(index).element = element;
    return old;
}
@Override
public void add(int index, E element) {
    /*
     * 最好：O(1)
     * 最坏：O(n)
     * 平均：O(n)
     */
    rangeCheckForAdd(index);
    if(index == 0){ // 给空链表添加第一个元素的情况
        first = new Node<>(element, first);
    }else{
        Node<E> prev = node(index - 1);
        prev.next = new Node<>(element, prev.next);
    }
    size++;
}
@Override
public E remove(int index) {
    /*
     * 最好：O(1)
     * 最坏：O(n)
     * 平均：O(n)
     */
    rangeCheck(index);
    Node<E> node = first;
    if (index == 0) { // 删除第一个元素是特殊情况
        first = first.next;
    } else {
        Node<E> prev = node(index - 1); // 找到前一个元素
        node = prev.next; // 要删除的元素
        prev.next = node.next; // 删除元素
    }
    size--;
    return node.element;
}
/**
 * 查看元素的位置
 * @param element
 * @return
 */
public int indexOf(E element) {
    if(element == null){
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (node.element == null){
                return i;
            }
            node = node.next;
        }
    }else {
        for (int i = 0; i < size; i++) {
            Node<E> node = first;
            // 因为element肯定不为null了,所以放在前面;避免空指针异常
            if (node.element.equals(element)) //比较数组即可，不用比较内存地址
            {
                return i;
            }
            node = node.next;
        }
    }
    return ELEMENT_NOT_FOUND;
}
//拼接字符串并打印
@Override
public String toString() {
    StringBuilder string = new StringBuilder();
    string.append("size=").append(size).append(": [");
    Node<E> node = first;
    for (int i = 0; i < size; i++) {
        if (i != 0) {
            string.append(", ");
        }
        string.append(node.element);
        node = node.next;
    }
    string.append("]");
    return string.toString();
}

}

   -  **清空元素**：`next` 不需要设置为 `null`，因为 `first` 指向了 `null`，后面的 `Node` 没有被指向，在 Java 中会自动被垃圾回收 ![](https://gitee.com/hg14150/blogiamges/raw/master/img/image-20210611135921074.png#crop=0&crop=0&crop=1&crop=1&id=s2oql&originHeight=361&originWidth=991&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 
   -  **添加元素**：需要考虑链表首位位置的元素，size=0/size=next ![](https://gitee.com/hg14150/blogiamges/raw/master/img/image-20210611140121430.png#crop=0&crop=0&crop=1&crop=1&id=SNHgt&originHeight=492&originWidth=987&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 
   -  **删除元素：**需要考虑链表首位位置的元素，size=0/size=next ![](https://gitee.com/hg14150/blogiamges/raw/master/img/image-20210611140212999.png#crop=0&crop=0&crop=1&crop=1&id=fK72f&originHeight=489&originWidth=991&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 
-  **单向链表二（虚拟头结点）** 
   -  **虚拟的头结点（不存储数据）**，减少代码冗余，增加业务处理逻辑 ![](https://gitee.com/hg14150/blogiamges/raw/master/img/image-20210611140444599.png#crop=0&crop=0&crop=1&crop=1&id=sXEvP&originHeight=302&originWidth=983&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 
   -  整体与单项链表无异，但因为多了虚拟头结点，增加/删除元素的方法有变化（add/remove） 
   -  **创建虚拟头结点** 
```java
    public SingleLinkedList() { 
    // 初始化一个虚拟头结点
        first = new Node<>(null, null);
    };

• 增加方法

  @Override
  public void add(int index, E element) {
    rangeCheckForAdd(index);
    Node<E> prev = (index == 0) ? first : node(index - 1);
    prev.next = new Node<>(element, prev.next);
    size++;
  }

• 删除方法

  @Override
  public E remove(int index) {
    rangeCheck(index);
    Node<E> prev = (index == 0) ? first : node(index - 1);
    Node<E> node = prev.next;
    prev.next = node.next;
    size--;
    return prev.element;
  }

• 虚拟头结点单向链表
  • 头结点为空，无指向（NULL）（不建议使用） ```java /**
  • @author hguo
  • @date2021/6/11 14:12
  • @title 虚拟头结点单向链表 */

/**

• 增加一个虚拟头结点

• @param */ public class SingleLinkedList2 extends AbstractList { //定义初始结点 private Node first;

  /**

  • 初始化一个虚拟头结点 */ public SingleLinkedList2() { first = new Node<>(null, null); };

/**
 * 链表中的节点
 * @param <E>
 */
private static class Node<E> {
    // 节点元素
    E element;
    // 节点指向下一个节点
    Node<E> next;
    public Node(E element, Node<E> next) {
        this.element = element;
        this.next = next;
    }
}
/**
 * 清空元素
 */
@Override
public void clear() {
    size = 0;
    first = null;
}
/**
 * 获取元素
 * @param index
 * @return
 */
@Override
public E get(int index) {
    return node(index).element;
}
/**
 * 设置或修改元素
 * @param index
 * @param element
 * @return
 */
@Override
public E set(int index, E element) {
    E old = node(index).element;
    node(index).element = element;
    return old;
}
/**
 * 插入元素
 * @param index
 * @param element
 */
@Override
public void add(int index, E element) {
    rangeCheckForAdd(index);
    Node<E> prev = (index == 0) ? first : node(index - 1);
    prev.next = new Node<>(element, prev.next);
    size++;
}
/**
 * 删除元素
 * @param index
 * @return
 */
@Override
public E remove(int index) {
    rangeCheck(index);
    Node<E> prev = (index == 0) ? first : node(index - 1);
    Node<E> node = prev.next;
    prev.next = node.next;
    size--;
    return prev.element;
}
/**
 * 索引元素
 * @param element
 * @return
 */
@Override
public int indexOf(E element) {
    // 有个注意点, 如果传入元素为null, 则不能调用equals方法, 否则会空指针
    // 因此需要对元素是否为null做分别处理
    if (element == null) {
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (node.element == null) return i;
            node = node.next;
        }
    } else {
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            if (node.element.equals(element)) return i;
            node = node.next;
        }
    }
    return ELEMENT_NOT_FOUND;
}
/**
 * 根据索引找到节点
 * @param index
 * @return
 */
private Node<E> node(int index) {
    rangeCheck(index);
    Node<E> node = first.next;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node;
}
@Override
public String toString() {
    StringBuilder string = new StringBuilder();
    string.append("size=").append(size).append(": [");
    Node<E> node = first.next;
    for (int i = 0; i < size; i++) {
        if (i != 0) {
            string.append(", ");
        }
        string.append(node.element);
        node = node.next;
    }
    string.append("]");
    return string.toString();
}

}

<a name="d6ee3be5"></a>
###### 3、复杂度分析
![](https://gitee.com/hg14150/blogiamges/raw/master/img/image-20210611145222441.png#crop=0&crop=0&crop=1&crop=1&id=zyX5Y&originHeight=315&originWidth=821&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
<a name="cc019d10"></a>
##### 3.3.6、双向链表的实现
<a name="b25bb406"></a>
###### 1、双向链表的操作
![](https://gitee.com/hg14150/blogiamges/raw/master/img/image-20210613144527156.png#crop=0&crop=0&crop=1&crop=1&id=A9xzS&originHeight=592&originWidth=975&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
![](https://gitee.com/hg14150/blogiamges/raw/master/img/image-20210613144636204.png#crop=0&crop=0&crop=1&crop=1&id=Is1Fx&originHeight=509&originWidth=984&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
![](https://gitee.com/hg14150/blogiamges/raw/master/img/image-20210613144527156.png#crop=0&crop=0&crop=1&crop=1&id=jySlN&originHeight=592&originWidth=975&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
![](https://gitee.com/hg14150/blogiamges/raw/master/img/image-20210613144636204.png#crop=0&crop=0&crop=1&crop=1&id=F59J8&originHeight=509&originWidth=984&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=)
<a name="f9d466a6"></a>
###### 2、接口设计分析
-  双向链表的出现只为解决单向链表查询或插入只能单向操作导致效率低的问题 
-  双链表是链表的一种，由节点组成，**每个数据结点中都有两个指针，分别指向直接后继和直接前驱**。 
-  在链表存储多个元素时，对元素的操作可以正向操作，也可以逆向操作，提高了增删改查的结点查询效率 ![](https://gitee.com/hg14150/blogiamges/raw/master/img/image-20210611162507109.png#crop=0&crop=0&crop=1&crop=1&id=p3ESO&originHeight=455&originWidth=929&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 
-  双向链表**只有一个元素**的情况：`first`、`last` 指向同一个节点 ![](https://gitee.com/hg14150/blogiamges/raw/master/img/image-20210611162651385.png#crop=0&crop=0&crop=1&crop=1&id=DPS5D&originHeight=335&originWidth=910&originalType=binary&ratio=1&rotation=0&showTitle=false&status=done&style=none&title=) 
-  **定义结点** 
```java
public class DoubleLinkedList<E> extends AbstractList<E> {
    //定义首结点
    private Node<E> first;
    //定义为结点
    private Node<E> last;
    /**
     * 定义链表中的结点
     * @param <E>
     */
    private static class Node<E> {
        E element;
        Node<E> prev; // 指向前驱节点
        Node<E> next; // 指向后继节点
        public Node(Node<E> prev, E element, Node<E> next) {
            this.prev = prev;
            this.element = element;
            this.next = next;
        }
        @Override
        public String toString(){
            StringBuilder sb = new StringBuilder();
            if(prev != null){
                sb.append(prev.element);
            }else{
                sb.append("null");
            }
            sb.append("_").append(element).append("_");
            if(next != null){
                sb.append(next.element);
            }else{
                sb.append("null");
            }
            return sb.toString();
        }
    }
}

• 插入操作
  • 插入位置小于size的1/2就从fisrt开始插入，大于1/2就从last开始插入

• 

  @Override
  public void add(int index, E element) {
   rangeCheckForAdd(index);
   // size == 0
   // index == 0
   if (index == size) { // 往最后面添加元素
       Node<E> oldLast = last;
       last = new Node<>(oldLast, element, null);
       if (oldLast == null) { // 这是链表添加的第一个元素
           first = last;
       } else {
           oldLast.next = last;
       }
   } else { // 正常添加元素
       Node<E> next = node(index);
       Node<E> prev = next.prev;
       Node<E> node = new Node<>(prev, element, next);
       next.prev = node;
       if (prev == null) { // index == 0
           first = node;
       } else {
           prev.next = node;
       }
   }
   size++;
  }

• 删除操作
  • 插入位置小于size的1/2就从fisrt开始遍历删除，大于1/2就从last开始遍历删除

@Override
public E remove(int index) {
    rangeCheck(index);
    Node<E> node = node(index);
    Node<E> prev = node.prev;
    Node<E> next = node.next;
    if (prev == null) { // index == 0
        first = next;
    } else {
        prev.next = next;
    }
    if (next == null) { // index == size - 1
        last = prev;
    } else {
        next.prev = prev;
    }
    size--;
    return node.element;
}

• 双向链表接口定义

  /**
  * @author hguo
  * @date2021/6/11 16:13
  * @title 双向链表
  */
  public class DoubleLinkedList<E> extends AbstractList<E> {
   //定义首结点
   private Node<E> first;
   //定义为结点
   private Node<E> last;
   /**
    * 定义链表中的结点
    * @param <E>
    */
   private static class Node<E> {
       E element;
       Node<E> prev; // 指向前驱节点
       Node<E> next; // 指向后继节点
       public Node(Node<E> prev, E element, Node<E> next) {
           this.prev = prev;
           this.element = element;
           this.next = next;
       }
       @Override
       public String toString(){
           StringBuilder sb = new StringBuilder();
           if(prev != null){
               sb.append(prev.element);
           }else{
               sb.append("null");
           }
           sb.append("_").append(element).append("_");
           if(next != null){
               sb.append(next.element);
           }else{
               sb.append("null");
           }
           return sb.toString();
       }
   }
   /**
    * 清空元素
    */
   @Override
   public void clear() {
       size = 0;
       first = null;
       last = null;
   }
   /**
    * 获取元素
    * @param index
    * @return
    */
   @Override
   public E get(int index) {
       return node(index).element;
   }
   /**
    * 设置或修改元素
    * @param index
    * @param element
    * @return
    */
   @Override
   public E set(int index, E element) {
       Node<E> node = node(index);
       E old = node.element;
       node.element = element;
       return old;
   }
   /**
    * 插入元素
    * @param index
    * @param element
    */
   @Override
   public void add(int index, E element) {
       rangeCheckForAdd(index);
       if (index == size) { // 往最后面添加元素
           Node<E> oldLast = last;
           last = new Node<>(oldLast, element, null);
           if (oldLast == null) { // 这是链表添加的第一个元素
               first = last;
           } else {
               oldLast.next = last;
           }
       } else { // 正常添加元素
           Node<E> next = node(index);
           Node<E> prev = next.prev;
           Node<E> node = new Node<>(prev, element, next);
           next.prev = node;
           if (prev == null) { // index == 0
               first = node;
           } else {
               prev.next = node;
           }
       }
       size++;
   }
   /**
    * 删除元素
    * @param index
    * @return
    */
   @Override
   public E remove(int index) {
       rangeCheck(index);
       Node<E> node = node(index);
       Node<E> prev = node.prev;
       Node<E> next = node.next;
       if (prev == null) { // index == 0
           first = next;
       } else {
           prev.next = next;
       }
       if (next == null) { // index == size - 1
           last = prev;
       } else {
           next.prev = prev;
       }
       size--;
       return node.element;
   }
   /**
    * 索引元素
    * @param element
    * @return
    */
   @Override
   public int indexOf(E element) {
       if (element == null) {
           Node<E> node = first;
           for (int i = 0; i < size; i++) {
               if (node.element == element) return i;
               node = node.next;
           }
       } else {
           Node<E> node = first;
           for (int i = 0; i < size; i++) {
               if (node.element.equals(element)) return i;
               node = node.next;
           }
       }
       return ELEMENT_NOT_FOUND;
   }
   /**
    * 根据索引找到节点
    *
    * @param index
    * @return
    */
   private Node<E> node(int index) {
       rangeCheck(index);
       if (index < (size >> 1)) { // 索引小于一半从前往后找
           Node<E> node = first;
           for (int i = 0; i < index; i++) {
               node = node.next;
           }
           return node;
       } else { // 索引大于一半从后往前找
           Node<E> node = last;
           for (int i = size - 1; i > index; i--) {
               node = node.prev;
           }
           return node;
       }
   }
   /**
    * 拼接并打印元素
    * @return
    */
   @Override
   public String toString() {
       StringBuilder string = new StringBuilder();
       string.append("size=").append(size).append("：[");
       Node<E> node = first;
       for (int i = 0; i < size; i++) {
           if (i != 0) {
               string.append(", ");
           }
           string.append(node);
           node = node.next;
       }
       string.append("]");
       return string.toString();
   }
  }

3、测试

 @Test
    public void listTest1(){
        ArrayList<Object> list1 = new ArrayList<>();
        list1.add(12);
        list1.add(13);
        list1.add(14);
        list1.add(15);
        list1.add(16);
        System.out.println(list1);
        DoubleLinkedList<Object> list = new DoubleLinkedList<>();
        list.add(12);
        list.add(13);
        list.add(14);
        list.add(15);
        list.add(16);
        System.out.println(list);
    }