Java数据结构之顺序表和链表精解

前言

两个数据结构：顺序表和链表

数据结构是一门学科，和语言无关。

数据 + 结构：一种描述和组织数据的方式。

1. 顺序表

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

问题引入：一个数组放在这，我们如何才能自己不去数，让程序自己进行计数？

答：在引入变量，每次放一个元素就更新一次。（如下图，为问题的示意）

也就是说顺序表的底层其实是一个数组，在 java 当中顺序表都是动态的因为 java 当中的new 其实就相当于 c 语言中的 malloc 。

代码实现

我们来实现一个动态顺序表，以下是需要支持的接口。 各个函数的具体实现部分要我们自己来写。

public class MyArrayList {//此为创建一个接口
   public int[] elem;
   public int usedSize;
   public static int capacity = 10;

public MyArrayList() {
       this.elem = new int[capacity];//新建一个数组
   }
   public boolean isFull() {
       return this.usedSize == capacity;//判断数组是否已满
   }

// 在 pos 位置新增元素
   public void add(int pos, int data) { //pos为要插入元素的下标，data为要插入的数据
       if (pos < 0 || pos > this.usedSize) {
           System.out.println("pos位置不合法！");
           return;
       }
       //1、满的情况   2、pos的合法情况
       if (isFull()) {
           //扩容
           this.elem = Arrays.copyOf(this.elem, 2 * capacity);
           capacity *= 2;//新的容量
       }//此处调用前面 isfull（） 函数来判断是否已满，返回真，执行if里面的语句，扩容两倍；若不满，返回假，跳过if内的语句。
       for (int i = this.usedSize - 1; i >= pos; i--) {
           this.elem[i + 1] = this.elem[i];
       }//在前面的代码确定数组里面有盈余位置的情况下，将前一个数赋给后一个位置，从而腾出 pos 位置
       this.elem[pos] = data; //给pos 位置的函数赋我们想要的值（即data）
       this.usedSize++;//usedsize 是奇数器，pos位置增加一个数组，自然要算上
   }

// 打印顺序表
   public void display() {
       for (int i = 0; i < this.usedSize; i++) {
           System.out.print(this.elem[i] + " ");
       }
       System.out.println();
   }// 此处使用for循环遍历打印

public boolean isEmpty() {
       return this.usedSize == 0;
   }//判断数组是否为空

// 判定是否包含某个元素
   public boolean contains(int toFind) {
       if (isEmpty()) return false;
       for (int i = 0; i < this.usedSize; i++) {
           if (this.elem[i] == toFind) {
               return true;
           }
       }
       return false;
   }//toFind 为我们要查找的元素，先判断是否为空，再用循环遍历判断是否为该数

// 查找某个元素对应的位置
   public int search(int toFind) {
       if (isEmpty()) return -1;
       for (int i = 0; i < this.usedSize; i++) {
           if (this.elem[i] == toFind) {
               return i;
           }
       }
       return -1;
   }//这个查找和上面的那个判断唯一的区别就是上面返回的是真与假，这个返回的是查到的那个数，本质的方法都是一样的

// 获取 pos 位置的元素
   public int getPos(int pos) {
       if (isEmpty()) {
           //return -1; 业务的处理
           throw new RuntimeException("顺序表是空的");//手动抛出错误(异常)
       }
       if (pos < 0 || pos >= this.usedSize) {
           throw new RuntimeException("pos不合法");//手动抛出错误(异常)
       }

return this.elem[pos];
   }//这个其实很简单，只需排除一下空表和pos 不合法的情况，之后返回 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不合法！");
           return;
       }
       if (isEmpty()) {
           System.out.println("顺序表为空！");
           return;
       }
       this.elem[pos] = value;
   }//这个也简单，只要判断一下 数组是否不合法，是否为空，直接 this.elem[pos] = value就行了

//删除第一次出现的关键字key
   public void remove(int toRemove) {
       if (isEmpty()) return;
       int index = search(toRemove);
       if (index == -1) {
           System.out.println("没有你要删除的数字");
           return;
       }
       for (int i = index; i < this.usedSize - 1; i++) {
           this.elem[i] = this.elem[i + 1];
       }
       this.usedSize--;
   }
   //这里就是判断数组是否为空，index 是否存在（此处调上面 search 函数），最后用for 循环遍历，将后一个元素覆盖在前一个元素上面

