心安

数据结构(一)-- 数组和链表

字数统计: 3k阅读时长: 11 min
2018/12/20 Share

前言

在进入本系列文章之前,我们先明确几个概念。可能很多同学不太理解,为什么要学数据结构?为什么面试一定会问数据结构?平时写代码的时候感觉也没用过数据结构啊,数据结构到底重要在哪儿呢?首先,我可以很明确、很负责任的说,数据结构非常非常重要,百分之99的Java面试都会问到,不问数据结构只能说明面试官是个棒槌(不一定直接问,而是通过其他问题引出来)。

那么,第一个问题,数据结构是什么?百度百科传送门。我个人不是很喜欢特别官方的说法,感觉简单的问题说的太深奥,太高大上,看不懂。所以这里我还是说说自己对于数据结构的理解。我个人的理解就是,数据结构其实就是数据在计算机中的存储方式。我们所有看到的、听到的都是数据,那么这些数据应该以何种方式存储在计算机中,如何让我们高效的使用这些数据,这就是数据结构解决的问题。

举个简单的例子,我们知道在Java的集合类中,有ArrayList和LinkedList,Java基础比较不错的同学肯定马上就明白这个类的区别了。不清楚的也没有关系,本文后面会讲到这两种经典的数据结构。这里我先告诉大家,ArrayList对于查询操作,速度会优于LinkedList,而对于插入操作LinkedList却优于ArrayList。现在我们有一个需求,选用一个类来存储一个班级里面的所有同学的联系方式以供查询,聪明的同学肯定马上回答,肯定选择ArrayList,查询速度快嘛。答案是正确的,因为我们不太需要插入操作,更多的是查询操作,所以选择查询速度较快的ArrayList。

通过这个简单的例子我们就知道数据结构的重要性。试想一下,如果不了解数据结构,选择了错误的数据结构存储了一个word文档,结果打开这个文档竟然花费了5分钟,这是一件多么可怕的事情啊。同样的,设计合理的数据结构来让我们的数据更加高效、快速的存储和传输,对于我们程序设计者来说,简直太重要了。ok,一顿哔哔这么多,很多同学已经很烦了,赶紧进入正题开始搞事情吧。

数组

  • 数组的特点

有程序设计基础的同学相信都很熟悉数组这个名词了,几乎所有的程序语言都会有这种数据结构。那么数组是什么呢?它其实就是用来存储多个相同数据类型的数据的集合。

数组的特点:数组是在内存中开辟的一块连续的空间,数据存储是有序的,数组带有索引,并且索引值从0开始,数组的长度是不可变的。我们可以通过数组名[索引值]来访问数组中的元素,由于存在索引,所以数组的查询速度较快。

  • 为什么数组这么快

很多资料上面都这么说,但是却没有被解释为什么。这里我解释一下,我们要查询(访问)一个元素,就需要知道这个元素在内存中的位置,也就是内存地址,那么我们现在有一个数组,我们知道数组的内存地址(数组的索引中记录的就是数组的内存地址起始位置,这里描述的不准确,只是为了读者方便理解),我们也可以通过数组元素的类型很容易知道每个元素的长度,那么每个元素的内存地址我们就可以通过数组起始地址加上该元素在数组中的位置乘以数组元素的长度来确定。如下:

上面的只是为了更好的和读者说明数组查询速度快的原理,与数组实际在内存中的存储可能有些出入,但是不妨碍大家理解。

  • 数组插入元素

    对容器的操作一共四种:增、删、改、查。上面我们说了数组的查询速度很快,并且讲述了其原理。下面我们看一下数组元素的插入。往数组中间插入一个新元素,如果要插入的位置上面已经有元素了就需要将后面的元素往后面移动一位,然后插入,同时,由于要插入新元素,所以原本的数组容量不再满足需求,所以需要创建新数组,把数据复制过去,然后插入新元素。如下图:

    我们会发现数组的插入会受到插入的位置的影响。

    如果插入到数组的最后一个位置,那么只需要扩容然后插入即可,如果不考虑扩容的时间复杂度,那么插入到数组尾部的时间复杂度是O(1);

    但是如果插入到数组头位置,就需要将整个数组的元素都往后移动一遍;同样不考虑扩容的时间复杂度,那么插入到数组头部的时间复杂度是O(n);

    那么我们计算平均时间复杂度就是O(n/2) = O(n)。所以,结论就是数组插入元素到指定位置的时间复杂度是O(n),这个时间复杂度是比较差的。

ArrayList

前面说了数组,发现数组最大的弊端就是数组的长度是不可变的,也就是当我们声明了一个长度为L的数组,这个数组的长度就不能再变化了。那么如果说我们的数据量大于数组长度的时候,这个数组就不再满足我们的需求了。Java在1.0版本就提供了一种“动态数组”,Vector,顾名思义就是长度可以自由变化的数组。但是由于这个类是线程安全的,效率相对较低,所以在Java1.2版本又推出了我们的主角ArrayList。ArrayList和Vector的主要区别就是ArrayList是线程不同步的,所以效率更高,也就逐渐取代了Vector。那么我们着重看一下这个ArrayList,看一下它是如何做到长度可以自由变化的。

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
transient Object[] elementData;

