数据结构Java实现02--数组、链表和动态数组_java 数组和链表

2.数组和链表

2.1 数组

数组 Array 是一种线性数据结构，其将相同类型元素存储在连续的内存空间中。我们将元素在数组中的位置称为元素的索引 index。

数组初始化。一种给定初始值，称为静态初始化。

/*以下两种方式均可静态初始化*/
int[] nums = new int[]{1,2,3,4,5};
int[] nums = {1,2,3,4,5};
1
2
3

一种不给定初始值，称为动态初始化。

//需要给定数组的长度
int[] arr = new int[5];
1
2

可以发现， 两种初始化方式都需要确定数组的长度，且不可改变。

2.1.1 数组的优点

**数组随机访问元素非常高效。**由于数组元素被存储在连续的内存空间中，因此计算数组元素的内存地址非常容易，给定数组首个元素的地址和某个元素的索引，可得到以下公式：

$元素内存地址=数组内存地址+元素长度\times 元素索引$

我们可以在 O（1）时间内随机获取数组中的任意一个元素。

int[] nums = new int[]{1,2,3,4,5};
int number = nums[2];
System.out.println(number);
1
2
3

2.1.2 数组缺点

**数组在初始化后长度不可变。**如果需要扩容数组，则需要新建一个数组，然后把原数组元素依次复制到新数组，在数组很大的情况下，非常耗时。

int[] extend(int[] nums, int enlarge) {
    // 初始化一个扩展长度后的数组
    int[] res = new int[nums.length + enlarge];
    // 将原数组中的所有元素复制到新数组
    for (int i = 0; i < nums.length; i++) {
        res[i] = nums[i];
    }
    // 返回扩展后的新数组
    return res;
}
1
2
3
4
5
6
7
8
9
10

**数组中插入或删除元素效率低。**如果我们想要在数组中间插入一个元素，由于数组元素在内存中是“紧挨着的”，它们之间没有空间放任何数据。因此，我们不得不将此索引之后的所有元素都向后移动一位，然后再把元素赋值给该索引。

void insert(int[] nums,int num,int index){
    Arrays.copyof(nums,
    for(int i=nums.length-1;i>
1
2
3

当数据比较大时，创建数组需要一块连续的比较大的空间。而实际情况中空闲内存空间往往散落各处，因此不能很好地利用内存资源。

使用链表可以避免这一点。

2.1.3 数组常用操作

数组遍历

    void travelse(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i]);
        }
    }
1
2
3
4
5

数组查找

注意，以下代码为遍历方式的查找，最坏情况时间复杂度为O(n)。

如果是有序数组，可以通过二分查找进行优化，优化后的时间复杂度为O(logn)。