// 清空顺序表
   public void clear() {
       for (int i = 0; i < this.usedSize; i++) {
           this.elem[i] = 0;
       }
       this.usedSize = 0;
   }//用for循环遍历每一个元素，将其赋值为 0 ，之后再将计数器 usedsized 也赋值为 0
}

顺序表的写起来是非常简单的，但是他也是有一定的缺陷和不足的。它主要是负责实现增删查改的功能，查改功能是很简便的，如果直接就给定下标的话，时间复杂度就是O（1），但是增删的话，时间复杂度就必定为 O(N)，这就非常麻烦（也就是说以后当我们工作中要用查改就选用顺序表就是最优选的）。所以我们接下来就有必要引入链表这一种数据结构。

2. 链表

链表是一种物理存储结构上非连续存储结构，其存储结构便是上面放值，下面放下一个节点的地址，也就是说，虽然他是不连续的，当上一个节点仍然能找到下一个节点，类似于链子一样，一个串一个，但区别是，链表彼此之间不相接触。

链表图解

代码实现

class Node {//创建一个节点类
//一个节点是有两个域或者多个域的，以下便是创建的两个域
   public int val;//链表里面的数值
   public Node next;//这是一个引用变量，用于标识每个链表单元的下一个数的地址，因为它存的是节点，而节点的类型就是Node，所以我们也用Node 来定义这个变量。

public Node(int val) { //这是一个类里面的一个方法用来给链表当中的val赋值
       this.val = val;//因为next存的hi下一个节点的地址，所以我们是不知道也不能赋值的
       }
}
//链表
public class MyLinkedList {//此处为创建链表的接口
    public Node head;//标识单链表的头节点（这也是一个引用变量）

/**
    * 穷举的方式 创建链表  当然很low。此处只是为了好理解
    */
   public void createList() {
       Node node1 = new Node(12);//新建一个节点的对象node1，此为节点1，赋值为12
       Node node2 = new Node(3);//此为节点2，赋值3
       Node node3 = new Node(5);//此为节点3，赋值5
       Node node4 = new Node(2);//此为节点4，赋值6
       node1.next = node2;//node1中的next存node2（node2是一个对象的引用，存的是对象在堆中的地址）

// 也就是说node1.next指向node2指向的地址

node2.next = node3;//以下三个原理同上
       node3.next = node4;
       this.head = node1;//此处为定义一个head（后面head可能会有改动）

}

/**
    * 打印单链表
    */
   public void show() {
       Node cur = this.head;//将head的值暂时存到cur中，这样就是单纯地是cur在变，head值不改变
       while(cur != null) {
           System.out.print(cur.val+" ");
           cur = cur.next;//通过这道程序将cur依次向后移动最后到空的时候打印出来
       }
       System.out.println();
   }

//得到单链表的长度
   public int size() {
       Node cur = this.head;//同样地，此处还以cur为介质向后移动
       int count = 0;
       while (cur != null) {
           count++;//4  cur 依次经过各个节点的时候count便随之计数
           cur = cur.next;
       }
       return count;
   }

//查找是否包含关键字key是否在单链表当中 15
   public boolean contains(int val) {//这里函数参数中的val就是我们要查找的 key
       Node cur = this.head;
       while (cur != null) {//同样的方法遍历节点
           if(cur.val == val) {
               return true;
           }
           cur = cur.next;
       }
       return false;//如果遍历完了都没有找到那就肯定没有了
   }

//头插法
   public void addFirst(int data) {//date为要插入的数据
       Node node = new Node(data);//此处为创建要插入的节点（对象）内部存储的值为 date
       if(this.head == null) {//判断头结点是否为空
           this.head = node;// 若为空，则根本没有链表，直接将要插入的节点赋给head
       }else { //此为有链表存在的状况
           node.next = this.head;//此处操作让head原本指向的对象(节点)成为链表中的第二个节点
           this.head = node;
           //上面的操作让head指向了node指向的节点(head是头结点的标志，自然要让他移到第一位)
       }
   }

//尾插法
   public void addLast(int data) {//data为要插入的数据
       Node node = new Node(data);//新建一个节点改值为data
       if(this.head == null) {//判断链表是否为空，若为空，则为一个节点便也是最后一个
           this.head = node;//直接让head指向node指向的节点即可
       }else {//若节点不为空时
           Node cur = this.head;//将head中的地址赋给中间变量cur
           while (cur.next != null) {
               cur = cur.next; //用cur遍历节点
           }
           cur.next = node;//这是的cur已经待在了最后一个节点上它的next上没有东西了
                           //所以这个时候将node指向的地址交给next，既完成了节点的插入
       }
   }

public Node searchPrev(int index) {
       Node cur = this.head;//同样地，以 cur为介质
       int count = 0;
       while(count != index-1) {
           cur = cur.next;//用cur 遍历链表
           count++;
       }
       return cur;//此时返回的 cur刚好指向 index-1这个节点
   }

//任意位置插入,第一个数据节点为0号下标
   public void addIndex(int index,int data) {
       if(index < 0 || index > size()) {//判断index是否合法
           System.out.println("下标不合法");
           return;
       }
       //头插法
       if(index == 0) {//index为0时，就是头插法
           addFirst(data);
           return;
       }
       //尾插法
       if(index == size()) {//index为数组长度是就是尾插法
           addLast(data);
           return;
       }
       Node cur = searchPrev(index);//让cur 拿到第index-1位置节点地址
       Node node = new Node(data);//创建一个存了数据为data 的节点
       node.next = cur.next;//将刚刚创建的节点中的next存进 cur 中的next(即把index的地址放到node的next里)
       cur.next = node;//再将node中存着的地址放到cur的next中
       //插中间归根到底就是next的交换，以下为传递顺序：
       //index-1中index的地址 ——> node.next
       //node的地址 ——> cur.next
   }

//下面这段代码用来找val的前驱节点
   public Node searchPrevNode(int val) {
       Node cur = this.head;//还是以 cur 为中间量
       while (cur.next != null) {//cur 遍历至数组的最后一位
           if(cur.next.val == val) {//这里是判断cur的下一个节点中的值是否为val
               return cur;//如果是的就返回cur
           }
           cur = cur.next;
       }
       return null;
   }

//删除第一次出现关键字为key的节点
   public void remove(int val) {
       if(this.head == null) return;

//单独判断头节点的问题
       if(this.head.val == val) {
           this.head = this.head.next;
           return;//这段代码的意思就是如果就是如果第一个节点中的值就是要删除的值
           //那么直接就让第一个节点的引用指向下一个节点，其实就是忽略第一个起到了一个删除效果
           //而原来第一个节点变成了没有人引用的对象会被jvm回收
       }
       Node cur = searchPrevNode(val);//拿到下一个节点值为val的cur
       if(cur == null) {//
           System.out.println("没有你要删除的节点！");
           return;
       }
       //下面就是cur 存在的情况
       Node del = cur.next;//创建一个节点del让其使用cur中下一个节点的地址(也就是要删的val地址)
       cur.next = del.next;//再把del中的存的下一个地址赋给 cur，那么就间接地抹去了val
   }
   //删除所有值为key的节点
   public void removeAllKey(int val) {
       if(this.head == null) {//节点是否为空？
           return;
       }
       Node prev = this.head;//让 prev指向 head指向的对象(prev本质上就是前驱节点)
       Node cur = this.head.next;//让 cur指向 head.next位置
       while (cur != null) { //用cur 来遍历数组
           if(cur.val == val) { //
               prev.next = cur.next;//抹去要删的节点
               cur = cur.next;//移动至下一个节点处
           }else {//以下是 cur处的值 不等于 val 的情况
               prev = cur;//将prev移到cur的位置
               cur = cur.next;//再将cur 向后移动
           }
       }
       //只有头结点且头结点便是要删除的val的情况
       if(this.head.val == val) {
           this.head = this.head.next;
       }
   }
   public void clear(){

}

}

来源：https://blog.csdn.net/qq_54693675/article/details/119983075