Snake8859

数组和链表

7/10/2022

# 数组

# 定义

数组是一种常见的数据结构，它由相同类型的元素组成，并且使用一块连续的内存来存储。数据可用直接利用元素的索引（index）来计算出元素对应的存储地址。它的特点是能提供随机访问但是容量有限。

从本质上讲，数组与顺序表、链表 (opens new window)、栈 (opens new window)和队列 (opens new window)一样，都用来存储具有 "一对一" 逻辑关系数据的线性存储结构。

img

# Java的数组

数组变量的声明和创建数组可以用一条语句完成，如下所示：

dataType[] arrayRefVar = new dataType[arraySize];
1

另外，你还可以使用如下的方式创建数组。

dataType[] arrayRefVar = {value0, value1, ..., valuek};
1

数组的元素是通过索引访问的。数组索引从 0 开始，所以索引值从 0 到 arrayRefVar.length-1。

数据遍历可通过for循环、for-each循环、增强for循环实现。

  1. for

    int[] number = {1,2,3,5,8};
for (int i=0;i<number.length;i++) {
    System.out.println("第"+(i+1)+"个元素的值是："+number[i]);
}
    1
    2
    3
    4

    数组长度：number.length

  2. 增强for

    int[] number = {1,2,3,5,8};
for(int val:number) {
    System.out.print("元素的值依次是："+val+"\t");
}
    1
    2
    3
    4

# 多维数组

根据数组中存储数据之间逻辑结构的不同，数组可细分为一维数组、二维数组、...、n 维数组。以二维数组为例，来介绍多维数组的创建、访问和遍历。

在 Java (opens new window) 中二维数组被看作数组的数组，即二维数组为一个特殊的一维数组，其每个元素又是一个一维数组。Java 并不直接支持二维数组，但是允许定义数组元素是一维数组的一维数组，以达到同样的效果。

# 声明二维数组

声明二维数组的语法如下：

type arrayName[][];    // 数据类型 数组名[][];
1

或

type[][] arrayName;    // 数据类型[][] 数组名;
1

其中，type 表示二维数组的类型，arrayName 表示数组名称，第一个中括号表示行，第二个中括号表示列。

下面分别声明 int 类型和 char 类型的数组，代码如下：

int[][] age;
char[][] sex;
1
2

# 初始化二维数组

二维数组可以初始化，和一维数组一样，可以通过 3 种方式来指定元素的初始值。这 3 种方式的语法如下：

type[][] arrayName = new type[][]{值 1,值 2,值 3,…,值 n};    // 在定义时初始化
type[][] arrayName = new type[size1][size2];    // 给定空间，在赋值
type[][] arrayName = new type[size][];    // 数组第二维长度为空，可变化
1
2
3

使用第一种方式声明 int 类型的二维数组，然后初始化该二维数组。代码如下：

int[][] temp = new int[][]{{1,2},{3,4}};
1

上述代码创建了一个二行二列的二维数组 temp，并对数组中的元素进行了初始化。图 1 所示为该数组的内存结构。

img

使用第二种方式声明 int 类型的二维数组，然后初始化该二维数组。代码如下：

int[][] temp = new int[2][2];
1

使用第三种方式声明 int 类型的二维数组，并且初始化数组。代码如下：

int[][] temp = new int[2][];
1

# 访问单个元素

在上部分使用的前 2 种方式创建并初始化了一个二行二列的 int 类型数组 temp。当需要获取二维数组中元素的值时，也可以使用下标来表示。语法如下：

arrayName[i-1][j-1];
1

其中，arrayName 表示数组名称，i 表示数组的行数，j 表示数组的列数。例如，要获取第二行第二列元素的值，应该使用 temp[1]来表示。这是由于数组的下标

起始值为 0，因此行和列的下标需要减 1。

通过下标获取 class_score 数组中第二行第二列元素的值与第四行第一列元素的值。代码如下：

public static void main(String[] args) {
    double[][] class_score = {{10.0,99,99},{100,98,97},{100,100,99.5},{99.5,99,98.5}};
    System.out.println("第二行第二列元素的值："+class_score[1][1]);
    System.out.println("第四行第一列元素的值："+class_score[3][0]);
}
1
2
3
4
5

# 访问全部元素

在一维数组中直接使用数组的 length 属性获取数组元素的个数。而在二维数组中，直接使用 length 属性获取的是数组的行数，在指定的索引后加上 length（如

array[0].length）表示的是该行拥有多少个元素，即列数。

