JDK提供了一组主要的数据结构的实现,如List、Set、Map等常用结构,这些结构都继承自java.util.collection接口。List接口 List有三种不同的实现,ArrayList和Vector使用数组实现,其封装了对内部数组的操作。LinkedList使用了循 ...
JDK提供了一组主要的数据结构的实现,如List、Set、Map等常用结构,这些结构都继承自java.util.collection接口。
List有三种不同的实现,ArrayList和Vector使用数组实现,其封装了对内部数组的操作。LinkedList使用了循环双向链表的数据结构,LinkedList链表是由一系列的链表项连接而成,一个链表项包括三部分:链表内容、前驱表项和后驱表项。
LinkedList的表项结构如图:
LinkedList表项间的连接关系如图:
可以看出,无论LinkedList是否为空,链表都有一个header表项,它即表示链表的开头也表示链表的结尾。表项header的后驱表项便是链表的第一个元素,其前驱表项就是链表的最后一个元素。
对基于链表和基于数组的两种List的不同实现做一些比较:
1、增加元素到列表的末尾:
在ArrayList中源代码如下:
1 public boolean add(E e) {2 ensureCapacityInternal(size + 1); // Increments modCount!!3 elementData[size++] = e;4 return true;5 }
原标题:java核心数据结构总结
关键词:JAVA
*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们:
admin#shaoqun.com
(#换成@)。