这篇文章主要记录了几种基本的数据结构的学习过程，包括数组、栈、队列、单向链表、双端链表和双向链表，自己也试着去用Java语言动手写了栈、队列和链表，以加深印象。途中遇到了很多小问题，在解决的过程中，自己对这几种数据结构的理解也逐渐加深了。其中数组、栈和队列是相对比较简单的，基本上接触过编程语言的人都接触过数组，记得当时大学学的是VB，里面也讲到过数组和栈，所以前面的三个是之前遇到过的，也不难理解; 对我来讲，难点是链表，因为这个数据结构之前只有非常浅薄的一点理解，就是它是由一个一个的数据块链接起来的，但是怎么个链接法，就不知道了，这次系统的学习了下数据结构，总算是搞明白了啥是链表，以及如何自己动手写一个链表。

在开始之前，先来回忆下之前我们所知道的关于数组、栈、列队和链表的知识：

1. 数组：有序的元素序列，大小不可改变，查询容易，可以通过数组名[索引]的方式快速的访问到，但是插入和删除比较困难

2. 栈：先进后出，后进先出，后来居上

3. 队列：先进先出

4. 链表：每个数据分为两部分，即数据域和指针域，指针域将每个数据块连接起来，特点是插入和删除容易，但是查询就比较困难，因为没查询一个数据，都是从头挨个儿查一遍，如果要查询的数据在最后，就得将整个链表遍历一遍，所以说，链表的查询效率较低。

在本文所有的代码实现都是在Java语言环境下完成的

数组(Array)

如图所示就是一个简单的数组，当数组的大小指定之后，就无法改变，如果访问越界或者操作越界都会爆出java.lang.ArrayIndexOutOfBoundsException，在访问的时候可以通过数据名[索引]来访问数组中的数据，可以说是非常的方便了。在Java中可以通过：数据类型[] 数组名 = new 数据类型[数组大小]等好几种方式来定义一个数组，关于数组的基本使用这里也不再赘述，在这篇文章我要记录的是如何自己去封装一个数组，就像ArrayList一样，拥有添加，删除，查找等功能，来试试吧。

我尝试着去看了ArrayList的源码，看不懂，对扩容机制也不太了解，在下面这个案例中，我尝试着用笨办法去实现List的自动扩容，就是每次添加都判断元素是否大于了数组长度的75%，如果大于，则新new一个长度是原数组1.5倍的数组，将旧数组拷贝进去，并用新数组替代旧数组，想的时候确实挺简单的，但是真的自己动手做的时候，发现好多细节的问题，学到了不少东西。又花了些时间把注释整理了一遍，就是扩容的代码太无脑了，以后学到更好的方法再来替换。如果你有兴趣阅读了代码，有什么建议可以在评论区留言哦。

