如何实现Java中一个简单的LinkedList
LinkedList与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
构建一个双向链表
构建的代码如下：
privatestaticclassNode<E>{
Eitem;
Node<E>next;
Node<E>prev;
publicNode(Eitem,Node<E>next,Node<E>prev){
this.item=item;
this.next=next;
this.prev=prev;
}
}
常规的双向链表的构建方法，一个数字域存放数组，一个前指针指向一个Node类型的元素，一个后指针指向一个Node类型的元素。
对于LinkedList的实现而言，还需要以下三个成员变量
privateintsize; privateNode<E>first; privateNode<E>last;
Add方法
这里实现的add方法是简单的add(Ee)以及add(intindex,Ee)两个方法，addAll()将其他集合转换LinkedList的方法，暂时放到以后去实现。
add方法两个重载方法，其分别对应不同的添加方式。先说add(Ee)方法的实现。
publicbooleanadd(Eelement){
addAtLast(element);
returntrue;
}
不指定位置添加元素，则默认添加到了链表的最后。addAtLast的核心代码如下：
privatevoidaddAtLast(Eelement){
Node<E>l=last;
Node<E>node=newNode<E>(element,null,l);
last=node;
if(l==null){
first=node;
}else{
l.next=node;
}
size++;
}
首先找到最后一位的Node元素，然后根据element创建一个新的Node元素，其next指向为null,prev指向为最后一位Node元素。在创建完Node元素之后，last就变成了先创建的Node元素，接下来只需要把新node元素加到链表中即可。即让l对象(原最后一位，现倒数第二位元素的next指针，指向新node元素)。至此，新node元素的next指向null,prev指向倒数第二个元素，倒数第二个元素的next指向新node，就将node成功加入链表。
上述的操作也可以看出，其插入的操作非常省时间，比起ArrayList，扩容，移动元素快很多。
add的第二个重载方法add(intindex,Ee),先看代码实现：
publicvoidadd(intindex,Eelement){
checkRangeForAdd(index);
if(index==size){
addAtLast(element);
}else{
Node<E>l=node(index);
addBeforeNode(element,l);
}
}
首先判断要插入的index是否在范围内，在的话，再执行后续的add操作。如果要插入的index刚好是最后一位，则执行上面讲的addAtLast，如果不是，则得到index所对应的Node元素，执行addBeforeNode。
获取index所对应的Node元素，是node方法，代码如下：
privateNode<E>node(intindex){
if(index<(size<<1)){
Node<E>cursor=first;
for(inti=0;i<index;i++){
cursor=cursor.next;
}
returncursor;
}else{
Node<E>cursor=last;
for(inti=size-1;i>index;i--){
cursor=cursor.prev;
}
returncursor;
}
}
这里的查找采用二分查找，节省查找时间，而且也应用到了双向链表的特点。首先判断index在前一半的范围内，还是后一半的范围内。如果是前一半，则游标Node初始为first,用游标Node元素的next，不断指向index所在的元素。如果是后一半，则游标Node初始为last,用游标Node元素的prev,不断指向index所在的元素。
在指定元素的前面插入新节点的addBeforeNode的方法如下：
privatevoidaddBeforeNode(Eelement,Node<E>specifiedNode){
Node<E>preNode=specifiedNode.prev;
Node<E>newNode=newNode<>(element,specifiedNode,preNode);
if(preNode==null){
first=newNode;
}else{
preNode.next=newNode;
}
specifiedNode.prev=newNode;
size++;
}
插入的方式很简单，新节点的prev是原index元素的prev,新节点的next是原index元素。剩下的操作是把该node放到链表中，让原index元素的prev的next为新节点，但是要判断preNode是不是空，是的话，表示newNode为第一个元素，就是first。
至此，一个add方法，就实现完了。
get方法
get方法在有了上述node方法之后，就非常的简单。代码如下：
publicEget(intindex){
checkRange(index);
returnnode(index).item;
}
checkRange检查index是否不在范围内。
privatevoidcheckRange(intindex){
if(index>=size||index<0){
thrownewIndexOutOfBoundsException("指定index超过界限");
}
}
indexOf方法
indexOf(Objecto)用来得到指定元素的下标。
publicintindexOf(Objectelement){
Node<E>cursor=first;
intcount=0;
while(cursor!=null){
if(element!=null){
if(element.equals(cursor.item)){
returncount;
}
}else{
if(cursor.item==null){
returncount;
}
}
count++;
cursor=cursor.next;
}
return-1;
}
与ArrayList一样，从第一位开始查找，首先先判断element是不是null,分成两种情况。
remove方法
remove方法与add方法一样，同样有两个重载的方法，remove(Objecto)与remove(intindex)
先看简单的remove(intindex)方法，代码如下：
publicEremove(intindex){
checkRange(index);
returndeleteLink(index);
}
deleteLink是将该index所对应的节点的链接删除的方法，其代码如下：
privateEdeleteLink(intindex){
Node<E>l=node(index);
Eitem=l.item;
Node<E>prevNode=l.prev;
Node<E>nextNode=l.next;
if(prevNode==null){
first=nextNode;
}else{
prevNode.next=nextNode;
l.next=null;
}
if(nextNode==null){
last=prevNode;
}else{
nextNode.prev=prevNode;
l.prev=null;
}
size--;
l.item=null;
returnitem;
}
首先获得该index对应的Node元素，得到该Node元素的前一个元素和后一个元素。接下来，只需要将前一个元素和后一个元素直接相连即可，其他只需要额外判断前一个元素和后一个元素是否为null就行。在判断前一个元素是否为null的时候，只需要操作前一个元素，在判断后一个元素是否为null的时候，也只需要操作后一个元素。最后，将要删除的元素各个引用至为null。
remove另一个重载方法remove(Objecto)，在实现了indexOf和deleteLink方法之后，就非常简单。
publicbooleanremove(Objecto){
intindex=indexOf(o);
if(index<0){
returnfalse;
}
deleteLink(index);
returntrue;
}
获取该元素对应对应的下标，然后执行deleteLink方法，完成remove操作。
总结
至此，一个功能简单的LinkedList就实现完成了，全部的代码可以看源码地址，
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，同时也希望多多支持毛票票！