int find(int[] nums, int target){
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] == target){
                return i;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8

2.2 链表

与数组相比，链表更具灵活性，它可以被存储在非连续的内存空间中。

链表LinkerList是一种线性数据结构，其每个元素都是一个节点对象，各个节点之间通过指针连接，从当前节点通过指针可以访问到下一个节点。指针中记录了下个节点地内存地址，所以无需保存内存地址的连续性。

链表的节点Node包含两项数据，1是节点的值Value，2是指向下一节点的指针Pointer。

尾节点没有下一个节点，所以Pointer指向null。

//创建NodeList类，包含value、next属性和构造函数
class NodeList {
    private int value;
    private NodeList next;
    NodeList(int value){
        this.value = value;
    }
//此处省略setter和getter
}
1
2
3
4
5
6
7
8
9

**链表初始化方法。**建立链表分为两步，第1步是初始化各个节点对象，第2步是构建引用关系，可以从链表的头节点出发，通过指针next依次访问所有节点。

class NodeListTest{
    public static void main(String[] args) {
        NodeList n1 = new NodeList(1);
        NodeList n2 = new NodeList(2);
        NodeList n3 = new NodeList(3);
        NodeList n4 = new NodeList(4);
        NodeList n5 = new NodeList(5);
        n1.setNext(n2);
        n2.setNext(n3);
        n3.setNext(n4);
        n4.setNext(n5);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.2.1 链表优点

**链表中插入与删除节点的操作效率高。**假如链表中间的两个节点A、B之间插入一个新节点C，我们只需改变节点指针即可。

C.next = B;
A.next = C;
1
2

该操作的时间复杂度为O(1)，对比数组添加元素的时间复杂度为O(n)，效率高很多。

如果是删除节点，只需将前一个节点的指针指向下一个，要删除的指针next置为null，复杂度也为O(1)。

2.2.2 链表缺点

**链表随机访问效率低。**链表在随机访问时需要从头节点出发，逐个向后遍历直至找到目标节点。

 NodeList access(NodeList head, int index){
        if(head == null) return null;
        for (int i = 0; i < index; i++) {
            head = head.next;
        }
        return head;
    }
1
2
3
4
5
6
7

**链表内存占用大。**链表中的每个节点除了保存值之外，还需要保存指针。

2.2.3 链表操作

遍历链表查找。

int find(NodeList head, int target) {
        int index = 0;
        while (head != null) {
            if (head.value == target)
                return index;
            head = head.next;
            index++;
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10

2.2.4 常见链表类型

**单向链表。**单向链表的节点包含值和指向下一节点的指针两项。首个节点称为头节点，最后一个节点成为尾节点，尾节点指向None 。

环形链表。如果我们令单向链表的尾节点指向头节点（即首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。

双向链表。与单向链表相比，双向链表记录了两个方向的指针。双向链表的节点定义同时包含指向后继节点和前驱节点的指针。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但需要占用更多的内存空间。

2.3 动态数组

使用数组时，如果我们无法事先确定数据量，数组长度过小会导致频繁扩容数组，长度过大会导致内存空间浪费。所以可以使用动态数组来解决此问题。在Java中有专门的实现类ArrayList。

2.3.1 动态数组实现

在这里我们会对ArrayList进行简单的实现。

//继承Iterable为了实现迭代器遍历
public class MyArrayList implements Iterable<Integer>{
    //内部的数组
    private int[] data;
    //初始容量
    private int initCapacity;
    //大小，即现有的元素个数
    private int size;
    //无参构造方法，初始容量为10
    public MyArrayList() {
        data = new int[0];
        initCapacity = 10;
    }
    //有参构造方法，需要传入一个初始容量
    public MyArrayList(int initCapacity) {
        data = new int[initCapacity];
        this.initCapacity = initCapacity;
    }
  
    //动态数组添加元素
    public void add(int value) {
        ensureCapacity(); //确认数组容量,容量不足需要扩容
        data[size++] = value;
    }
    //动态数组扩容
    private void ensureCapacity() {
        if (data.length == 0) {
            this.data = new int[initCapacity];
            return;
        }
        if (data.length == size) {
            int newLen = (int) ceil(data.length * 1.5);
            int[] newData = new int[newLen];
            data = Arrays.copyOf(data, newLen);
        }
    }
    //动态数组访问元素
    public int get(int index) {
        if (index >= size || index < 0) {
            throw new IndexOutOfBoundsException("哎呀，越界啦");
        }
        return data[index];

    }

    public int size() {
        return size;
    }

    //动态数组修改元素
    public void set(int index, int value) {
        if (index >= size || index < 0) {
            throw new IndexOutOfBoundsException("哎呀，越界啦");
        }
        this.data[index] = value;
    }
    //动态数组删除元素
    public void remove(int index) {
        if (index >= size || index < 0) {
            throw new IndexOutOfBoundsException("哎呀，越界啦");
        }
        System.arraycopy(data,index+1,data,index,size-index-1);
        size--;
    }

    //通过迭代器实现遍历
    @Override
    public Iterator<Integer> iterator() {
        //返回一个Iterator的匿名内部类
        return new Iterator<Integer>() {
            int index = 0;
            @Override
            public boolean hasNext() {
                return index < size;
            }

            @Override
            public Integer next() {
                return data[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
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

2.3.2 动态数组常用操作

**初始化列表。**分为有初始值和无初始值两种初始化方法。 在Java源码的ArrayList实现中，默认初始容量为10，如果数组满了，每次扩容1.5倍。

访问与更新元素。

//参考上面的列表实现代码
list.get(index);
list.set(index,value);
1
2
3

添加、删除元素。

//自动添加到数组末尾
list.add(value);
list.remove(index);
1
2
3

遍历列表。

 for(Integer v : list){
            System.out.print(v+" ");
}
1
2
3

2.4 总结

• 数组支持随机访问、占用内存较少；但插入和删除元素效率低，且初始化后长度不可变。
• 链表通过更改指针实现高效的节点插入与删除，且可以灵活调整长度；但节点访问效率低、占用内存较多。常见的链表类型包括单向链表、循环链表、双向链表。
• 动态数组，又称列表，是基于数组实现的一种数据结构。它保留了数组的优势，同时可以灵活调整长度。列表的出现极大地提高了数组的易用性，但可能导致部分内存空间浪费。

创作声明：本文参考《算法第4版》和Hello算法写作，大部分内容基于Hello算法教程，修改了数据结构的描述和部分Java代码，如有侵权问题，请联系作者。