[数据结构与算法]Java版顺序表和链表

前言

本篇博客主要从Java角度讲解了顺序表和链表的知识，篇幅较长，但如果能够阅读下来，我相信应该会让你在数据结构初阶的认知有一定的提升。

还在持续更新中~~

顺序表

1、什么是线性表？

线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见
的线性表：顺序表、链表、栈、队列、串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的
线性表在物理上存储时，通常以数组和链式结构的形式存储
一般数组物理上是连续的，链式结构物理上是不连续的

2、什么是顺序表？

简单来讲，顺序表就是数组。但是又有和数组不同的地方
例如数组有以下特点：

1. 不可扩容，初始化多少就只能存多少元素
2. 不知道当前数组中有多少有效数据
3. 对数组进行操作需要手动实现
4. 可以在任意有效位置放置元素

实际上顺序表等于数组加上一定的操作逻辑

2.1 概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

从这里可以看出顺序表在逻辑上和物理上都是连续的

顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储。
2. 动态顺序表：使用动态开辟的数组进行存储。

静态顺序表适用于明确知道需要存多少数据的场景，例如在刷算法题要使用数组的时候，我们通常会开辟最大长度+10(+10是为了防止越界访问)。

但大多数情况下，数据量都是未知的，使用静态顺序表的定长数组会导致空间开多了浪费，开少了不够用。

相比之下动态顺序表更灵活, 根据需求来动态的分配空间大小

2.2 顺序表实现

这里采用实现一个自己的ArrayList来深刻体会顺序表内部实现逻辑。代码如下，写的比较详细，但如果想真正学会还是要自己动手练几遍。

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 凩子
 * Date: 2022-07-02
 * Time: 11:23
 */

import java.util.*;
// 模拟ArrayList
// 这里定义的elem为int类型的数组, 如果想存其他类型的话可改成对应类型或改为泛型
class MyArrayList {
    // 实例成员变量: 不初始化默认值就是对应的0值
    // 定义一个数组引用, 不建议直接初识化, 因为当前不知道用户需求
    public int[] elem; // 不初始化为null
    // 表示当前有效元素个数
    public int usedSize; // 不初始化为0

    // 无参构造方法, 默认数组长度为5
    public MyArrayList() {
        this.elem = new int[5];
    }
    // 有参构造方法, 数组长度由用户来传入
    public MyArrayList(int len) {
        if (len > 0) {
            this.elem = new int[len];
        }else {
            System.out.println("输入数组长度非法, 自动生成大小为5的数组");
            this.elem = new int[5];
        }
    }

    // 在pos位置新增一个元素, 从0开始
    public void add(int pos, int data) {
        // 判断插入位置是否合法
        // 小于0下标不合法
        // 大于0是因为顺序表必须为逻辑连续存储, 故最多只能尾插一个元素
        // 即除第一个元素外, 每个元素都必有一个前驱, 有效元素之间不可有间隔
        // 例已有一个元素, 现在只能尾插或在下标0的位置插入, 不可放在2及以后的下标
        if (pos < 0 || pos > this.usedSize) {
            System.out.println("pos位置不合法, pos=" + pos);
            return;
        }
        // 如果数组已满, 则对数组进行二倍扩容
        if (isFull()) {
            // 使用elem指向新数组
            this.elem = Arrays.copyOf(this.elem, 2 * this.elem.length);
        }
        // 移动需要后移的元素
        for (int i = this.usedSize; i > pos; i--) {
            this.elem[i] = this.elem[i-1];
        }
        // 放置元素
        this.elem[pos] = data;
        // 有效元素加一
        this.usedSize++;
    }

    // 判断数组是否已满
    public boolean isFull() {
        // 如果有效元素数量等于数组长度就意味着数组已满
        return this.elem.length == this.usedSize;
    }

    // 打印顺序表
    public void display() {
        // 注意要遍历的元素是有效元素, 不是整个数组
        for (int i = 0; i < this.usedSize; i++) {
            System.out.print(this.elem[i] + " ");
        }
        System.out.println();
    }

