链表和数组队列

            之前没有学过数据结构，链表真的很丧心病狂有木有~~~~~~

           之前学过数组，但是对于数组数据在哪里创建和存储简直一概不知啊，后来学到堆和栈内存，才有一点浅薄的认识。

               数组：                                                                   

数组的创建：堆内存用来存放由new运算符创建的对象和数组，在堆中分配的内存，由java虚拟机的自动垃圾回收器来管理。在堆中创建一个数组后，在栈内存中同时定义一个变量，这个变量代表堆内存中数组的首地址，该变量用于以后访问数组。

数组的优点:1） 访问,查找元素通过下标，效率高，时间复杂度为O(1)

                  2） 浪费空间

数组的缺点:1) 数据分配一块连续的内存上，创建时必须明确大小，不能动态扩充

                  2） 插入元素和删除元素，在改动元素之后的元素也得跟着变化，操作麻烦

定义数组的方式：一维数组

数据类型 [] 数组名 = new 数据类型[长度];

数据类型 [] 数组名 = {值,...};

数据类型 [] 数组名 = new 数据类型[]{值,...};

数据类型 [] 数组名;

数组名 = new 数据类型[长度];

数组名 = new 数据类型[]{值,...};

二维数组：

数据类型 [][] 数组名 = new 数据类型[行][列];

数据类型 [][] 数组名 = {{值,...},...};

数据类型 [][] 数组名 = new 数据类型[][]{{值,...},...};

数据类型 [][] 数组名;

数组名 = new 数据类型[行][列];

数组名 = new 数据类型[][]{{值,...},...};

数组初始化:
初始化是指为数组元素开辟内存空间,并且赋初始值.
注意:不能只分配空间而不赋初始值.

空指针异常的实例：

Student [] array = new Student[10];

Student stu = array[0];

stu.setName("张三");

//必须要先给对象，才能使用。

链表：

1、链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。

2、链表的优点：1） 插入和删除元素不必改动其他元素，复杂度小，为O（1）

                          2） 不要求连续的存储空间，空间利用率高

     链表的缺点：1）访问元素得从头结点开始，不能随机存取

                          2）查找元素的效率低

3、链表的分类：单链表，双链表，循环链表

单链表：单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。

双链表： 在单循环链表中，虽然从任一单元出发，可以找到其前驱单元，但需要O(n)时间。如果我们希望能快速确定表中任一元素的前驱和后继元素所在的单元，可以在链表的每个单元中设置两个指针，一个指向后继，另一个指向前驱，形成双向链表或简称为双链表。

 循环链表：

 

链表中插入一个节点的方法:

注意:插入一个节点后，给节点之间建立关系，得先建立后面的，再建立前面的，顺序千万不能错

因为数组大小固定，不知长度的情况下，数组操作起来很不灵活，链表正好弥补了数组的缺点，但是数组队列也可实现改变数组大小的功能。现在介绍一下数组队列：当你新建的数组长度不满足要求时，在堆内存中再新建一个长度改变的数组，对原数组中的数据进行改变时，必须把原数据拷贝到新数组中，再改变数据，最后还要把新数组的首地址赋给原数组的首地址。

实现：添加一个元素的实现方法

 

 对于add()或者insert()方法中的参数类型，可以是不同的对象，这时需要用到java中的泛型实现。泛型这个没有去具体的查找，有时间再去弄清楚。