开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 线性表与链表的详解 -> 正文阅读

[数据结构与算法]线性表与链表的详解

跟着阿姨走，幸福啥都有——关阿姨笔录

文章目录

零不同算法时间复杂度对比
一线性表(ArrayList)
1.1 线性表的增删改查实现
1.1.1 查找
1.1.2 添加
1.1.3 删除

1.2 综合代码
1.2.1 接口
1.2.2 公共抽象类
1.2.3 实现的代码
1.2.4 测试代码

1.3 练习题

二链表(LinkedList)
2.1 单向链表的实现
2.1.1 查询节点的值
2.1.2 添加节点
2.1.3 删除节点

2.2 综合代码
2.2.3 实现的代码
2.2.4 测试

2.3 双向链表的实现
2.3.1 增加新节点
链表中间位置
链表开始位置
链表末尾位置
空链表的添加

2.3.2 删除节点
链表中间位置
链表头位置【包括只一个节点的情况】

2.4 综合代码
2.4.1 测试
2.5 总结

三双向链表和动态数组的对比

零不同算法时间复杂度对比

分别以递归和循环实现斐波那契函数

package 数据结构.Day01;

import java.util.Scanner;

/**
 * @author 缘友一世
 * @date 2022/8/27-10:04
 */
//递归 斐波那契数列
/*
* 下标 0 1 2 3 4 5 6 7
* 数列 0 1 2 3 5 8 13
* */
public class Recursion {
    public static void main(String[] args) {
        long n=0;
        System.out.print("请输入要求的第几个的数：");
        Scanner scanner=new Scanner(System.in);
        if(scanner.hasNextLong()) {
            n= scanner.nextLong();
        }
        scanner.close();
        System.out.println("循环实现：第"+n+"个斐波那契数为："+fun2(n));
        System.out.println("递归实现：第"+n+"个斐波那契数为："+fun1(n));
    }
    //递归实现
    public static long fun1(long n ) {
        if(n<=1) return n;
        return fun1(n-1)+fun1(n-2);
    }
    //循环实现
    public static long fun2(long n) {
        if(n<=1) return n;
        long first=0;
        long second=1;
        for(int i=1;i<=n-1;i++) {
            long sum=first+second;
            first=second;
            second=sum;
        }
        return second;
    }
}

计时器代码

package 数据结构.Day01;

import java.text.SimpleDateFormat;
import java.util.Date;
/**
 * @author 缘友一世
 * @date 2022/8/27-10:58
 */
public class TimeTool {
    private static final SimpleDateFormat fmt=new SimpleDateFormat("HH:mm:ss.SSS");
    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 mill=(end-begin)/1000.0;
        System.out.println("耗时："+mill+"秒");
        System.out.println("------------");

    }
}

测试代码

package 数据结构.Day01;

/**
 * @author 缘友一世
 * @date 2022/8/27-11:10
 */
public class Test01 {
    public static void main(String[] args) {
        int n=46;
        TimeTool.check("fun1", new TimeTool.Task() {
            @Override
            public void execute() {
                System.out.println(Recursion.fun1(n));
            }
        });
        TimeTool.check("fun2", new TimeTool.Task() {
            @Override
            public void execute() {
                System.out.println(Recursion.fun2(n));
            }
        });
    }
}

总结
- 递归的时间复杂度是O(2^n)，而循环的时间复杂度是O(n)

一线性表(ArrayList)

线性表时最基本、最简单、也是最常用的一种数据结构、一个线性表是n个具有相同特征的数据元素的有序列表。
- 数组是一种顺序存储的线性表。
- 存储多个值，每个元素可以通过索引访问。
- 数据按照顺序存储在连续位置的存储器中。
优点：
- 空间利用率高
- 查询速度高效，通过下标来直接存取
缺点：
- 插入和删除比较慢，比如：插入或者删除一个元素时，整个表需要遍历移动元素来重新排一次顺序
- 不可以增长长度，有空间限制，当需要存取的元素个数可能多于顺序表的元素个数时，会出现“溢出”问题当元素个数远少于预先分配的空间时，空间浪费
动态数组接口设计

