如何实现Java中一个简单的LinkedList - 行业资讯 - 肥雀云

LinkedList与ArrayList都是列表接口的具体实现类.LinkedList与ArrayList在功能上也是大体一致,但是因为两者具体的实现方式不一致,所以在进行一些相同操作的时候,其效率也是有差别的。

对于抽象的数据结构,线性表而言,线性表分为两种,一种是顺序存储结构的顺序表,另一种是通过指针来描述其逻辑位置的链表。

<强>针对于具体的Java实现:

　　<李> 　　<李> 　　　　

针对插入与删除操作,ArrayList每插入一个元素,首先需要判断数组的空间够不够,不够要进行扩容,在有足够的空间的基础上,在指定的指数位置上插入元素,但是该指数及以后的元素都要后移。虽然删除操作不需要判断空间够不够,但同样需要该指数及以后的元素向前移动,这些移动的操作会增加时间的复杂度。但是对于LinkedList就不一样,因为使用指针来指示其逻辑的位置,所以插入与删除的操作的时间复杂度都是* * O (1) * *

虽然对于ArrayList而言,插入与删除的时间复杂度很高,但是对于查找指定位置的元素这种操作而言,就非常的快,因为可以通过数组直接得到该下标对应的元素。反而,LinkedList而言,无法直接返回指定位置的元素,需要一个个查询,其时间的复杂度就是* * O (n) * *

与如何实现Java的ArrayList经典实体类一样,实现的目的主要在于练手以及掌握官方实现的原理和一些技巧,因此很多需要与其他类配合的方法和功能,就先不在这里实现如迭代器等

所以,实现的LinkedList的方法如下:

与实现ArrayList的名字一样,为SimpleLinkedList。源码地址,欢迎星,叉

构建的代码如下:

　　　　　　私有静态类Node下一个; 　　Nodeprev; 　　公共节点(E, Node接下来,Node上一页){ 　　这一点。项=项目; 　　这一点。下一个=下一个; 　　这一点。prev=prev; 　　} 　　} 　　之前　　　　

常规的双向链表的构建方法,一个数字域存放数组,一个前指针指向一个节点类型的元素,一个后指针指向一个节点类型的元素。

对于LinkedList的实现而言,还需要以下三个成员变量

　　　　　　私人int大小; 　　私人Node第一个; 　　私人Node最后一次; 　　之前　　　　

<强>添加方法

这里实现的添加方法是简单的添加(E E)以及添加(int指数E E)两个方法,addAll()将其他集合转换LinkedList的方法,暂时放到以后去实现。

添加方法两个重载方法,其分别对应不同的添加方式。先说添加(E E)方法的实现。

　　　　　　公共逻辑加(E元素){ 　　addAtLast(元素); 　　返回true; 　　} 　　　　

不指定位置添加元素,则默认添加到了链表的最后.addAtLast的核心代码如下:

　　　　　　私人空间addAtLast (E元素){ 　　Nodel=去年; 　　Node节点=new Node(元素,null, l); 　　去年=节点; 　　如果(l==null) { 　　第一次=节点; 　　其他}{ 　　l下一个=节点; 　　} 　　大小+ +; 　　} 　　　　

首先找到最后一位的节点元素,然后根据元素创建一个新的节点元素,其未来指向为null,上一页指向为最后一位节点元素。在创建完节点元素之后,最后就变成了先创建的节点元素,接下来只需要把新节点元素加到链表中即可。即让l对象(原最后一位,现倒数第二位元素下指的针,指向新节点元素)。至此,新节点元素的未来指向空,上一页指向倒数第二个元素,倒数第二个元素的未来指向新节点,就将节点成功加入链表。

上述的操作也可以看的出,其插入的操作非常省时间,比起ArrayList,扩容,移动元素快很多。

添加的第二个重载方法添加(int指数E E),先看代码实现:

　　　　　　公共空间添加(int指数E元素){ 　　checkRangeForAdd(指数); 　　如果(指数==大小){ 　　addAtLast(元素); 　　其他}{ 　　Nodel=节点(指数); 　　addBeforeNode(元素,l); 　　} 　　} 　　　　

首先判断要插入的指数是否在范围内,在的话,再执行后续的添加操作。如果要插入的指数刚好是最后一位,则执行上面讲的addAtLast,如果不是,则得到指数所对应的节点元素,执行addBeforeNode。

获取指数所对应的节点元素,是节点的方法,代码如下: