数据结构

数据结构表（ADT）解析(上)

1、前言

自工作以来，越来越觉得数据结构的重要性，类似于网络上面拉去下来的数据进行分类，还是自定义View画图的x，y还是滑动的距离。滑动距离的判断种种。感觉自己很是欠缺火候，所以开始恶补数据结构、算法的知识，让自己可以提高。

之前在知乎上面看了一个帖子，在讨论数据结构的重要性，有一句话说的很好，也是笔者开始写一系列数据结构算法的动力，在这里送给给位看客，

  • 对于一个程序员来说，算法的高度决定程序员的高度，而一个程序员将来成就的高度取决于算法的高度

看完以后热情满满，打算从最基本的开始学习，如果各位看客发现在什么地方说的不对，希望指出。谢谢各位。

2、抽象数据类型（ADT）

学习数据结构之前，我们需要明白什么是抽象数据类型，

抽象数据类型（abstract data type）:是带有一组操作的一些对象的集合，抽象数据类型是数学方面的抽象。在抽象数据类型定义中没有地方提到关于这组操作时如何实现的任何解释。这里有两个比较重要的地方，首先第一个是一组操作。然后是一些对象的集合，

在这里笔者的理解是有一个装篮球的箱子，箱子上面有各种各样的按钮，每一个按钮都可以操作箱子里面篮球，比如让箱子将所有的篮球全部吐出来，等等，这里这个装篮球的箱子以及里面的篮球和按钮就是抽象数据类型。

常见的抽象数据类型有表、栈、队列、树、图、散列 等，将在后面篇章详细讨论，这里只对表进行说明。

3、表（ADT）

3.1 表当中的元素

我们将处理 $A_{0}$、 $A_{1}$、 $A_{2}$、 $A_{3}$、 $A_{4}$、····· $A_{N-1}$的一般的表。我们就说这个表的长度是N。我们将长度为0的表叫做空表（empty list）

对于一个不为空的表，我们说 $A_{i}$后继 $A_{i-1}$（i < N, i > 0）并且$A_{i-1}$ 前驱 $A_{i}$。$A_{0}$为表当中的第一个元素，没有前驱元，而$A_{N-1}$为表当中的最后一个元素，没有后继元。

3.2 表当中的操作

对于每种ADT并不存在什么固定的操作，而为每种ADT提供合理的操作，一般取决于程序的设计者。对于表这种ADT，笔者在这里提出比较常用的操作。为 ：

1
2
3
4
5
6
7
8
9
10
11
12
printList : 按照表的顺序打印各个位置的对象，如是对象打印地址。
makeEmpty : 将该表置空

find : 返回某一项第一次返回的位置。
findValueForIndex : 通过index查找value 
findIndexForValue : 通过value查找index

insert : 在表的末尾插入
insertForIndex : 在指定位置插入

remove : 通过value删除元素
remmoveForIndex : 通过index删除元素

4、表的实现

4.1、数组实现简单的表。

我们把通过数组实现的表接口叫做顺序表。顺序表的所有操作都可以通过使用数组来实现，但是这里会涉及到一个问题就是，就是数组应该是固定长度的，我们的表应该让上层用户感觉不到容量，及当用户想要去添加的时候，我们可以让用户无限添加。这就是数组实现表里面的一个通用问题，这里的解决方式是让数组扩容，什么是扩容呢？ 就是通过大于旧数组的长度去定义一个新的数组，然后把旧的数组里面的所有元素全部拷贝到新数组。

关于新数组的长度应该是多少呢？笔者在这里给出

  • 新数组长度 = 旧数组的长度 +（ 旧数组的长度 * 2）
1
2
3
4
5
6
7
8
9
10
11
12
13
int [] arr = new int[10];
···
···
//开始扩容
int newSize = arr.length + ( arr.length * 2 );
int[] newArray = new int[newSize];

//扩容完成，下面开始拷贝
for(int k = 0; k < arr.length; k++){
	newArray[k] = arr[k]
}
//归还引用
arr = newArray ;

这种数据结构的优点在于，查找，基本消耗的时间都是线性时间，而上述提供的findValueForIndex操作，常数时间就可以很轻松的完成。