package Array;public class Myarray {// 数组中元素的数据类型，本例中是long类型的数组，// 本来想弄个泛型，结果不会搞，先就这样吧private long[] arr;// 数组中的元素数目，刚创建，啥都还没装呢，所以是0private int elementes = 0;// 数组的大小，用来扩容用的private int size = 0;// 扩容用的数组private long[] arrgrow; /*** 空参构造*/public Myarray() {// 默认数组长度为16arr = new long[16];}/*** 有参构造，传入一个自定义数组的长度值* * @param MaxSize*/public Myarray(int MaxSize) {// 数组的长度设置为用户输入的值arr = new long[MaxSize];}/*** 添加数组元素，普通添加，就是添加到末尾* * @param value*/public void add(long value) {// 添加的时候判断，当前的元素数目是否达到了数组长度的75%，如果没有则正常添加size = arr.length;if (elementes < arr.length * 0.75) {arr[elementes] = value;elementes++;} else {// 达到扩容条件了，开始扩容,这部分代码被我们提出去了，直接this调用即可arr = expansion(arr,size);// 正常添加arr[elementes] = value;elementes++;}}/*** 插入前排序* @param value*/public void orderadd(long value) {size = arr.length;// l 用于找到比要插入的数大的数的索引int l = 0;// 插入前还是判断是否扩容if (elementes < arr.length * 0.75) {orders(arr,value, l);} else {// 达到扩容条件了，开始扩容,这部分代码被我们提出去了，直接this调用即可arr = expansion(arr, size);// 扩容完毕，继续添加orders(arr,value, l);}}/*** 遍历格式化打印数组中的数据*/public void show() {// 当只有一个数据时，就直接打印，也别浪费时间去遍历了if (elementes == 1) {System.out.println("[" + arr[elementes - 1] + "]");} else {// 格式化打印成 [-1,0,1,3,4,5] 这种格式System.out.print("[");for (int i = 0; i < elementes - 1; i++) {System.out.print(arr[i] + ",");}System.out.print(arr[elementes - 1]);System.out.println("]");}}/*** 在数组中查找数据，找到第一个后返回对应的索引值，没找到的话，返回-1* * @param value* @return*/public int search(long value) {int j;for (j = 0; j < arr.length; j++) {// 遍历数组，对比，找到相等的了就退出循环，这样就获得了对应的索引if (value == arr[j]) {break;}}// 如果找到了最后一个，则说明没有找到，返回-1if (j == elementes) {return -1;} else {// 找到了，返回对应的索引值return j;}}/*** 通过二分法查找* 二分法查找的前提是数组必须得是有序的* @param value* @return*/public int binarysearch(long value) {// 三个位置，最左边的数，最右边的数，中间的数int middle = 0;int left = 0;int right = elementes-1;while (true) {// 一直找，一直找// 计算中间的数等于两边数的和整除2middle = (left + right) / 2;// 判断中间数是否匹配if (arr[middle] == value) {// 如果中间的数匹配，则返回中间的数，这玩意儿就是你要找的数的索引return middle;} else if (left > right) {// 如果不是且左边的数都大于右边的数了，则说明没有找到，返回-1return -1;} else {// 剩下的情况if (arr[middle] > value) {// 如果中间的数据大于要找的数，则证明那个数在中间数的左边// 中间数-1变成右边数，继续找right = middle - 1;} else {// 如果中间的数据小于要找的数，则证明该数在中间数的右边// 中间数+1变为左边数，继续找left = middle + 1;}}}}/*** 通过索引查找，输入索引，返回数值* * @param index* @return*/public long get(int index) {// 初始化返回值为-1,代表没有找到long result = -1;if (index < 0 || index >= arr.length) {// 如果用户输入的索引越界了，打印信息告知System.out.println("您输入的索引越界了，请检查后输入");} else {// 找到了，给返回值重新赋值为查找到的索引result = arr[index];}return result;}/*** 通过索引删除* * @param index*/public void delete(int index) {if (index < 0 || index >= arr.length) {System.out.println("您输入的索引越界了，带脑子了嘛？");} else {for (int k = index; k < arr.length - 1; k++) {arr[k] = arr[k + 1];}arr[elementes - 1] = 0;elementes--;}}/*** 前面的添加数据部分，用到了扩容的代码，这部分代码的重复性较高，所以将它抽取出来* * @param size*/public long[] expansion(long[] arr,int size) {// 这个扩容方法比较笨哈，就是新new一个长度为原来1.5倍的数组，然后把旧数组全装进去size = (int) (size * 1.5);arrgrow = new long[size];for (int j = 0; j < elementes; j++) {arrgrow[j] = arr[j];}// 将扩容后的数组指向arrarr = arrgrow;return arr;}public void orders(long[] arr,long value,int l) {// 挨个遍历数组，比对value和各个数的大小for (l = 0; l < elementes; l++) {// 这里这个elementes其实就是总共的元素数，插入了一个，就是+1// 如果有个数比value大，则证明value应该插入到 l 这个位置，退出循环if (value < arr[l]) {break;}}// 将 l 到最后一个数整体往后移动一位，以留出 l 的位置for (int m = elementes; m > l; m--) {// 倒着遍历，将l位到elementes的数据都往后移动一位arr[m] = arr[m - 1];}// 将数据插入到 l 的位置arr[l] = value;elementes++;}
}

Test Demo:

package Array;
public class MyarrayTest {public static void main(String[] args) {Myarray myarray = new Myarray(5);//初始化数组长度为5myarray.orderadd(1);myarray.orderadd(0);myarray.orderadd(5);myarray.orderadd(3);myarray.orderadd(4);myarray.orderadd(-1);myarray.orderadd(-5);myarray.orderadd(-5);myarray.orderadd(-5);myarray.orderadd(-5);myarray.orderadd(-5);myarray.orderadd(-5);myarray.orderadd(-5);myarray.orderadd(-5);myarray.orderadd(-5);myarray.orderadd(-5);// 添加超过5的数据myarray.show();int x = myarray.binarysearch(5);System.out.println("查找结果："+ x);myarray.delete(-1);myarray.show();}
}

[-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-1,0,1,3,4,5]
查找结果：15
您输入的索引越界了，带脑子了嘛？
[-5,-5,-5,-5,-5,-5,-5,-5,-5,-5,-1,0,1,3,4,5]

运行okay。

栈(Stack)

未完待续～～