如何实现Java中一个简单的LinkedList-创新互联

创新互联www.cdcxhl.cn八线动态BGP香港云服务器提供商，新人活动买多久送多久，划算不套路！

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

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

针对于具体的Java实现：

1. 顺序存储的顺序表是用数组来实现的，以数组为基础进行封装各种操作而形成的List为ArrayList
2. 链表是用指针来描述其逻辑位置，在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;
 }
 }