    // 查找某个元素对应的位置
    public boolean contains(int find) {
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == find) {
                return true;
            }
        }
        return false;
    }

    // 查找某个元素第一次出现过的下标
    public int search(int find) {
        for (int i = 0; i < this.usedSize; i++) {
            if (this.elem[i] == find) {
                return i;
            }
        }
        // 遍历过所有有效元素后没找到即为没出现过, 返回-1即可
        return -1;
    }

    // 获取pos位置的元素
    public int getPos(int pos) throws Exception {
        // 合法下标范围[0, usedSize-1]
        // 小于0的下标是非法的
        // 大于usedSize, 通过 add()方法可以知道这是不允许存在的
        // usedSize表示的是有效元素个数, 假如只有一个有效元素, 则usedSize=1。
        // 但是该元素的下标是0, usedSize指向的是一个无效位置
        if (pos < 0 || pos >= this.usedSize) {
            throw new Exception("输入位置非法");
        }
        return this.elem[pos];
    }

    // 获取顺序表有多少有效元素
    public int size() {
        return this.usedSize;
    }

    // 将pos位置的元素设置为value
    public void setPos(int pos, int value) {
        if (pos < 0 || pos >= this.usedSize) {
            System.out.println("pos位置不合法, pos=" + pos);
            return;
        }
        this.elem[pos] = value;
    }

    // 删除第一次出现的关键字key
    // 注意此处的数组元素类型为int
    // 如果元素类型为引用类型, 如自创建的Student
    // 按照以下方式删除一个元素后, 将usedSize-1
    // 但其实最后一个元素仍然在指向它所指向的对象, 这样会导致内存泄漏 (一个对象没有被任何变量引用才算真正被删除)
    // 所以正确做法是将各元素移动后还要将最后一个值置为null (注意前提条件是元素类型为引用类型)
    public void remove(int toRemove) {
        // 查找要删除元素的下标
        int index = this.search(toRemove);
        if (index == -1) {
            System.out.println("不存在此元素");
            return;
        }
        // 注意边界, 删除是通过将下一个元素放置到当前位置来实现的
        // 所以最终只能遍历到倒数第二个位置, 以读取倒数第一个元素并放置到倒数第二个位置
        // 如果遍历到倒数第一个位置, 当usedSize=elem.length时, 则this.elem[i+1]会出现下标越界情况;
        for (int i = index; i < this.usedSize-1; i++) {
            this.elem[i] = this.elem[i+1];
        }
        // 记得有效数据数量要减一
        this.usedSize--;
    }

    // 清空顺序表
    // 如果是引用类型要遍历一遍数组, 将每一个元素置空
    public void clear() {
        this.usedSize = 0;
    }
}

当主函数实例化一个MyArrayList时（命名为myArrayList），会出现下面的场景。

myArrayList这个引用会被放到栈里面。所有实例化的元素都会被存放到堆中，所以myArrayList会指向堆中的一块区域，这块区域存放的就是被new出来的MyArrayList。new MyArrayList时构造方法会自动new一个数组，这个被new出来的数组也会在堆中开辟一块空间（注意不是在MyArrayList这块区域），elem会指向这块区域。

2.3 顺序表的问题及思考

优点

1. 可以通过下标快速查找到指定元素，时间复杂度为O(1)
2. 空间利用率较高，所有的空间开销都用来存放数据

缺点

1. 顺序表中间/头部的插入删除，时间复杂度为O(N)，时间复杂度较大
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的资源开销。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，假如我们只想再插入5个数据，后面不再插入了，那么就浪费了95个数据空间。

思考： 如何解决以上问题呢？不妨先学习一下链表的知识，看看能否从中找到答案。

链表

1、链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的。
链表逻辑上连续，物理上不一定连续

实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

• 单向、双向
• 带头、不带头
• 循环、非循环
  
  在这里主要讲解单向不带头节点非循环和双向不带头节点非循环

单向不带头节点非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。

双向不带头非循环链表：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

为了大家能够更好的理解这几种结构，以下就画图来尽可能的展示一下，希望能对大家有所帮助。

2、链表实现

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 凩子
 * Date: 2022-07-04
 * Time: 10:23
 */
 
/**
 * LinkedList底层是通过双向链表实现的, 这里是借鉴了一下名字
 * 此处为单向不带头非循环链表
 */
// 根据上面的展示图我们可以将每一个节点进行抽象化, 创建为一个类
class ListNode {
    // 数据域, 此处为了好操作, 所以定为int类型, 当然也可以使用自定义类型
    public int val;
    // 指针域, 存储下一节点地址, 此处为引用
    public ListNode next;

    public ListNode() {

    }
    // 已知数据是多少的构造方法
    public ListNode(int val) {
        this.val = val;
    }

}

