• 线性表与链表的详解

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

    文章目录

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

    • 分别以递归和循环实现斐波那契函数
    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;
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 计时器代码
    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("------------");

    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 测试代码
    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));
            }
        });
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 总结
      • 递归的时间复杂度是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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    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
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    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
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    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
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55

    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
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202

    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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    在这里插入图片描述

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    在这里插入图片描述

    二 链表(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;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    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++;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    2.1.3 删除节点

    • 思路图解【情况分为头节点添加和非头节点添加】
      在这里插入图片描述
      在这里插入图片描述
    • 代码实现
    @Override
    public E remove(int index) {
        //下标越界检查 index
        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;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

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

}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127

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


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    在这里插入图片描述

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


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    在这里插入图片描述

    2.5 总结

    在这里插入图片描述

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

    • 双向链表VS动态数组
      • 动态数组：开辟、销段内存空间的次数相对较少，但是可能造成空间的浪费（通过缩容解决)
      • 双向链表：开辟、销毁内存空间的次数相对较多，但不会造成空间的浪费
      • 如果需要频繁在末尾添加删除操作，动态数组和双向链表均可
      • 如果频繁需要在头部讲行增删操作，建议使用双向链表
      • 如果在任意位置增删元素建议使用双向链表
      • 如果频繁查询（随机访问元素）建议使用动态数组
  • 相关阅读:
    跑步运动耳机哪个牌子好、推荐几款专业跑步耳机
    leetcode34.排序数组中查找元素第一个和最后一个位置两种解题方法（超详细）
    自动化测试：webdriver的断言详解
    《Large Language Models for Generative Information Extraction: A Survey》阅读笔录
    JVM类加载器（详解）
    pandas学习资源
    分享几个.NET开源的AI和LLM相关项目框架
    泊松随机变量的分解与求和
    腾讯云CVM标准型S5性能如何？CPU采用什么型号？
    离线安装PostgreSQL数据库(v13.4版本)
  • 原文地址：https://blog.csdn.net/yang2330648064/article/details/126668057