int size():/元素的数量
boolean isEmpty()://是否为空
boolean contains(Eelement）://是否包含某个元素
void add(E element)://添加元素到最后面
E get(int index)://返回index位置对应的元素
E set(int index,Eelement)://设置index位置的元素
void add(int index,E element）://往index位置添加元素
E remove(int index)://删除index位置对应的元素
int indexOf(E element)://查看元素的位置
void clear()://清除所有元素

1.1 线性表的增删改查实现

1.1.1 查找

 /**
     * 
     * @param element
     * @return i索引
     */
    public int indexOf(E element) {
        //查找一个null值
        if(element==null) {
            for(int i=0;i<size;i++) {
                if(elements[i]==null) {
                    return i;
                }
            }
        }else {
            for(int i=0;i<size;i++) {
                if(element.equals(elements[i])) {
                    return i;
                }
            }
        }
        return ELEMENT_NOT_FOUND;
    }

1.1.2 添加

图解

/**
    * 确保数组容量
    * */
    public void ensureCapacity(int capacity) {
        if(elements.length>capacity) {
            return ;
        }
        //扩容1.5倍
        E[] newElements = (E[])new Object[elements.length + (elements.length >> 1)];
        for(int i=0;i<size;i++) {
            newElements[i]=elements[i];
        }
        elements=newElements;
    }

    /**
    * 向index位置添加元素
    * */
    public void add(int index,E element ) {
        if(index<0 || index>size) {
            throw new ArrayIndexOutOfBoundsException("下标越界，允许范围：size 0=>"+size+"当前索引为："+index);
        }
        ensureCapacity(size);
        for(int i=size;i>index;i--) {
            elements[i]=elements[i-1];//元素右移
        }
        elements[index]=element;
        size++;
    }

1.1.3 删除

在这里插入图片描述

代码

/**
    * 移除index位置元素
    * @Param index 被移除元素的索引
    * @return 返回原来值
    * */
    public E remove(int index) {
        checkIndex(index);
        E old=elements[index];
        for(int i=index;i<size;i++) {
            elements[i]=elements[i+1];
        }
        size--;
        elements[size]=null;//清空最后一个元素
        //判断缩容
        if(size<=elements.length>>1) {
            System.out.println("开始缩容");
            ensureCapacity(elements.length>>1);//起始才函数什么也没做，调用函数有些多余
          //int res = elements.length>>1;//起始函数什么也没做，调用函数有些多余
            //System.out.println(res);
        }
        return old;
    }

1.2 综合代码

1.2.1 接口

package 数据结构.Day03;

/**
 * @author 缘友一世
 * @date 2022/8/28-17:14
 */
public interface List<E> {
    int size();
    int indexOf(E element);//查看元素的位置
    boolean contains(E element);//是否包含某个元素
    E get(int index);//返回index位置对应的元素
    E set(int index,E element);//设置index位置的元素
    void clear();//清除所有元素
    void add(E element);//添加元素到最后面
    void add(int index,E element);//向index位置添加元素
    E remove(int index);//删除index位置对应的元素
    boolean isEmpty();//是否为空
}

1.2.2 公共抽象类

package 数据结构.Day03;

/**
 * @author 缘友一世
 * @date 2022/8/28-17:26
 */
//公共代码 抽象类
public abstract class AbstractList<E> implements List<E>  {
    protected int size=0;
    protected static final int ELEMENT_NOT_FOUND=-1;

    /**
     * 元素个数
     * @return
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * 是否包含某个元素
     * @param element
     * @return
     */
    public boolean contains(E element) {
        return indexOf(element)!=ELEMENT_NOT_FOUND;
    }

    @Override
    public void add(E element) {
        add(size,element);
    }

    /**
     * 判断是否为空
     * @return true空| false 非空
     */
    public boolean isEmpty() {
        return size==0;
    }

    //判断是否越界
    public void checkIndex(int index) {
        if(index<0 || index>=size) {
            throw new ArrayIndexOutOfBoundsException("下标越界，允许范围：size 0=>"+(size-1)+"当前索引为："+index);
        }
    }
    public void checkAddIndex(int index) {
        if(index<0 || index>size) {
            throw new ArrayIndexOutOfBoundsException("下标越界，允许范围：size 0=>"+size+"当前索引为："+index);
        }
    }
}

1.2.3 实现的代码

package 数据结构.Day02;

import 数据结构.Day03.AbstractList;

/**
 * @author 缘友一世
 * @date 2022/8/27-14:39
 */
//动态数组 自动扩容
public class DynamicArray<E> extends AbstractList<E> {
    //保存当前元素长度
    // private int size =0;
    //定义默认初始化容量
    private static final int DEFAULT_CAPACITY=10;
    //查找失败返回值
    // private static final int ELEMENT_NOT_FOUND=-1;
    //用于保存数组元素
    private E[] elements=(E[]) new Object[DEFAULT_CAPACITY];

    public DynamicArray() {
        this(DEFAULT_CAPACITY);
    }
    /**
    *带参数初始化
     */
    public DynamicArray(int capacity) {
        if(capacity<DEFAULT_CAPACITY) {
            elements=(E[]) new Object[DEFAULT_CAPACITY];
        } else {
            elements=(E[]) new Object[capacity];
        }
    }

    /**
    * 当前数组是否为空
    * 空：true
    * 非空：false
    * @return */
    /*public boolean isEmpty() {
        return size==0;
    }*/

    /**
    * 是否包含元素
    *@Param element
    */
   /* public boolean contains(E element) {

        return indexOf(element)!=ELEMENT_NOT_FOUND;
    }*/

    /**
     *
     * @param element
     * @return i索引
     */
    public int indexOf(E element) {
        //查找一个null值
        if(element==null) {
            for(int i=0;i<size;i++) {
                if(elements[i]==null) {
                    return i;
                }
            }
        }else {
            for(int i=0;i<size;i++) {
                if(element.equals(elements[i])) {
                    return i;
                }
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 判断是否越界
     * @param index
     */
    public void checkIndex(int index) {
        if(index<0 || index>=size) {
            throw new ArrayIndexOutOfBoundsException("下标越界，允许范围：size 0=>"+(size-1)+"当前索引为："+index);
        }
    }
    /**
    * 返回对应索引的值 不存在返回-1
    * @Param index 元素的索引
    * @return 对应值 | -1
    * */
    public E get(int index) {
        checkIndex(index);
        return elements[index];
    }

    /**
    * 设置index位置元素的值
    *@Param index 需要设置的位置索引
    * @Param element 设置的值
    * @return 返回原来的值
    * */
    public E set(int index,E element) {

        return elements[index];
    }

    /**
    * 清空所有元素*/
    public void clear() {
        for(int i=0;i<size;i++) {
            elements[i]=null;
        }
    }

    /**
    * 返回当前元素的数量
    * */
   /* public int size() {
        return size;
    }*/

    /**
    * 添加元素到尾部*/
    public void add(E element) {
       /* if(size>elements.length-1) {
            System.out.println("开始扩容");
            ensureCapacity(size);
        }
        elements[size]=element;
        size++;*/
        add(size,element);
    }

    /**
    * 确保数组容量
    * */
    public void ensureCapacity(int capacity) {
        if(elements.length>capacity) {
            return ;
        }
        //扩容1.5倍
        E[] newElements = (E[])new Object[elements.length + (elements.length >> 1)];
        for(int i=0;i<size;i++) {
            newElements[i]=elements[i];
        }
        elements=newElements;
    }

    /**
    * 向index位置添加元素
    * */
    public void add(int index,E element ) {
        if(index<0 || index>size) {
            throw new ArrayIndexOutOfBoundsException("下标越界，允许范围：size 0=>"+size+"当前索引为："+index);
        }
        ensureCapacity(size);
        for(int i=size;i>index;i--) {
            elements[i]=elements[i-1];//元素右移
        }
        elements[index]=element;
        size++;
    }

    /**
    * 移除index位置元素
    * @Param index 被移除元素的索引
    * @return 返回原来值
    * */
    public E remove(int index) {
        checkIndex(index);
        E old=elements[index];
        for(int i=index;i<size;i++) {
            elements[i]=elements[i+1];
        }
        size--;
        elements[size]=null;//清空最后一个元素
        //判断缩容
        if(size<=elements.length>>1) {
            System.out.println("开始缩容");
            ensureCapacity(elements.length>>1);//起始才函数什么也没做，调用函数有些多余
          //int res = elements.length>>1;//起始才函数什么也没做，调用函数有些多余
            //System.out.println(res);
        }
        return old;
    }

    /**
    * 返回元素集合
    * */

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("size:" + size + " => [");
        for(int i=0;i<size;i++) {
            if(i!=0) {
                sb.append(" ,");
            }
            sb.append(elements[i]);
        }
        sb.append("]");
        return sb.toString();
    }

}

1.2.4 测试代码

package 数据结构.Day02;

/**
 * @author 缘友一世
 * @date 2022/8/27-17:21
 */
public class Test02 {
    public static void main(String[] args) {
        DynamicArray list = new DynamicArray(10);
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(6);
        list.add(7);
        list.add(8);
        list.add(9);
        list.add(10);
        System.out.println(list.toString());
        System.out.println(list.size());

        list.add(11);
        list.add(12);
        System.out.println(list.toString());
        list.remove(2);
        list.remove(2);
        list.remove(2);
        list.remove(2);
        System.out.println(list.toString());

        list.remove(2);
        System.out.println(list.toString());
    }
}

在这里插入图片描述

1.3 练习题

将数组中的0放在最后面，其他元素按照原来的顺序排列

 public static void test01() {
        int[] nums={0,1,0,3,12};
        int head=0;
        int tail=0;
        for(tail=0;tail<nums.length;tail++) {
            if(nums[tail]!=0) {
                if(head!=tail) {
                    nums[head]=nums[tail];
                    nums[tail]=0;
                }
                head++;
            }
        }
        for(int num:nums) {
            System.out.print(num+" ");
        }
    }
    //将数组中的0房子最后面，其他元素按照原来的顺序排列
    public static void test02() {
        int[] nums01={0,1,0,3,12};
        int head=0;
        int tail=0;
        int temp=0;
        for(tail=0;tail<nums01.length;tail++) {
            if(nums01[tail]!=0) {
                temp=nums01[head];
                nums01[head]=nums01[tail];
                nums01[tail]=temp;
                head++;
            }
        }
        for(int num:nums01) {
            System.out.print(num+" ");
        }
    }

在这里插入图片描述

二链表(LinkedList)

链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的
链表的优缺点
- 优点:可动态增加删除，大小可变
- 缺点：只能通过顺次指针访问，查询效率低
常见链表的分类

2.1 单向链表的实现

2.1.1 查询节点的值

思路图解
代码实现

 //判断是否越界
    public void checkIndex(int index) {
        if(index<0 || index>=size) {
            throw new ArrayIndexOutOfBoundsException("下标越界，允许范围：size 0=>"+(size-1)+"当前索引为："+index);
        }
    }
@Override
    public E get(int index) {
        //下标越界处理
        checkIndex(index);
        return node(index).element;
    }
    private Node<E> node(int index) {
        //下标越界处理
        checkIndex(index);

        Node<E> node=first;
        for(int i=0;i<index;i++) {
            node = node.next;
        }
        return node;
    }

2.1.2 添加节点

思路图解【情况分为头节点添加和非头节点添加】
代码实现

 public void checkAddIndex(int index) {
        if(index<0 || index>size) {
            throw new ArrayIndexOutOfBoundsException("下标越界，允许范围：size 0=>"+size+"当前索引为："+index);
        }
    }
   @Override
    public void add(int index, E element) {
        //下标越界处理 index可以等于size——在末尾添加
        checkAddIndex(index);
        //在头处添加节点
        if(index==0) {
            first = new Node<>(first, element);
        }else {
            //获取前一个节点的地址
            Node<E> pre = node(index - 1);
            //获取取后一个节点【相较于插入的节点】的地址
            Node<E> next = pre.next;
            //创建新的节点，并将本节点的地址
            pre.next=new Node(next,element);
        }
        //最后节点个数加1
        size++;
    }

2.1.3 删除节点

思路图解【情况分为头节点添加和非头节点添加】
代码实现

@Override
    public E remove(int index) {
        //下标越界检查 index<size
        checkIndex(index);
        Node<E> oldNode=first;//0x444
        if(index==0) {
            first=first.next;//0x888
        }else {
            //获取前一个节点
            Node<E> pre = node(index - 1);
            oldNode = pre.next;//0x666
            pre.next=pre.next.next;//0x777
        }
        size--;
        return oldNode.element;
    }

2.2 综合代码

接口和公共抽象类与线性表部分的相同

2.2.3 实现的代码

package 数据结构.Day03;

/**
 * @author 缘友一世
 * @date 2022/8/28-17:35
 */
public class LinkedList<E> extends AbstractList<E> {
    private Node<E> first;
    //内部类
    private class Node<E> {
        E element;//存储的数据
        Node<E> next;//下一个node的地址

        public Node( Node<E> next,E element) {
            this.element = element;
            this.next = next;
        }
    }

    @Override
    public E get(int index) {
        //下标越界处理
        checkIndex(index);
        return node(index).element;
    }

    private Node<E> node(int index) {
        //下标越界处理
        checkIndex(index);

        Node<E> node=first;
        for(int i=0;i<index;i++) {
            node = node.next;
        }
        return node;
    }

    @Override
    public E set(int index,E element) {
        //下标越界处理
        checkIndex(index);
        //通过node(index)获取element
        Node<E> node = node(index);
        E old = node.element;
        node.element=element;
        return old;
    }

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

    @Override
    public int indexOf(E element) {
        Node<E> node=first;
        if(element==null) {
            for(int i=0;i<size;i++) {
                if(node.element==null) {
                    return i;
                }
                node=node.next;
            }
        }else {
            for(int i=0;i<size;i++) {
                if(element.equals(node.element)) {
                    return i;
                }
                node=node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    @Override
    public void add(int index, E element) {
        //下标越界处理 index可以等于size——在末尾添加
        checkAddIndex(index);
        //在头处添加节点
        if(index==0) {
            first = new Node<>(first, element);
        }else {
            //获取前一个节点的地址
            Node<E> pre = node(index - 1);
            //获取取后一个节点【相较于插入的节点】的地址
            Node<E> next = pre.next;
            //创建新的节点，并将本节点的地址
            pre.next=new Node(next,element);
        }
        //最后节点个数加1
        size++;
    }

    @Override
    public E remove(int index) {
        //下标越界检查 index<size
        checkIndex(index);
        Node<E> oldNode=first;//0x444
        if(index==0) {
            first=first.next;//0x888
        }else {
            //获取前一个节点
            Node<E> pre = node(index - 1);
            oldNode = pre.next;//0x666
            pre.next=pre.next.next;//0x777
        }
        size--;
        return oldNode.element;
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("size:" + size + " => [");
        Node<E> node=first;
        for(int i=0;i<size;i++) {
            if(i!=0) {//只要不是第一个元素就拼接一个逗号和空格
                sb.append(" ,");
            }
            sb.append(node.element);//拼接每个元素
            node=node.next;
        }
        sb.append("]");
        return sb.toString();
    }

}

2.2.4 测试

package 数据结构.Day03;

/**
 * @author 缘友一世
 * @date 2022/8/28-22:59
 */
public class Test {
    public static void main(String[] args) {
        List Linked = new LinkedList<>();
        Linked.add(111);
        Linked.add(222);
        System.out.println(Linked.toString());
        Linked.add(0, 0);
        System.out.println(Linked.toString());
        Linked.remove(0);
        System.out.println(Linked.toString());
    }
}

在这里插入图片描述

2.3 双向链表的实现

2.3.1 增加新节点

链表中间位置

在这里插入图片描述

链表开始位置

在这里插入图片描述

链表末尾位置

在这里插入图片描述

空链表的添加

在这里插入图片描述

2.3.2 删除节点

链表中间位置

在这里插入图片描述

链表头位置【包括只一个节点的情况】

在这里插入图片描述

2.4 综合代码

接口和公共抽象类与线性表部分的相同

package 数据结构.Day04;

import 数据结构.Day03.AbstractList;

/**
 * @author 缘友一世
 * @date 2022/8/28-17:35
 */
public class LinkedListDouble<E> extends AbstractList<E> {
    private Node<E> first;
    private Node<E> last;
    //内部类
    private class Node<E> {
        E element;//存储的数据
        Node<E> pre;//上一个node的地址
        Node<E> next;//下一个node的地址

        public Node(Node<E> pre, Node<E> next, E element) {
            this.element = element;
            this.pre = pre;
            this.next = next;
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            if(pre!=null) {
                sb.append(pre.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 E get(int index) {
        //下标越界处理
        checkIndex(index);
        return node(index).element;
    }

    private Node<E> node(int index) {
        //下标越界处理
        checkIndex(index);
        if(index< (size>>1)) {
            //拿到first
            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.pre;
            }
            return node;
        }
    }

    @Override
    public E set(int index,E element) {
        //下标越界处理
        checkIndex(index);
        //通过node(index)获取element
        Node<E> node = node(index);
        E old = node.element;
        node.element=element;
        return old;
    }

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

    @Override
    public int indexOf(E element) {
        Node<E> node=first;
        if(element==null) {
            for(int i=0;i<size;i++) {
                if(node.element==null) {
                    return i;
                }
                node=node.next;
            }
        }else {
            for(int i=0;i<size;i++) {
                if(element.equals(node.element)) {
                    return i;
                }
                node=node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    @Override
    public void add(int index, E element) {
        //下标越界处理 index可以等于size——在末尾添加
        checkAddIndex(index);
        if(index==size) {
            Node<E> oldLast=last;
            last=new Node<E>(oldLast,null,element);
            if(oldLast==null) {
                first=last;
            }else {
                oldLast.next=last;
            }
        }else {
            Node<E> next = node(index);
            Node<E> pre = next.pre;
            Node<E> node = new Node<E>(pre, next, element);
            next.pre=node;
            if(pre==null) {
                first = node;
            }else {
                pre.next=node;
            }
        }
        size++;
    }

    @Override
    public E remove(int index) {
        //下标越界检查 index==size
        checkIndex(index);
       //记录被删除的节点
        Node<E> node = node(index);
        //记录被删除节点的前一个节点
        Node<E> pre = node.pre;
        //记录被删除节点的后一个节点
        Node<E> next = node.next;
        if(pre==null) {
            first=next;
        }else {
            //将前一个节点的next指向后一个节点
            pre.next=next;
        }
        if(next==null) {//index=size-1 删除最后一个元素
            last=pre;
        }else {
            //将最后一个节点的pre指向前一个节点
            next.pre=pre;
        }
        size--;
        return node.element;
    }
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("size:" + size + " => [");
        Node<E> node=first;
        for(int i=0;i<size;i++) {
            if(i!=0) {//只要不是第一个元素就拼接一个逗号和空格
                sb.append(" ,");
            }
            sb.append(node.toString());//拼接每个元素
            node=node.next;
        }
        sb.append("]");
        return sb.toString();
    }
}

2.4.1 测试

 public static void main(String[] args) {
        //双向链表
        System.out.println("双向链表：");
        LinkedListDouble<Object> doubleList = new LinkedListDouble<>();
        doubleList.add(1);
        doubleList.add(2);
        doubleList.add(3);
        System.out.println(doubleList);
        doubleList.add(0,4);
        System.out.println(doubleList);
        doubleList.remove(3);
        System.out.println(doubleList);
}

在这里插入图片描述

2.5 总结

在这里插入图片描述

三双向链表和动态数组的对比

双向链表VS动态数组
- 动态数组：开辟、销段内存空间的次数相对较少，但是可能造成空间的浪费（通过缩容解决)
- 双向链表：开辟、销毁内存空间的次数相对较多，但不会造成空间的浪费
- 如果需要频繁在末尾添加删除操作，动态数组和双向链表均可
- 如果频繁需要在头部讲行增删操作，建议使用双向链表
- 如果在任意位置增删元素建议使用双向链表
- 如果频繁查询（随机访问元素）建议使用动态数组