public class MyLinkedList {
	ListNode head = null;
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.createList();
        list.display();
    }

    // 此处采用手动创建节点并连接的方式先让大家感受一下链表
    // 在讲解一些知识之后再采用自动创建的方式
    public void createList() {
        // 创建五个节点, 初识默认next==null
        ListNode listNode1 = new ListNode(12);
        ListNode listNode2 = new ListNode(45);
        ListNode listNode3 = new ListNode(6);
        ListNode listNode4 = new ListNode(8);
        ListNode listNode5 = new ListNode(5);
        // listNode1的下一个节点为listNode2, 后续以此类推
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        listNode4.next = listNode5;
        // head指向了listNode1所指向的对象
        // 这里的head只是一个标记, 用来表示第一个节点, 当前链表并没有头节点
        head = listNode1;

    }
    public void display() {
        // 循环遍历, 先读取当前节点的数值, 然后移动至下一节点
        // 最后一个节点的下一节点为null, 所以当tmp==null时就可以结束了
        // 注意不要直接使用head进行遍历, 因为遍历一次之后head就变成了null, 就无法进行其他操作了
        // 所以这里使用了一个tmp的临时变量指向head所指向的节点, 然后使用tmp来进行循环遍历
        // tmp只是一个临时变量, display()执行完毕销毁即可, 所以变成null也无所谓
        ListNode tmp = this.head;
        while (tmp != null) {
            System.out.println(tmp.val);
            tmp = tmp.next;
        }
    }
        // 头插法
    // 顾名思义, 就是在开头插入一个节点
    // 头插法无需区分head是否为null
    public void addFirst(int data){
        // 创建新节点
        ListNode tmp = new ListNode(data);
        // 注意下面这两行代码顺序不可替换, 如果替换就会变成只有一个节点的环了
        // 设置新节点的下一个节点为当前链表的第一个节点
        tmp.next = this.head;
        // 将头节点标识指向新节点
        this.head = tmp;
    }
    // 尾插法
    // 在链表的末尾插入一个节点
    // 需要区分head是否为null
    public void addLast(int data) {
        // 创建新节点
        ListNode tmp = new ListNode(data);
        // 如果链表为空, 没有则直接用head标记新节点为头节点, 标记后记得直接return, 否则还会继续执行后续代码
        // 如果不做判断直接往下走的话在while判断的时候
        // 可能会出现null.next空指针异常(当head为null时)
        if (this.head == null) {
            head = tmp;
            return;
        }
        // 如果链表不为空, 则需要遍历至最后一个节点, 然后将最后一个节点的next指向新节点
        ListNode cur = this.head;
        // 最后一个节点的next一定为null, 所以用cur.next != null找最后一个节点
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = tmp;
    }
    // 任意位置插入,第一个数据节点为0号下标
    // 注意: 链表是没有下标的, 这里只是按照节点顺序来描述的, 并不是真的下标
    public boolean addIndex(int index,int data) {
        int size = this.size();
        // 非法插入直接返回失败即可
        if (index < 0 || index > size) {
            return false;
        }
        // 插入0下标就是头插, size下标就是尾插
        if (index == 0) {
            addFirst(data);
            return true;
        }
        if (index == size) {
            addLast(data);
        }

        ListNode tmp = new ListNode(data);
        ListNode prev = this.head;
        // 这里相当于是走了index-1步, 找到要插入位置的前一个节点
        // 因为这里是单链表, 我们需要得知前一个节点才能将新节点放置在它的后面
        // 如 0->1->2, 在1下标的位置插入3
        // 则需要先创建一个3节点, 将3节点的next指向1, 再将0的next指向3才算成功插入
        int count = 0;
        while (count != index-1) {
            prev = prev.next;
            count++;
        }
        tmp.next = prev.next;
        prev.next = tmp;
        return true;
    }
    // 查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        ListNode tmp = this.head;
        while (tmp != null){
            if (tmp.val == key) {
                return true;
            }
            tmp = tmp.next;
        }
        return false;
    }
    //得到单链表的长度
    public int size() {
        ListNode tmp = this.head;
        // count记录链表长度
        int count = 0;
        while (tmp != null) {
            count++;
            tmp = tmp.next;
        }
        return count;
    }
    // 清空整个链表
    public void clear() {
        // 暴力做法
        // 销毁一个对象其实就是没用引用指向这个对象了
        // 链表正是因为有当前的head这个引用才一直没有被清理掉(head的next指向下一个, 下一个的next又继续指向下下一个, 以此类推)
        // 当头节点不被head所引用, 那就消失了, 从而后续的节点也就都消失了
        // 建议一个一个的置空, 不要采用暴力做法(当然暴力做法也可以达到效果)
//        this.head = null;
        // 一个一个的设置为空
        ListNode cur = this.head;
        // 当前cur不等于null就说明还有节点未被清理
        while (cur != null) {
            // 先记录一下下一个节点
            ListNode curNext = cur.next;
            // 当前节点的指针域设为null
            // 当一个节点不再被已知变量引用, 就会被垃圾回收器回收
            cur.next = null;
            // cur指向下一个节点
            cur = curNext;
        }
        // 上面将head的后续节点都清理掉了
        // head还在引用第一个节点, 所以还需要在这里将head置为null
        head = null;
    }
}

总结

提示：这里对文章进行总结：