缺点就是，如果我们需要对顺序表当中的表结构（数据）进行改变呢？我们不妨设想一下，如果我们需要在第2位插入一个元素，那么就代表着，表里面的原先2位置的元素下表变化称为第3，而第3变为第4，以此类推，直到表中元素结束。删除也是同样的道理。当然如果我们在最后一位插入，我们的时间也是常数值。在这里我们考虑最坏情况，那就是在第一位插入活着删除，那么我们的时间就是$o(N)$。

总结：就是如果对于该表数据为只读权限（完全访问），而没有写权限，那么这种表结构的实现无一就是完美的，但是对插入删除操作比较多的话。笔者在这里不推荐使用这种表，而推荐下述的这种表结构（链表），后续会比较两表的效率问题，

4.2、简单链表

为了解决上述问题，人们开始思考，如果我们将表不进行连续存储，可以避免插入和删除的线性开销，下图为链表的一般想法

简单链表

上图可知，链表是一系列节点组成的，我们称之为Node，这些Node在内存当中是不连续的。每一个Node都有一条链，我们称之为next链，直向下一个Node，最后一个元素的next链为空。

我们如果打印全部，或者便利的话，通过第一个元素找到第二个元素以此类推，直到找到最后一个元素。时间是线性的，这个数组实现是一样的，不过其中的常数可能会比使用数组要大，findValueForIndex操作确实没有数组效率高，需要通过第一个开始找，直到遍历到index，所以时间复杂度为 $O(i)$ 。

如果是删除和插入操作，我们只需要修改两个链也就是引用，我们就可以完成插入操作和删除操作，不需要移动项，所以对比上述数组实现确实是简便了一些。下图为删除和插入的实现链表

简单链表

这里如果要插入的话，就把A3指向A4的引用变为A3指向x，然后把x的指向变为A4即可。不需要移动项，所以在这里时间复杂度是常数时间。

简单链表

如果要删除A4节点的话，这里我们直接把A3的链指向A5，然后把A4原本指向A5的链制空。就完成了A4的删除。时间复杂度也是常数时间。

使用上述链表的话，删除最后一个节点，我们得先找到指向最后一个节点的项，但是在上述链表当中，每一个节点不会提供前驱节点的任何信息。所以对上述链表进行改造，得出双向链表，即一个节点会提供下一个节点和上一个节点的信息，结构图如下所示。

简单链表

5、Java中的表（ADT）List

Java语言中，提供了一些普通数据结构的实现。该语言的这一部分叫做Collection API。表（ADT）是在Collection中实现的数据结构之一。

Java当中由java.util包中的List接口指定。根据上述表的实现思想，Java当中由ArrayList类提供了List ADT的一种可增长数组的实现。使用该数据结构的优点在于，get和set的调用花费常数时间。但是插入操作和删除操作代价昂贵（在于移动其与项）。

Java当中由LinkedList类提供了List ADT的双向链表的实现，优点在于新项的插入和删除开销比较小，这里假设变动项的位置是已知的，这意味着，在表的前端和末尾都是常数时间。使用LinkedList的缺点在于get的调用是昂贵的，除非调用的项非常的接近端点

5.1 Java当中Iterable接口

实现了Iterable接口的那些类，可以拥有增强For的循环，该循环施于这些类之上从而观察它们的所有项。

Collection接口当中扩展了Iterable接口。实现Iterable接口的类，必须提供了一个名叫iterator的方法。该方法返回一个实现了Iterator接口类。下面我们看看Iterator接口是干嘛的？

1
2
3
4
5
6
7
8
9
10
public interface Iterator<AnyType>{
	// 是否还有下一项？
	boolean hasNext();

	// 得到当前的项
	AnyType next();
	
	// 移除当前的项
	void remove();
}

具体每个方法是干嘛的，上述注释说的很清楚了。Iterator接口的思路就是，通过iterator方法，每个集合都可以创建一个实现Iterator接口的对象，并且将当前的位置概念在对象内部保存下来。

1、 使用iterator进行遍历。

获取当前对象的iterator，然后调用hasNext（）方法，next（）方法进行遍历。具体模拟入下所示：

