线性表与链表的详解

- 日理万妓 2024-04-07 12:20 48阅读 0赞

> 跟着阿姨走，幸福啥都有——关阿姨笔录  
> 
> 
> #### 文章目录 ####
> 
>  *  零 不同算法时间复杂度对比
>  *  一 线性表(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)  
        ![在这里插入图片描述][c0360514d9ba4369ba93da06ee8396ca.png]

## 一 线性表(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 添加 ####

*  图解  
    ![在这里插入图片描述][3745237784f246c8b67360132d79a05d.png]

/**
        * 确保数组容量
        * */
        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 删除 ####

![在这里插入图片描述][78a47ccffdb84b2e9ef40c902df2965b.png]

*  代码

/**
        * 移除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());
        }
    }

![在这里插入图片描述][d1817ccc5ea240c89edd0ba34d7055fc.png]

### 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+" ");
            }
        }

![在这里插入图片描述][7947b4207fe24c8c834d7b2ad6694082.gif_pic_center]

## 二 链表(LinkedList) ##

*  链表是一种链式存储的线性表，所有元素的内存地址不一定是连续的  
    ![在这里插入图片描述][9b2414d1b88442168de14e737fe99660.png]  
    ![在这里插入图片描述][f98441abe46248cc8b3f87247f911388.png]  
    ![在这里插入图片描述][3e37140745284c27ac68c635d5236422.png]
 *  链表的优缺点
    
     *  优点:可动态增加删除，大小可变
     *  缺点：只能通过顺次指针访问，查询效率低
 *  常见链表的分类  
    ![在这里插入图片描述][aba7c30d86ab4d66914aee7ceb71aadb.png]

### 2.1 单向链表的实现 ###

#### 2.1.1 查询节点的值 ####

*  思路图解  
    ![在这里插入图片描述][ebbb4518943b4a0685ab0cdb50b8eff5.png]
 *  代码实现

//判断是否越界
        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 添加节点 ####

*  思路图解【情况分为头节点添加和非头节点添加】  
    ![在这里插入图片描述][bc55d8dd920c4b1a88f9ae30e0446590.png]  
    ![在这里插入图片描述][d2e72979c1b448db83022b92a6f174c0.png]
 *  代码实现

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 删除节点 ####

*  思路图解【情况分为头节点添加和非头节点添加】  
    ![在这里插入图片描述][99beb621801f4225aa09e3472c4956bc.png]  
    ![在这里插入图片描述][e2f6e374200945d2b76535ece7e651fa.png]
 *  代码实现

@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());
        }
    }

![在这里插入图片描述][bb69ac20435a4cbf8ea0cafedff9a3b1.png]

### 2.3 双向链表的实现 ###

#### 2.3.1 增加新节点 ####

##### 链表中间位置 #####

![在这里插入图片描述][7400d0534b124af6a1787e78333e50e4.png]

##### 链表开始位置 #####

![在这里插入图片描述][9ef902c84e8a4cb9abf2ef156d86a31e.png]

##### 链表末尾位置 #####

![在这里插入图片描述][006096d5b2c44462a8e149c352872f46.png]

##### 空链表的添加 #####

![在这里插入图片描述][86773e878cf24337ad0b2401fc58cdb8.png]

#### 2.3.2 删除节点 ####

##### 链表中间位置 #####

![在这里插入图片描述][95dcc3a2b4dc4f248346f1f240166846.png]

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

![在这里插入图片描述][8431d4c79a7d4899a1d08c5b742b234e.png]

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

![在这里插入图片描述][d81c5dcf156e4277bccf97a018ae10a5.png]

#### 2.5 总结 ####

![在这里插入图片描述][cbd6dabbf8514084992b282fb621e257.png]

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

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

[c0360514d9ba4369ba93da06ee8396ca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/3419b0527d50425f946e9fc5dca01dbc.png
[3745237784f246c8b67360132d79a05d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/8e8cea1604f1460b85db26e9e2905a9d.png
[78a47ccffdb84b2e9ef40c902df2965b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/8c80f7ddc725451da7d30deac6341f25.png
[d1817ccc5ea240c89edd0ba34d7055fc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/220a82950a9544dda3782c4cc10a1a2e.png
[7947b4207fe24c8c834d7b2ad6694082.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/5d2702a0c6b84edc94533e15cb4f2d35.gif
[9b2414d1b88442168de14e737fe99660.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/80783a903a044885b6f10675f1df85f0.png
[f98441abe46248cc8b3f87247f911388.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/2225287fed9b4d3688415c9c184ed1a8.png
[3e37140745284c27ac68c635d5236422.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/10bff556100849cc800ee586f3b25938.png
[aba7c30d86ab4d66914aee7ceb71aadb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/af402ff272bf4cc8b6f5e26f46799a98.png
[ebbb4518943b4a0685ab0cdb50b8eff5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/6ff8d643e76845a7bdb01dd8ff8d7e16.png
[bc55d8dd920c4b1a88f9ae30e0446590.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/562cfcd41dc144848895c07973c6a65d.png
[d2e72979c1b448db83022b92a6f174c0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/af578fb7ee0e415d80d6496f7df7650d.png
[99beb621801f4225aa09e3472c4956bc.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/09fb91a154d54e749745ba35aacabeb2.png
[e2f6e374200945d2b76535ece7e651fa.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/d9bee78af7cb45d79da1b1c1c05bfcf2.png
[bb69ac20435a4cbf8ea0cafedff9a3b1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/1951924a64094b48ab61c63989d55001.png
[7400d0534b124af6a1787e78333e50e4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/05c342664f654b0e8f030437b0d9c056.png
[9ef902c84e8a4cb9abf2ef156d86a31e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/e75db9fb73d745df8682bede8a111313.png
[006096d5b2c44462a8e149c352872f46.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/fb7c3fdf0fa148fba2f248e2df8c547e.png
[86773e878cf24337ad0b2401fc58cdb8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/25e16e13eaf14fd8b5e7a64ab76a4f1b.png
[95dcc3a2b4dc4f248346f1f240166846.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/ddfa19a1a85040dda133028509b94c7b.png
[8431d4c79a7d4899a1d08c5b742b234e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/89f768dc97464974a2ada84cf3012b18.png
[d81c5dcf156e4277bccf97a018ae10a5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/a143ce99b4d14c91983b79df56c647fc.png
[cbd6dabbf8514084992b282fb621e257.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/835265d9e31f499096b00dc145b7f058.png