数据结构（一）：数组和链表

发表于 | 分类于 |
字数统计: 2k | 阅读时长 ≈ 7

数据结构是数据的组织、管理和存储格式，其使用目的是为了高效地访问和修改数据。

数组和链表属于线性结构，是最简单的数据结构。

数组

数组是有限个相同类型的变量所组成的有序集合。

数组中的每一个变量称为元素。数组是最常用，最简单的数据结构。

我们知道，内存是由一个个连续的内存单元组成，每一个内存单元都有自己的内存地址。

数组中的每一个元素，都储存在内存单元中，并且元素之间紧密排列，既不打乱元素的存储顺序，也不能跳过某个存储单元进行存储。这就是数组的顺序储存特点。可以借此很好地实现逻辑上的顺序表。

读取元素

对于数组，读取是最简单的操作。由于它是顺序存储，所以只要给出数组下标，即可读取到相对应的数组元素。这种根据下标读取元素的方式称为随机读取。

1
2
3
int array[] = new int[]{3,1,2,5,4,9,7,2};
//输出数组中下标为3的元素
System.out.println(array[3]);

修改元素

同理，修改数组中的某一元素，也可以直接利用下标实现。

1
2
3
int array[] = new int[]{3,1,2,5,4,9,7,2};
//修改数组下标为5的元素
array[5] = 10;

插入元素

插入元素有以下三种情况：

  1. 尾部插入
  2. 中间插入
  3. 超范围插入

尾部插入，是最简单的情况，直接把插入的元素放在数组尾部的空闲位置即可。等同于跟修改元素的操作。

中间插入，需要先把插入位置及后面的元素向后移动，腾出一个空位，再把要插入的元素放到对应的数组位置上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//数组实际元素的数量
int size = 8;

//数组插入
public void insert(int element, int index) throws Excepiton{
    //判断下标是否超出范围
    if (index < 0 || index > size){
        throw new IndexOutBoundsException("超出数组实际元素范围");
    }
    //腾出空位
    for(int i=size-1; i>=index; i--){
        array[i+1] = array[i]; 
    }
    //在空位上放入新元素
    array[index] = element;
    size++;
}

超范围插入，是指在装满了元素的数组中继续进行插入。这样首先要进行数组的扩容。数组的长度是在创建时就固定的，所以只能创建一个新的数组，长度是旧数组的2倍，再把旧数组中的元素全部复制过来。

我们对上面的代码继续进行补充，添加数组扩容的resize()方法。

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
//数组实际元素的数量
int size = 8;

//数组插入
public void insert(int element, int index) throws Excepiton{
    //判断下标是否超出范围
    if (index < 0 || index > size){
        throw new IndexOutBoundsException("超出数组实际元素范围!");
    }
    //实际元素达到数组容量上限
    if(size >= array.length){
        resize();
    }
    //腾出空位
    for(int i=size-1; i>=index; i--){
        array[i+1] = array[i]; 
    }
    //在空位上放入新元素
    array[index] = element;
    size++;
}

//数组扩容
public void resize(){
    int[] arrayNew = new int[array.length*2];
    System.arraycopy(array, 0, arrayNew, 0, array.length);
    array = arrayNew;
}

删除元素

数组的删除操作与插入操作相反，不过不用考虑扩容问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//数组实际元素的数量
int size = 8;

//数组删除
public int delete(int index) throws Excepiton{
    //判断下标是否超出范围
    if (index < 0 || index > size){
        throw new IndexOutBoundsException("超出数组实际元素范围!");
    }
    int deleteElement = array[index];
    //元素逐个左移
    for(int i=index; i<size-1; i++){
        array[i] = array[i+1]; 
    }
    size--;
    return deleteElement;
}

链表

链表是一种物理上非连续、非顺序的数据结构。由若干节点所组成。

单向链表的每个节点包含两部分，一部分存放数据的变量data，另一部分指向下个节点的指针next。

1
2
3
4
private static class Node {
    int data;
    Node next;
}

