当前位置： 首页 > news >正文

线性表与链表的详解

news 来源：原创 2024/5/17 22:22:11

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

文章目录

  • 零 不同算法时间复杂度对比
  • 一 线性表(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动态数组
    • 动态数组：开辟、销段内存空间的次数相对较少，但是可能造成空间的浪费（通过缩容解决)
    • 双向链表：开辟、销毁内存空间的次数相对较多，但不会造成空间的浪费
    • 如果需要频繁在末尾添加删除操作，动态数组和双向链表均可
    • 如果频繁需要在头部讲行增删操作，建议使用双向链表
    • 如果在任意位置增删元素建议使用双向链表
    • 如果频繁查询（随机访问元素）建议使用动态数组

相关文章：

  • 常量指针、指针常量，指针数组、数组指针，函数指针、指针函数
  • java基于ssm+vue+elementui楼盘房屋销售系统 前后端分离
  • FastAPI 学习之路（三十三）操作数据库
  • 网络技术-Cisco路由器
  • 【halcon案例01 】金属工件几何测量
  • 第十章Redis_主从复制
  • 牛客 NC24858 [USACO 2009 Nov S]Job Hunt
  • 687 最长同值路径——Leetcode 天天刷（2022.9.2）【DFS】
  • 新店速递丨白玉兰(商务）酒店赣榆吾悦广场店 正式上线
  • Windows 10 安装 Redis
  • java基于springboot+vue+elementui的漫画投稿交流平台 前后端分离
  • Tomcat服务部署，虚拟主机配置，
  • 支持向量机
  • R Markdown 格式
  • Opncv 实现拍照、颜色识别和阈值选取
  • egg(89)--egg之redis的发布和订阅
  • JS基础之数据类型、对象、原型、原型链、继承
  • laravel5.5 视图共享数据
  • Netty 4.1 源代码学习：线程模型
  • node-sass 安装卡在 node scripts/install.js 解决办法
  • node入门
  • Python 反序列化安全问题（二）
  • TCP拥塞控制
  • 从伪并行的 Python 多线程说起
  • 欢迎参加第二届中国游戏开发者大会
  • 如何设计一个比特币钱包服务
  • 数据科学 第 3 章 11 字符串处理
  • 通信类
  • 微服务核心架构梳理
  • 我们雇佣了一只大猴子...
  • ​MySQL主从复制一致性检测
  • ​ssh免密码登录设置及问题总结
  • ​渐进式Web应用PWA的未来
  • ## 临床数据 两两比较 加显著性boxplot加显著性
  • #单片机（TB6600驱动42步进电机）
  • （4）Elastix图像配准：3D图像
  • (分布式缓存)Redis分片集群
  • （附源码）计算机毕业设计SSM教师教学质量评价系统
  • *上位机的定义
  • .\OBJ\test1.axf: Error: L6230W: Ignoring --entry command. Cannot find argumen 'Reset_Handler'
  • .NET 8.0 中有哪些新的变化？
  • .NET Core 中的路径问题
  • .NET Core工程编译事件$(TargetDir)变量为空引发的思考
  • .net 验证控件和javaScript的冲突问题
  • .NET/C# 检测电脑上安装的 .NET Framework 的版本
  • .NET/C# 如何获取当前进程的 CPU 和内存占用？如何获取全局 CPU 和内存占用？
  • .netcore 获取appsettings
  • .NET程序员迈向卓越的必由之路
  • .NET分布式缓存Memcached从入门到实战
  • .net实现客户区延伸至至非客户区
  • .Net下使用 Geb.Video.FFMPEG 操作视频文件
  • .xml 下拉列表_RecyclerView嵌套recyclerview实现二级下拉列表，包含自定义IOS对话框...
  • /使用匿名内部类来复写Handler当中的handlerMessage()方法
  • @property括号内属性讲解
  • @拔赤：Web前端开发十日谈