横看成岭侧成峰,远近高低各不同。
不识庐山真面目,只缘身在此山中。
——苏轼
这一块儿学的是云里雾里,咱们先从简单的入手。逐渐的拨开迷雾见太阳。本次先做List集合的三个实现类的学习笔记
List特点:有序,元素可重复。其实它的本质就是一个线性表(下面会说到)
先上图,Java集合有Collection体系和Map体系:
然后简单介绍一下数据结构和算法:
数据结构就是数据和数据之间的关系,好比分子结构,晶体结构。碳原子按照一定的方式组合在一起形成碳分子,碳分子再按照一定方式形成晶体。
算法是对解题步骤的描述,体现在计算机上就是指令的有限序列
数据结构分为逻辑结构和物理结构。
逻辑结构:
物理结构:
顺序存储结构和链式存储结构。
顺序存储结构:在内存中开辟若干的连续空间,将每个空间存入数据,数据关联与其地址一致。比如数组。
上代码:
public class Test01 { public static void main(String[] args) {
Integer[] arr = new Integer[];
//向数组中插入元素
for (int i = ; i < arr.length; i++) {
arr[i] = i;
}
//将其中一个元素变为null;
arr[] = null;
//出现碎片
for (Integer item : arr) {
System.out.println(item);
}
System.out.println("===========");
arr[] = ;//存取方便,可直接赋值或取值
//删除第X个元素,但要避免碎片产生:
int x = ;
arr[x-]=null;//第二个元素引用变为null,该步骤可以省略,因为下面又更改了arr[x-1]的引用。写上仅为便于理解
//第X个元素之后的元素前移,代码表现为把后面的值依次赋给前面,从第X个开始
for (int i = x-; i < arr.length-; i++) {
arr[i] = arr[i+];
}
//length-1,需要新建数组来保存原数组
Integer[] newArr = new Integer[arr.length-];
for (int i = ; i < newArr.length; i++) {
newArr[i]=arr[i];
System.out.println(newArr[i]);
}
System.out.println("============");
//第Y个位置插入一个元素
int y = ;
//需要后移,所以先创建数组length+1
Integer [] newArr2 = new Integer[newArr.length+];
for (int i = ; i < newArr.length; i++) {
newArr2[i] = newArr[i];
}
//后移
for (int i = newArr2.length-; i > y- ; i--) {
newArr2[i]=newArr2[i-];
}
//插入
newArr2[y-] = ;
//遍历输出
for (int i = ; i < newArr2.length; i++) {
System.out.println(newArr2[i]);
}
} }
出结论:
顺序存储结构:
优点:1无需为表示表中元素之间的逻辑关系而添加空间
2可以快速地存取表中任意位置的元素
缺点:1插入和删除操作需要移动大量元素
2需要考虑索引越界为题
3扩容空间可能会造成空间浪费,缩小空间又可能会索引越界
4null值会造成空间“碎片”
链式存储结构:每个元素只记住它下一个元素是谁(地址)。
链式存储结构有多种,这里只介绍Java的链式存储结构:双向链表
上代码:
public class MyLinkedListDemo { public static void main(String[] args) throws Exception {
MyLinkList<String> list = new MyLinkList<>();
list.addFist("张三");
list.addFist("李四");
list.addLast("张三");
list.addLast("李四");
list.print();
System.out.println("===========");
list.add(,"王五");
list.print();
System.out.println("===========");
list.add(,"王五");
System.out.println(list.getSize());
list.add(,"王五");//这里会抛出空指针异常
}
}
public class MyLinkList<E> { Node<E> first;
Node<E> last; public void addFist(E e){
if (first == null) {
final Node<E> newNode = new Node<E>(null, e, null);//第一次加入数据,为first,last赋初值
first = newNode;
last = newNode;
}else{//否则把first的prev指向newNode,把newNode的next指向first,最后把newNode变为first
final Node<E> newNode = new Node<E>(null, e, first);
first.prev = newNode;
first = newNode;
}
}
public void addLast(E e){
if (last == null) {
final Node<E> newNode = new Node<E>(null, e, null);//第一次加入数据,为first,last赋初值
first = newNode;
last = newNode;
}else{//否则把last的next指向newNode,把newNode的prev指向last,最后把newNode变为last
final Node<E> newNode = new Node<E>(last, e, null);
last.next = newNode;
last = newNode;
}
}
public void add (int index,E e) throws Exception{//下标超出链表长度会空指针,因为超出长度的部分prev和next都是null
if(index == ){
addFist(e);
}else if (index == getSize()) {
addLast(e);
}else {
//这里画张图想一下,我要在1处插入x,就要把x的prev指向0,next指向1,把0的next指向x,把1的prev指向x
//这里的1和0就是index和index-1,通过循环Node.next获取index对应的Node
//先拿到0和1
Node<E> tempNodeNext = first;
for (int i = ; i < index; i++) {
tempNodeNext = tempNodeNext.next;
}
Node<E> tempNodePrev = tempNodeNext.prev;
//这里改指向
final Node<E> newNode = new Node<E>(tempNodePrev, e, tempNodeNext);
tempNodeNext.prev = newNode;
tempNodePrev.next = newNode;
}
}
public int getSize (){
Node<E> temp = first;
int i = ;
while(temp != null){
temp = temp.next;
i++;
}
return i;
}
//由于不实现Iterable,只能提供打印方法
public void print() {
Node<E> temp = first;
while(temp != null){
System.out.println(temp.item);
temp = temp.next;
}
}
private static class Node<E>{
Node<E> prev;
E item;
Node<E> next;
Node(Node<E> prev, E item, Node<E> next) {
super();
this.prev = prev;
this.item = item;
this.next = next;
}
}
}
出结论:
链式存储结构:
优点:插入和删除操作只需改变节点next和prev成员的指向即可,无需移位,无需扩容
缺点:失去了直接存取表中任意位置元素的能力
顺序存储结构和链式存储结构的对比:
1、存储分配方式:
顺序存储结构使用一段连续的存储单元依次存储线性表元素
链式存储结构使用任意存储单元存放线性表的元素
2、时间性能:
查找:
顺序存储结构O(1)
链式存储结构O(n)
插入和删除:
顺序存储结构O(n)
链式存储结构O(1)
3、空间性能:
顺序存储结构:空间分大了浪费,分小了上溢,还得扩容
链式存储结构:有空间就能分配,元素个数不受限制
言归正传。
ArrayList是顺序存储的线性表,LinkedList是链式存储的线性表
它们的特点都是有序,元素值可以重复。区别是底层算法不同。
Vector,这里我简单浏览了一下源代码,Vector底层算法和ArrayList是一样的
这里就不赘述了,直接说区别:
1、Vector的方法都是同步的(Synchronized),是线程安全的(thread-safe),而ArrayList的方法线程不安全,由于线程的同步必然要影响性能,因此ArrayList的性能比Vector好。
2、Vector扩容时容量翻倍,而ArrayList只增加50%的大小,(直接查它们的grow()方法)这样,ArrayList就有利于节约内存空间。
总之ArrayList比Vector在性能方面(无论时间性能还是空间性能)都是能省则省。
List就说到这里。下一篇说说队列