Java面向对象基础知识之数组和链表

1. 数组和链表区别

数组和链表都是线性数据结构，但它们的存储方式和特点不同。

• 数组是一种连续的内存存储方式，可以快速访问任何一个元素。但在插入和删除元素时，需要移动大量元素，效率很低，因此不适合插入和删除操作频繁的情况。
• 链表是一种非连续的内存存储方式，每个元素存储了下一个元素的地址，因此可以快速插入和删除元素。但访问指定位置的元素时需要遍历链表，效率较低。

2. 数组

2.1 定义和初始化数组

使用数组需要先定义一个数组变量，再初始化数组。 定义方式如下：

// 定义一个int类型的数组，长度为10
int[] arr = new int[10]; 

数组初始化有两种方式：

• 静态初始化：定义数组时赋初值
• 动态初始化：定义数组后再逐个赋值

静态初始化方式如下：

int[] arr1 = {1,2,3,4,5};

动态初始化方式如下：

int[] arr2 = new int[5];
arr2[0] = 1;
arr2[1] = 2;
arr2[2] = 3;
arr2[3] = 4;
arr2[4] = 5;

2.2 数组遍历

使用for循环遍历数组。

for(int i=0; i<arr.length; i++){
    System.out.println(arr[i]);
}

2.3 数组排序

可以使用Arrays类中提供的sort方法对数组进行排序。如下所示：

Arrays.sort(arr);

3. 链表

3.1 定义链表

链表由多个节点组成，节点包括两部分内容：数据域和指针域。数据域存储节点的值，指针域存储下一个节点的地址。

定义链表时需要先定义节点类，然后使用节点类定义链表。

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

ListNode node1 = new ListNode(1);
ListNode node2 = new ListNode(2);
ListNode node3 = new ListNode(3);

node1.next = node2;
node2.next = node3;

3.2 链表遍历

使用while循环遍历链表。

ListNode node = head; // head是链表的头节点
while(node != null){
    System.out.println(node.val);
    node = node.next;
}

3.3 在链表尾部添加节点

首先需要找到链表的尾节点，然后将尾节点的next指针指向新节点。如下：

ListNode tail = head;
while(tail.next != null){
    tail = tail.next;
}
tail.next = new ListNode(val);

4. 示例

4.1 数组示例

下面是一个数组排序的示例。

import java.util.Arrays;

public class ArrayExample {
    public static void main(String[] args) {
        int[] arr = {3,5,1,4,2};
        Arrays.sort(arr);  //排序
        for(int i=0; i<arr.length; i++) {
            System.out.println(arr[i]);  //遍历输出
        }
    }
}

4.2 链表示例

下面是一个在链表尾部添加节点的示例。

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class LinkedListExample {
    public static void main(String[] args) {
        ListNode head = new ListNode(1); //定义链表头节点
        ListNode tail = head;
        for(int i=2;i<=5;i++){ //循环添加节点
            tail.next = new ListNode(i);
            tail = tail.next;
        }
        ListNode node = head; //遍历链表
        while(node != null){
            System.out.println(node.val);
            node = node.next;
        }
    }
}

5. 总结

本文介绍了数组和链表的区别、定义和初始化、遍历、排序、以及链表添加节点等基本操作。在实际的开发中，应根据具体需求选择合适的数据结构。