如果要获取二维数组中的全部元素，最简单、最常用的办法就是使用 for 语句。在一维数组全部输出时，我们使用一层 for 循环，而二维数组要想全部输出，则使

用嵌套 for 循环（2 层 for 循环）。

# 例 3

使用 for 循环语句遍历 double 类型的 class_score 数组的元素，并输出每一行每一列元素的值。代码如下：

public static void main(String[] args) {
    double[][] class_score = { { 100, 99, 99 }, { 100, 98, 97 }, { 100, 100, 99.5 }, { 99.5, 99, 98.5 } };
    for (int i = 0; i < class_score.length; i++) { // 遍历行
        for (int j = 0; j < class_score[i].length; j++) {
            System.out.println("class_score[" + i + "][" + j + "]=" + class_score[i][j]);
        }
    }
}
1
2
3
4
5
6
7
8

上述代码使用嵌套 for 循环语句输出二维数组。在输出二维数组时，第一个 for 循环语句表示以行进行循环，第二个 for 循环语句表示以列进行循环，这样就实现

了获取二维数组中每个元素的值的功能。

# 访问整行元素

除了获取单个元素和全部元素之外，还可以单独获取二维数组的某一行中所有元素的值，或者二维数组中某一列元素的值。获取指定行的元素时，需要将行数固

定，然后只遍历该行中的全部列即可。

public static void main(String[] args) {
    double[][] class_score = { { 100, 99, 99 }, { 100, 98, 97 }, { 100, 100, 99.5 }, { 99.5, 99, 98.5 } };
    Scanner scan = new Scanner(System.in);
    System.out.println("当前数组只有" + class_score.length + "行，您想查看第几行的元素？请输入：");
    int number = scan.nextInt();
    for (int j = 0; j < class_score[number - 1].length; j++) {
        System.out.println("第" + number + "行的第[" + j + "]个元素的值是：" + class_score[number - 1][j]);
    }
}
1
2
3
4
5
6
7
8
9

# 访问整列元素

获取指定列的元素与获取指定行的元素相似，保持列不变，遍历每一行的该列即可。

public static void main(String[] args) {
    double[][] class_score = { { 100, 99, 99 }, { 100, 98, 97 }, { 100, 100, 99.5 }, { 99.5, 99, 98.5 } };
    Scanner scan = new Scanner(System.in);
    System.out.println("您要获取哪一列的值？请输入：");
    int number = scan.nextInt();
    for (int i = 0; i < class_score.length; i++) {
        System.out.println("第 " + (i + 1) + " 行的第[" + number + "]个元素的值是" + class_score[i][number]);
    }
}
1
2
3
4
5
6
7
8
9

# Array类

java.util.Arrays 类能方便地操作数组，它提供的所有方法都是静态的。

具有以下功能：

  • 给数组赋值：通过 fill 方法。
  • 对数组排序：通过 sort 方法,按升序。
  • 比较数组：通过 equals 方法比较数组中元素值是否相等。
  • 查找数组元素：通过 binarySearch 方法能对排序好的数组进行二分查找法操作。

具体说明请查看下表：

序号 方法和说明
1 public static int binarySearch(Object[] a, Object key) 用二分查找算法在给定数组中搜索给定值的对象(Byte,Int,double等)。数组在调用前必须排序好的。如果查找值包含在数组中，则返回搜索键的索引；否则返回 (-(插入点) - 1)。
2 public static boolean equals(long[] a, long[] a2) 如果两个指定的 long 型数组彼此相等，则返回 true。如果两个数组包含相同数量的元素，并且两个数组中的所有相应元素对都是相等的，则认为这两个数组是相等的。换句话说，如果两个数组以相同顺序包含相同的元素，则两个数组是相等的。同样的方法适用于所有的其他基本数据类型（Byte，short，Int等）。
3 public static void fill(int[] a, int val) 将指定的 int 值分配给指定 int 型数组指定范围中的每个元素。同样的方法适用于所有的其他基本数据类型（Byte，short，Int等）。
4 public static void sort(Object[] a) 对指定对象数组根据其元素的自然顺序进行升序排列。同样的方法适用于所有的其他基本数据类型（Byte，short，Int等）。

# 链表

# 定义

链表（LinkedList）是由一组不必相连【不必相连：可以连续也可以不连续】的内存结构【节点】，按特定的顺序链接在一起的抽象数据类型。链表虽然是一种线性表，但是并不会按线性的顺序存储数据，使用的不是连续的内存空间来存储数据。

抽象数据类型（Abstract Data Type [ADT]）：表示数学中抽象出来的一些操作的集合。