// 添加一个元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}

private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}

上面是ArrayList类的部分源码,首先有一个成员变量Object[] elementData,它就是用来装载元素的数组,之所以定义成Object类型是为了支持泛型,这里我们暂时不关注这个。

我们看到当添加元素的时候,也就是调用了add(E e)方法,它先是调用了ensureCapacityInternal(int minCapacity),传入的参数是原本数组的size + 1,也就是添加新元素之后数组的size。接着调用ensureExplicitCapacity(int minCapacity),在这里有一行if (minCapacity - elementData.length > 0)代码,这一行就是当添加了一个元素之后的数据量大于数组的size要执行的操作,也就是说现在这个数组装不下了,那么就调用grow(int minCapacity)方法,我们着重看一看这个方法。

这个方法第一行是保存了目前数组的长度,然后声明了一个新的变量newCapacity,新变量的值就等于原来数组长度 + 原数组长度右移一位,其实新数组长度等于原数组长度 * 1.5,不了解位运算的同学自行百度。下面还是几句代码还是操作这个新容量newCapacity,没有太多需要解释的,无非是处理一下容量的边界问题。最后一句代码是将原本数组中的元素复制到新数组中。

通过上面的分析,相信各位同学不难发现,其实ArrayList实现动态长度的原理无非是当发现数组满了,就扩容,通过源码发现,每次扩容到原来的1.5倍,然后建立新的数组,最后把旧数组中的数据复制到新数组中

线程安全:指某个函数、函数库在并发环境中被调用时,能够正确地处理多个线程之间的共享变量,使程序功能正确完成。即在多线程场景下,不发生有序性、原子性以及可见性问题。

链表

上面讲到数组是在内存中开辟的一块连续的空间来存储数据的,数据是有序的,而链表和数组则不同,链表是在内存中不连续的。链表是一个节点一个节点连接起来组成的线性结构,每个节点里面一部分存储了数据值,一部分存储了下一个节点的位置的“指针”。当然更复杂的还有双向链表,不仅存储了下一个节点的指针还存储了上一个节点的指针。单向链表在内存中的示意图如下:

那么看一下最简单的实现思路,实现一个 Node 类来表示每个节点,代码比较简单,就不过多解释了,看懂这个最基础版的再去看 Java 实现的会轻松很多:

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
public class LinkedList<E> {

class Node {

Node next;

E e;

Node(Node next, E e) {
this.next = next;
this.e = e;
}

Node(E e) {
this(null, e);
}

Node() {
this(null, null);
}

@Override
public String toString() {
return e.toString();
}
}

private Node head;

private int size;

public int size() {
return this.size;
}

public boolean isEmpty() {
return size == 0;
}

/**
* 在 index 位置插入元素 e
*
* @param e 新插入的元素
* @param index 要插入的位置
*/
public void add(E e, int index) {
checkIndex(index);
// 定义一个前置指针指向头结点,循环结束后这个指针将会指向 index - 1 位置
Node preNode = this.head;
for (int i = 0; i < index; i++) {
preNode = preNode.next;
}
// 找到 index 位置的元素
// Node next = preNode.next;

// 通过元素 e 来构建新节点,并且让这个节点指向 index 位置的元素
// Node newNode = new Node(next, e);

// 让 index - 1 位置的元素的 next 指向新元素
// preNode.next = newNode;
// 下面这行代码是上面三行的简写
preNode.next = new Node(preNode.next, e);
size++;
}

/**
* 查询指定位置的元素,修改指定位置的元素和此方法一致
*
* @param index 要查询的元素的索引
* @return 节点的元素
*/
public E get(int index) {
checkIndex(index);
Node current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current.e;
}

/**
* 移除指定索引位置的节点,并且返回节点的元素
*
* @param index 要删除的节点的索引值
* @return 被删除的节点的元素
*/
public E remove(int index) {
checkIndex(index);
Node preNode = head;
for (int i = 0; i < index; i++) {
preNode = preNode.next;
}
// 循环结束 preNode 指向 index - 1 位置
// preNode 的下一个元素就是目标元素
Node targetNode = preNode.next;
// 让 index - 1 位置的元素指向 index + 1 位置的元素
preNode.next = targetNode.next;
targetNode.next = null;
return targetNode.e;
}

private void checkIndex(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("错误的索引值.");
}
}
}

笔者偷个懒,不画插入和删除节点的图示了,网上很容易就能找到,结合代码也能看得懂。

原文作者:XinAnzzZ

原文链接:https://www.yuhangma.com/2018/algorithm/2018-12-20-data-structure-linkedList/

发表日期:December 20th 2018, 12:00:00 am

更新日期:February 2nd 2021, 4:44:20 pm

版权声明:(转载本站文章请注明作者和出处 心 安 – XinAnzzZ ,请勿用于任何商业用途)

CATALOG
  1. 1. 前言
  2. 2. 数组
  3. 3. ArrayList
  4. 4. 链表