链表的第一个节点称为头节点，最后一个节点称为尾节点。尾节点的next指针指向空。

双向链表的节点除了拥有data和next指针，还拥有指向前置节点的prev指针。

1
2
3
4
5
private static class Node {
    int data;
    Node next;
    Node prev;
}

查找节点

链表无法像数组一样通过下标快速定位，只能从头节点向后逐个查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//链接实际节点的数量
private int size;
//头节点指针
private Node head;
//尾节点指针
private Node last;

//链表查找
public Node get(int index) throws Exception {
    if(index<0 || index>=size){
        throw new IndexOutOfBoundsException("超出链表节点范围！");
    }
    Node temp = head;
    for(int i=0; i<index; i++){
        temp = temp.next;
    }
    return temp;
}

修改节点

修改节点需要先按照上面的查找方法，找出节点，然后直接更新即可。

插入节点

只要内存空间允许，链表能够插入的节点是无穷的，所以不需要考虑扩容的问题。插入节点分为以下三种情况：

  1. 头部插入
  2. 尾部插入
  3. 中间插入

头部插入：先把新节点的next指针指向原先的头节点，再把新节点变为链表的头节点。

尾部插入：先把尾节点的next指针指向新的节点，再把新节点变为链表的尾节点。

中间插入：先把插入位置的前置节点的next指针指向插入的新节点，再将新节点的next指针指向前置节点的next指针原先所指向的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//链表插入
public void insert(int data, int index) throws Exception {
    if(index<0 || index>size) {
        throw new IndexOutOfBoundsException("超出链表节点范围！");
    }
    Node insertedNode = new Node(data);
    if(index == 0){
        //头部插入
        insertedNode.next = head;
        head = insertedNode;
    }else if(index == size){
        //尾部插入
        last.next = insertedNode;
        last = insertedNode;
    }else{
        //中间插入
        Node prevNode = get(index-1);
        Node nextNode = prevNode.next;
        prevNode.next = insertedNode;
        insertedNode.next = nextNode;
    }
    size++;
}

删除节点

在许多高级语言中，如java，拥有自动垃圾回收机制。这时不用刻意释放被删除的节点，只要没有外部引用指向它们，被删除的节点会被自动回收。删除节点同样分为以下三种情况：

  1. 头部删除
  2. 尾部删除
  3. 中间删除

头部删除：把链表的头节点设为原先头节点的next指针。

尾部删除：把倒数第二个节点的next指针指向空。

中间删除：把要删除节点的前置节点的next指针，指向要删除节点的next指针。

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
//链表删除
public Node remove(int index) throws Exception{
    if(index<0 || index>=size){
        throw new IndexOutOfBoundsException("超出链表节点范围！");
    }
    Node removedNode = null;
    if(Node == 0){
        //头部删除
        removedNode = head;
        head = head.next;
    }else if(index == size-1){
        //尾部删除
        Node prevNode = get(index-1);
        removedNode = last;
        prevNode.next = null;
        last = preNode;
    }else{
        //中间删除
        Node prevNode = get(index-1);
        removedNode = prevNode.next;
        Node nextNode = removedNode.next;
        prevNode.next = nextNode;
    }
    size--;
    return removedNode;
}

总结

数组和链表都属于线性的数据结构，它们相关操作的性能总结如下表。

数据结构 查找 修改 插入 删除
数组 O(1) O(1) O(n) O(n)
链表 O(n) O(1) O(1) O(1)

数组拥有非常高的随机访问能力，只要给出下标，就可以用常量时间找到对应元素。二分查找就是利用了数组这个特性。相应的，在插入和删除元素时，数组元素需要逐个移动，效率就会比较差。

而链表能够灵活地进行插入和删除操作，在查找时的效率会比较差。

所以，数组适合的是读操作多，写操作少的场景。链表适合的是写操作多，读操作少的场景。

Chen wechat
欢迎扫描二维码，订阅我的博客公众号MiracleChen