1
2
3
4
5
6
7
···
Iterator<AnyType> iterator = collection.iterator();
while(iterator.hasNext()){
	AnyType item = iterator.next();
	System.out.println(item.toString());
}
···

在Iterator接口里面我们看到一个remove方法，这个方法主要是删除由next方法返回的最新的项，在Collection当中同样也提供了remove方法，两者到底有什么不同呢？

这里笔者推荐的是如果可以使用Iterator接口里面的remove，尽量使用。为什么这么说呢？原因有以下两点

1、因为我们知道collection当中的remove是先要找到删除的项，然后进行删除。而Iterator接口里面的remove是已经找到项的，在这里会节省一部分的时间。

2、如果直接使用Iterator的时候。如果对正在被遍历的集合进行结构上面的改变，那么迭代器将不再合法会跑出ConcurrentModificationException异常。如果直接使用Iterator内部的remove则不会抛出异常。

5.2 ArrayList的实现

笔者在这里模拟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
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
/**
 * 自定义ArrayList的实现方式
 * @author 刘酸酸
 *
 * @param <AnyType>
 */
public class MyArrayList<AnyType> implements Iterable<AnyType>{

	/** 默认扩容长度 */
	private static final int DEFAULT_CAPACITY = 10 ;
	
	/** 当前数据结构的长度 */
	private int mSize ;
	
	/** 内部使用的数据来存储数据 */
	private AnyType[] mArray ;
	
	public MyArrayList() {
		initMyArray();
	}

	/** 初始化数组 */
	private void initMyArray() {
		mSize = 0 ;
		ensureCapacity(DEFAULT_CAPACITY) ;
	}
	
	/** 返回当前元素的长度 */
	public int size(){
		return mSize ;
	}
	
	/** 当前表是否为空 */
	public boolean isEmpty(){
		return size() == 0 ;
	}
	
	/** 根据下表返回元素 */
	public AnyType get(int index){
		checkIndex(index);
		return mArray[index];
	}
	
	/** 在index的位置替换newValue，然后返回index位置以前的Vaule */
	public AnyType set(int index, AnyType newValue){
		checkIndex(index);
		AnyType oldValue = mArray[index];
		mArray[index] = newValue ;
		return oldValue ;
	}
	
	/** 默认插入，在当前表的最后一位进行插入 */
	public boolean add (AnyType value){
		add(size(),value);
		return true;
	}
	
	/** 移除index的元素并且把给元素返回 */
	public AnyType remove(int index){
		AnyType old = mArray[index] ;
		for(int i = index; i < size() - 1; i++){
			mArray[i] = mArray[i + 1] ;
		}
		mSize -- ;
		return old ;
	}
	
	/**给index的位置插入一个新的元素，index以后的所有元素后移一位 */
	public void add(int index, AnyType value){
		if(mArray.length == size()){
			ensureCapacity(size() * 2 + 1);
		}
		for(int i = mSize; i > index; i-- ){
			mArray[i] = mArray[i -1];
		}
		mArray[index] = value ;
		
		mSize ++ ;
	}
	
	/** 检查 */
	private void checkIndex(int index){
		if(index < 0 || index >= size()){
			throw new ArrayIndexOutOfBoundsException("index is not true");
		}
	}
	
	/** 扩容方法 */
	@SuppressWarnings("unchecked")
	private void ensureCapacity(int newCapactity){
		if(newCapactity < mSize){
			return 	;
		}
		AnyType[] old = mArray ;
		mArray = (AnyType[]) new Object[newCapactity];
		for(int i = 0; i < size(); i++){
			mArray[i] = old[i];
		}
	}

	@Override
	public Iterator<AnyType> iterator() {
		return new ArrayListIterator();
	}
	
	/**
	 * MyArrayList的迭代器。
	 * @author pengchengliu
	 *
	 */
	private class ArrayListIterator implements Iterator<AnyType>{

		private int mCurrent ;
		
		@Override
		public boolean hasNext() {
			return mCurrent < size();
		}

		@Override
		public AnyType next() {
			return mArray[mCurrent++];
		}

		@Override
		public void remove() {
			MyArrayList.this.remove(--mCurrent) ;
		}
	}
}