链表具体体现为由一系列节点(node)组成，每个节点包括两部分内容：一个是存储数据元素自身的数据域，另一部分存储下一个节点地址的指针域。

img

链表中的节点

# 链表分类

常见的链表结构包括以下几种：

  • 单向链表

    单链表 单向链表只有一个方向，结点只有一个后继指针 next 指向后面的节点。因此，链表这种数据结构通常在物理内存上是不连续的。我们习惯性地把第一个结点叫作头结点，链表通常有一个不保存任何值的 head 节点(头结点)，通过头结点我们可以遍历整个链表。尾结点通常指向 null。

    单链表

  • 双向链表

    双向链表 包含两个指针，一个 prev 指向前一个节点，一个 next 指向后一个节点。

    双向链表

  • 循环链表

    循环链表 其实是一种特殊的单链表，和单链表不同的是循环链表的尾结点不是指向 null，而是指向链表的头结点。

    循环链表

  • 双向循环链表

    双向循环链表 最后一个节点的 next 指向 head，而 head 的 prev 指向最后一个节点，构成一个环。

    双向循环链表

# 链表特征

链表的数据结构有以下几点特征：

  1. 节点与节点通过地址进行链接。例如，多个人手拉手，每个人使用自己的右手拉住下个人的左手，依次类推，这样多个人就连在一起了。

    单链表结构

  2. 插入和删除节点快（复杂度为O(1)O(1)）

    • 增加元素：只需要修改连接下个元素的地址即可。

      增加结点

    • 删除元素：只需要修改连接下个元素的地址即可。

      删除结点

  3. 查找节点慢（复杂度O(n)O(n))：想查找某个元素，需要通过连接的节点，依次向后查找指定元素。

# Java自定义链表

  • 链表创建

    public class ListNode {
    int val;//数据
    ListNode next;//指针

    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}
    1
    2
    3
    4
    5
    6
    7
    8
    9

  • 链表遍历、节点插入、节点删除

    public class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }

    // 遍历链表
    public static void printLinkedList(ListNode listNode){
        while(listNode != null){
            System.out.println("node : " + listNode.val);
            listNode = listNode.next; // 节点向后移动
        }
        System.out.println();
    }

    // 插入节点
    public static void insertNode(ListNode listNode, int value, int insertValue){
        while(listNode != null){
            if(listNode.val == value){
                ListNode newNode = new ListNode(insertValue); // 创建新节点
                newNode.next = listNode.next; // 新节点的下一个节点指向
                listNode.next = newNode; // 插入新节点
                return;
            }
            listNode = listNode.next;
        }
    }

    // 删除节点(不包含首尾)
    public static void deleteNode(ListNode listNode, int i){
        while(listNode != null){
            if(listNode.val == i - 1){
                listNode.next = listNode.next.next;
                return;
            }
            listNode = listNode.next;
        }
    }

    public static void main(String[] args) {
        ListNode preNode = new ListNode(0); // 创建头节点(预先节点)
        ListNode curNode; // 声明一个中间变量用来在移动过程中指向当前节点
        curNode = preNode; // 指向头节点
        
        // 创建链表
        for(int i = 1; i < 10 ; i ++) {
            ListNode node = new ListNode(i); // 创建新的节点
            curNode.next = node; // 当前节点下一个指向新节点
            curNode = curNode.next; // 节点向后移动
        }
        
        curNode = preNode;
        // 遍历链表
        printLinkedList(curNode);
        // 链表指定节点插入
        insertNode(curNode, 9, 99);
        printLinkedList(curNode);
        // 链表指定节点删除
        deleteNode(curNode, 3);
        printLinkedList(curNode);
    }
}
    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

# 数组 VS 链表

  • 数组支持随机访问，而链表不支持。
  • 数组使用的是连续内存空间对 CPU 的缓存机制友好，链表则相反。
  • 数组的大小固定，而链表则天然支持动态扩容。如果声明的数组过小，需要另外申请一个更大的内存空间存放数组元素，然后将原数组拷贝进去，这个操作是比较耗时的！

# 参考

  • 数组：http://data.biancheng.net/view/181.html
  • Java数组：http://c.biancheng.net/view/5852.html
  • Java数组：https://www.runoob.com/java/java-array.html
  • 链表：http://data.biancheng.net/view/160.html
  • 链表：https://javaguide.cn/cs-basics/data-structure/linear-data-structure.html
  • Java自定义链表：https://www.cnblogs.com/chenfx/p/14288066.html
Last Updated: 11/22/2022, 10:02:55 PM

树