如何实现Java中一个简单的LinkedList-创新互联
创新互联www.cdcxhl.cn八线动态BGP香港云服务器提供商,新人活动买多久送多久,划算不套路!
成都创新互联成立与2013年,是专业互联网技术服务公司,拥有项目成都做网站、网站制作网站策划,项目实施与项目整合能力。我们以让每一个梦想脱颖而出为使命,1280元萍乡做网站,已为上家服务,为萍乡各地企业和个人服务,联系电话:18980820575LinkedList与ArrayList都是List接口的具体实现类。LinkedList与ArrayList在功能上也是大体一致,但是因为两者具体的实现方式不一致,所以在进行一些相同操作的时候,其效率也是有差别的。
对于抽象的数据结构——线性表而言,线性表分为两种,一种是顺序存储结构的顺序表,另一种是通过指针来描述其逻辑位置的链表。
针对于具体的Java实现:
- 顺序存储的顺序表是用数组来实现的,以数组为基础进行封装各种操作而形成的List为ArrayList
- 链表是用指针来描述其逻辑位置,在Java中以双向链表为基础进行封装各种操作而形成的List为LinkedList
针对插入与删除操作,ArrayList每插入一个元素,首先需要判断数组的空间够不够,不够要进行扩容,在有足够的空间的基础上,在指定的index位置上插入元素,但是该index及以后的元素都要后移。虽然删除操作不需要判断空间够不够,但同样需要该index及以后的元素向前移动,这些移动的操作会增加时间的复杂度。但是对于LinkedList就不一样,因为使用指针来指示其逻辑的位置,所以插入与删除的操作的时间复杂度都是 ** O(1) **
虽然对于ArrayList而言,插入与删除的时间复杂度很高,但是对于查找指定位置的元素这种操作而言,就非常的快,因为可以通过数组直接得到该下标对应的元素。反而,LinkedList而言,无法直接返回指定位置的元素,需要一个个查询,其时间的复杂度就是 ** O(n) **
与如何实现Java的ArrayList经典实体类一样,实现的目的主要在于练手以及掌握官方实现的原理和一些技巧,因此很多需要与其他类配合的方法和功能,就先不在这里实现如iterator等
所以,实现的LinkedList的方法如下:
add方法
get方法
indexOf方法
remove方法
与实现ArrayList的名字一样,为SimpleLinkedList。源码地址,欢迎star,fork
构建一个双向链表
构建的代码如下:
private static class Node{ E item; Node next; Node prev; public Node(E item, Node next, Node prev) { this.item = item; this.next = next; this.prev = prev; } }
文章名称:如何实现Java中一个简单的LinkedList-创新互联
网页地址:http://pwwzsj.com/article/cdegdc.html