Java重写LinkedList方法详解，双向链表结构包括增删改查及List接口和测试类（不含迭代器）
本文简单介绍下什么是LinkedList以及链表的结点和双向链表结构以及怎样用Java简单重写LinkedList类，目的在于重写的LinkedList类实现与JDK提供的LinkedList类中基本功能相同
前言
本项目使用的是Maven项目，同时使用的是Junit框架进行测试。如果是普通的Java项目，需要自己拷贝代码并自己写主函数方法进行测试。
什么是LinkedList
LinkedList
LinkedList类是List接口的一个具体实现类，用于创建链表数据结构来存放数据，相比于List接口的另一个具体实现类ArraysList，LikedList在插入或删除元素时具有更好的性能，但在查找某一元素时，LinkedList的性能就不如ArraysList了。LinkedList基本用法与ArraysList相同，但LinkedList具有一些自己独特的方法，所以当我们使用LinkedList自身独有的方法时（比如addFirst、addLast等），要注意如果是用List接口去定义的LinkedList对象，我们需要把对象向下转型进行强制类型转换，才能调用LinkedList的独有的方法。
比如：
List<String> list=new LinkedList<String>();
LinkedList<String> list1=(LinkedList<String>) list;
list1.addFirst("d");
链表结点
LinkedList的底层是基于双向链表，提到双向链表就得先说下构成双向链表的结点。在链表的数据结构中，链表中的每一个元素称为“结点”，单链表中每个结点都应包括两个部分：一个是需要用到的实际数据data；另一个就是存储下一个结点地址的指针，即数据域和指针域；而双向链表中，每个结点包括存储其上一个结点地址的指针，用到的数据data和存储下一个结点的指针。数据结构中的每一个数据结点对应于一个存储单元，这种储存单元称为储存结点，也可简称结点。
单向链表结点结构（data为实际存放的数据，next为存放下一个结点地址的指针）如图
双向链表结点结构（prev是存放上一个结点地址的指针，data为实际用到的数据，next为存放下一个结点地址的指针）如图
双向链表结点在Java中的构造代码
JDK底层提供的源码
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
我自己重写LinkedList时构造的双向链表结点代码
/*设计结点，作为一个内部类封装在LinkedList类里仅供LinkedList本类使用*/
private static class Node {
Object data;//结点中实际存放的元素数据
Node prev;//上一个结点（直接前驱）的引用
Node next;// 下一个结点（直接后继）的引用
Node(Node prev,Object data,Node next){
this.prev=prev;
this.data=data;
this.next=next;
}
}
双向链表结构
LinkedList存储是双向链表结构，双向链表是链表的一种，双向链表又分为双向循环链表和普通的双向链表，JDK中的LinkedList类是普通的双向链表不涉及循环，双向链表中每个数据结点在存放实际用的数据的同时还都有两个指针分别这个结点的直接前驱和直接后继，所以从双向链表的任意一个结点都能很容易直接访问它的前驱结点和后继结点。
Java中双向链表结构如图
我所重写的LinkedList类双向链表结构的Java参考代码
package list.ext;
import list.iface.List;
/**
* @author 作者 水寒轩
* @version 1.0
创建时间：2019年12月4日 上午9:06:34
* 类说明 重写LinkedList方法
*/
public class LinkedList implements List {
/*设计结点*/
private static class Node {
/*设计双向链表结点，代码参考本文结点的部分*/
}
private Node firstNode=null;//链表中的首节点
private Node lastNode=null;//链表中的尾节点
private int size=0;//链表长度
/*以下是对链表操作的各类方法*/
方法1
方法2
.....
}
关于List接口
LinkedList是List接口的一种具体实现类，所以我们在重写LinkedList时必须实现List接口里的方法。
我们可以通过查看参考JDK提供的List接口的方法，自己创建一个List接口，我们自己创建的List接口中要包括一些JDK提供的List接口常用的方法（我们可以在List接口中将其定义为抽象方法），然后我们对自己写的List接口进行实现，目的在于通过我们自己写的List接口实现与JDK中提供的List接口相同的基本功能方法。
List接口代码
package list.iface;
/**
* @author 作者 水寒轩
* @version 1.0
创建时间：2019年12月4日 上午8:09:59
* 类说明 List接口
*/
public interface List{
/**
* @return the size 获取集合中元素的数量
*/
public abstract int size();
/**
* @param object 向集合中添加元素
* @return
*/
public abstract boolean add(Object object);
/**
* @param index 指定位置下标 向集合中指定插入某个元素的目标位置
* @param object 要向集合插入的元素
* @return
*/
public abstract void add(int index, Object object);
/**
* @param anotherExtList 将anotherExtList集合追加到本集合的最后
*/
public abstract void addAll(List anotherExtList);
/**
* @param index 移除集合中指定index下标位置的元素
*/
public abstract void remove(int index);
/**
* 清空集合
*/
public abstract void clear();
/**
* @param index 输入集合中元素值的index位置
* @return 返回集合中index位置上元素的的值
*/
public abstract Object get(int index);
/**
* @return 返回数组对象
*/
public abstract Object[] toArray();
/**
* 打印输出集合中元素的值
*/
public abstract void printList();
/**
*
* @param index 输入集合中要修改的元素的指定index下标位置
* @param object 修改后的元素
*/
public abstract void set(int index, Object object);
/**
* @param anotherExtArrayList 将anotherList集合追加到本集合的指定index位置
*/
public abstract void addAll(int index,List anotherExtList);
}
重写LinkedList类方法
本部分会讲解部分重点方法代码，其余方法解析请参考之后的重写LinkedList类的具体代码。
基础方法
这里的基本方法不是简单的add一类的方法，而是对LinkedList操作的一些基本方法，特别是一些封装在类内部仅供LinkedList本类调用的方法是实现LinkedList类的一些基础功能方法的先决条件，十分重要。
判断下标是否合法
首先，当我们打算给集合传一个下标，进行插入或者删除的时候，我们必须考虑传入的下标是否合法，一个集合合法的下标范围是在0到这个集合的size-1，超过这个范围的下标都是非法操作，所以我们需要一个方法去判断这个下标是否合法，合法时继续操作，非法就抛出异常。具体封装方法实现请参考代码注释，封装方法代码如下：
/*调用isElementIndex方法，判断输入下标是否合法，不合法时抛出异常*/
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+this.size);
}
/*判断输入下标是否合法，供checkElementIndex方法调用，不合法时由checkElementIndex方法抛出异常*/
private boolean isElementIndex(int index) {
/*表达式index >= 0 && index < size成立返回true，不成立返回false*/
return index >= 0 && index < size;
}
根据下标找结点的内部封装方法
关于根据下标找结点的内部封装方法，之所以需要这种方法，是因为LinkedList与ArrayList结构不同，ArrayList存储结构的本质是一个数组，是在内存地址中开辟的一组地址连续的空间单元，如图：
为什么ArrayList查找某一元素性能好而添加或删除性能差，是因为ArrayList的首元素的内存地址我们是已知的，当我们查找某个下标的时候，只需要根据
首元素地址+下标×每个元素占用的内存空间大小，就能很快的精确定位到该元素的位置，以下标为i的元素每个元素占n个字节内存空间大小举例，我要查找它在ArrayList的位置，只需要根据首地址0x00XX+i*n就能查找到下标为i的元素位置，但是在添加，ArryaList必须再在数组中开辟一个新的空间存放新的数组，新的数组空间要比原先的大，然后再在把原先数组元素拷贝进新数组里，再在指定位置添加元素，原指定位置元素及其之后的所有元素后移；删除的时候是要先把指定元素之后的元素前移，开辟一个比原先数组小的新数组（可以先理解为比原先数组长度小1位），再把原先数组从头拷贝原先数组长度减一个元素，这样才实现了插入和删除操作。而LinkedList存储方式在内存中是无序的所以首元素地址+下标×每个元素占用的内存空间大小的方法就不能够使用，只能通过遍历链表来判断下标index元素结点在链表中的位置，也可以把这个过程理解为就是给链表中的元素结点打下标（这也是为什么LinkedList查找某一元素性能不如ArrayList的根本原因，因为每次我们去查找一个元素都得对链表进行遍历，但是在插入或删除时，LinkedList虽然需要进行遍历，但是却不会发生元素的位移，也不需要开辟新的空间用来存放修改后的元素数据）所以我们需要一个判断结点下标的方法来实现这个过程。
判断结点下标的方法有两种，首先是第一种，从头开始遍历，一个一个查，代码如下：
// /*根据下标找节点：从头遍历*/
private Node node(int index) {
//先判断index是否合法
checkElementIndex(index);
int tag=0;
/*用来循环统计在链表中从头查找结点所经历的结点个数
也可以理解为是手动给结点做下标，
比如查第一个结点经历了０个结点，所以第一个结点的tag是０；
查找第二个结点经历了１个结点，所以第二个结点的tag是１以此类推，
可以理解成结点的下标*/
Node tempNode=null;//用来指向查找到的结点返回
/*从首结点往后遍历*/
for(Node n=this.firstNode;n!=null;n=n.next) {
/*判断查找的第几个结点是index*/
if(tag==index) {
temp=n;
break;
}
tag++;
}
return temp;
}
然后是第二种，二分查找法来判断结点下标，先跟长度的中间数比较，如果比其小就从头开始查找，比其大就从尾元素开始查找，直到查找到为止，相比第一种方法，遍历元素是第一种方法的一半，时间复杂度也是第一种的一半，程序效率是第一种方法的二倍，代码如下：
/*根据下标找节点：二分法查找*/
/*优点：是从头查找的普通方法的时间复杂度的一半，程序效率是普通从头遍历方法的二倍*/
private Node node(int index) {
//先判断index是否合法
checkElementIndex(index);
/*集合长度右移一位，相当于除以２*/
// 从效率上看，使用移位指令有更高的效率，因为移位指令占2个机器周期，而乘除法指令占4个机器周期。
// 从硬件上看，移位对硬件更容易实现，所以会用移位
if(index<(size>>1)) {
/*前半部分从头找*/
Node node=this.firstNode;
for(int i=0;i<index;i++) {
node=node.next;
}
return node;
}else {
/*后半部分从末尾找*/
Node node=this.lastNode;
for(int i=size-1;i>index;i--) {
node=node.prev;
}
return node;
}
}
根据下标获得元素的方法，只需要调用根据下标判断结点的方法找到相应的结点再返回结点的值即可，代码如下：
/*根据下标获取链表元素*/
public Object get(int index) {
/*先调用node(index)方法，根据下标查找节点，再返回节点的值*/
return this.node(index).data;
}
添加元素方法
addFirst、addLast以及add方法
addFirst和addLast是LinkedList的独有方法，而add方法是List接口提供的方法由LinkedList去具体实现，其中，add方法功能与addLast方法一致，在Java代码中add也是直接调用的addLast方法进行实现，所以不再进行详细讲解。
先讲解下addFirst和addLast方法，顾名思义，addFirst是添加首元素而addLast是添加尾元素，接下来分别讲解。
addFirst方法
首先先来讲解addFirst，分为空表状态下添加和非空表状态下添加
空表状态下添加首元素：
由于表中只有一个添加元素，所以链表首结点结点对象和尾结点结点对象都指向这一个元素结点，这个元素结点的prev和next都为null，链表长度从0变为1
非空表状态下添加首元素：
添加前
添加时，让原首元素结点的prev指向要添加的结点，要添加的结点addNode的next指向原首元素结点，过程如图
最后再让链表的首结点结点对象指向添加的结点，然后让链表的长度加1，添加首结点的过程就完成了。
重写后的addFirst方法实现代码
/*在LinkedList首元素位置添加元素*/
public void addFirst(Object object) {
/*构建结点用来存放元素数据*/
Node node=new Node(null, object, null);
if(this.size==0) {
this.firstNode=node;
this.lastNode=node;
this.size++;
}else {
this.firstNode.prev=node;
node.next=this.firstNode;
this.firstNode=node;
this.size++;
}
}
addLast方法
接下来讲解下addLast，同样也分为空表状态和非空表状态的添加
空表状态下添加
首先，当集合为空的时候，addLast方法功能与addFirst功能相同，添加的元素结点既是首元素结点又是尾元素结点，所以直接调用addFirst方法即可，具体实现参考addFirst空表状态下添加过程，这里就不再详述。
非空表状态下添加
非空表状态下添加过程与addFirst非空表状态下添加大同小异，主要针对的操作只是让原链表lastNode结点的next指向要添加的addNode，要添加的addNode的prev指向lastNode再让lastNode指向addNode，长度再加一结点就添加完成了。
添加前：
添加时：
添加完成：
重写后的addLast方法实现代码，由于add方法与addLast方法功能相同，同时附带add方法代码
/*在LinkedList尾元素位置添加元素*/
public void addLast(Object object) {
/*构建结点用来存放元素数据*/
Node node=new Node(null, object, null);
if(this.size==0) {
this.addFirst(object);
}else {
this.lastNode.next=node;
node.prev=this.lastNode;
this.lastNode=node;
this.size++;
}
}
/*添加元素*/
public boolean add(Object object) {
// TODO Auto-generated method stub
/*添加元素的时候直接在LinkedList最后添加元素*/
this.addLast(object);
return true;
}
在指定位置插入元素或集合、将一个集合添加到另一个集合方法
在指定下标处添加元素的add(int index, Object object)方法
首先当index为0时，相当于我们在链表的首元素位置添加元素，跟addFirst方法功能相同，所以我们直接调用addFirst方法即可，具体过程参考addFirst方法讲解。现在我们来讲解下当index不为0且范围合法情况下插入某一指定位置的操作，我们要首先明确，当我们选择在下标index位置插入一个元素时，原先index位置的元素下标要变为index+1具体过程如下图解。
添加前：
先把要添加的结点addNode的prev指向原index位置结点的直接前驱，然后把addNode的next指向原index结点位置：
然后再让原先index位置的直接前驱的next指向addNode，再让原下标index的结点的prev指向addNode，链表长度加1，添加完成，过程如图：
之所以采取这种先让addNode的prev和next连接链表，再让链表中相关结点的prev和next指向addNode的方法，是因为我们如果直接先让原index结点的prev指向addNode的话，addNode的prev就找不到原index结点的直接前驱，虽然我们可以创建一个对象结点，先指向原index位置的直接前驱来克服这种情况，但是这种情况要多创建一个对象结点，会占用系统资源，因此我们就需要通过优化自己的代码来避免系统资源的无谓浪费。
将指定集合元素插入到下标index位置的方法addAll(int index,List anotherExtList)
实现这种功能方法有两个方法，首先来讲第一种方法，第一种方法是创建链表存储数据然后再拼接，先创建一个链表tempLinkedList，然后遍历要插入的anotherExtList集合，再把这个集合的元素一个一个插入到tempLinkedList里，再将tempLinkedList的首结点的prev指向index位置结点的直接前驱再把tempLinkedList的尾结点的next指向index结点，然后index结点的直接前驱的next指向tempLinkedList的首结点，最后再把这个index结点的prev指向tempLinkedList的尾结点，整个链表的长度变成size加上tempLinkedList的长度。图示如下：
具体参考代码如下：
/*将指定集合元素插入到下标index位置*/
/*方法１：构建新链表存储List数据然后整体插入*/
public void addAll(int index,List anotherExtList) {
checkElementIndex(index);
if(index==0) {
LinkedList tempLinkedList=new LinkedList();
/*先构建一个链表tempLinkedList存放anotherExtList的数据*/
for(int i=0;i<anotherExtList.size();i++) {
tempLinkedList.add(anotherExtList.get(i));
}
this.firstNode.prev=tempLinkedList.lastNode;
tempLinkedList.lastNode.next=this.firstNode;
this.firstNode=tempLinkedList.firstNode;
this.size=this.size+anotherExtList.size();
}else {
LinkedList tempLinkedList=new LinkedList();
/*先构建一个链表tempLinkedList存放anotherExtList的数据*/
for(int i=0;i<anotherExtList.size();i++) {
tempLinkedList.add(anotherExtList.get(i));
}
/*获取要插入的位置结点*/
Node tempNode=this.node(index);
/*让首结点前驱等于下标index结点的直接前驱，让尾结点后继等于下标为index的结点*/
tempLinkedList.firstNode.prev=tempNode.prev;
tempLinkedList.lastNode.next=tempNode;
tempNode.prev.next=tempLinkedList.firstNode;
tempNode.prev=tempLinkedList.lastNode;
this.size=this.size+anotherExtList.size();
}
}
第二种方式是遍历anotherExtList集合元素，遍历一个调用add(int index, Object object)方法插入一个，具体方法解析参考代码注释，代码如下：
/*将指定集合元素插入到下标index位置*/
/*方法２：循环遍历anotherExtList，把anotherExtList一个一个往index位置插入，每插入一次的同时执行一次index+1*/
public void addAll(int index,List anotherExtList) {
checkElementIndex(index);
for(int i=0;i<anotherExtList.size();i++) {
this.add(index, anotherExtList.get(i));
/*index如果不后移，接下来插入的元素是在新的index位置插入，相当于把原先的集合倒叙插入，与实际情况不符，实际情况是继续插入在原先的index的位置上*/
index++;
}
}
把另一个集合追加到本集合之后的addAll(List anotherExtList)方法
只需要遍历anotherExtList集合元素，遍历一个调用add方法添加一个即可，代码如下：
/*把另一个集合追加到本集合之后*/
public void addAll(List anotherExtList) {
// TODO Auto-generated method stub
for (int i = 0; i < anotherExtList.size(); i++) {
add(anotherExtList.get(i));
}
}
删除元素方法
removeFirst、removeLast以及remove(int index)删除指定下标元素的方法
removeFirst和removeLast方法
这两类方法很简单，由于也是LinkedList自身独有的方法，用法与addFirst和addLast相同，具体功能实现可参考代码和注释，结合自己画图便可以理解，具体代码如下：
/*移除LinkedList首元素*/
public void removeFirst() {
/*创建一个结点对象指向首结点*/
Node tempDelFirstNode=this.firstNode;
/*链表首结点对象指向原首结点的直接后继，此时原首结点的直接后继变为链表现在的首结点对象*/
this.firstNode=tempDelFirstNode.next;
/*现在的首结点的prev置为null*/
this.firstNode.prev=null;
/*将原先的首结点的next置null*/
tempDelFirstNode.next=null;
/*将原先的首结点的data置null*/
tempDelFirstNode.data=null;
/*链表长度减１*/
this.size--;
}
/*移除LinkedList尾元素*/
public void removeLast() {
/*创建一个结点对象指向尾结点*/
Node tempDelLastNode=this.lastNode;
/*链表尾结点对象指向原尾结点的直接前驱，此时原尾结点的直接前驱变为链表现在的尾结点对象*/
this.lastNode=tempDelLastNode.prev;
/*现在的尾结点的next置为null*/
this.lastNode.next=null;
/*将原先的尾结点的prev置null*/
tempDelLastNode.prev=null;
/*原先尾结点data清空*/
tempDelLastNode.data=null;
/*链表长度减１*/
this.size--;
}
remove(int index)方法
先通过node（index）方法判断index结点下标找到这个结点tempDelNode，然后通过tempDelNode.prev找到其直接前驱，让其直接前驱的next指向tempDelNode的直接后继，再让tempDelNode的直接后继的prev指向tempDelNode的直接前驱，最后让tempDelNode的data、prev和next都为null然后链表长度减1，就完成了结点的删除。图解如下
结点连接方式参考add（index，object）方法连接方式，在此不多做解释。
具体实现代码如下：
/*移除指定下标元素*/
public void remove(int index) {
// TODO Auto-generated method stub
checkElementIndex(index);
/*相当于移除首元素结点*/
if(index==0) {
this.removeFirst();
}else if(index==this.size-1) {/*相当于移除尾元素结点*/
this.removeLast();
}else {
Node tempDelNode=this.node(index);
tempDelNode.prev.next=tempDelNode.next;
tempDelNode.next.prev=tempDelNode.prev;
tempDelNode.prev=null;
tempDelNode.data=null;
tempDelNode.next=null;
this.size--;
}
}
如此，一些重要的方法就讲解完毕，其他一些简单方法请参考之后重写LinkedList类的具体代码和注释。
LinkedList重写后的具体代码
package list.ext;
import list.iface.List;
/**
* @author 作者 水寒轩
* @version 1.0
创建时间：2019年12月4日 上午9:06:34
* 类说明 重写LinkedList方法
*/
public class LinkedList implements List {
/*设计结点*/
private static class Node {
Object data;//结点中实际存放的元素数据
Node prev;//上一个结点（直接前驱）的引用
Node next;// 下一个结点（直接后继）的引用
Node(Node prev,Object data,Node next){
this.prev=prev;
this.data=data;
this.next=next;
}
}
private Node firstNode=null;//链表中的首节点
private Node lastNode=null;//链表中的尾节点
private int size=0;//链表长度
public int size() {
// TODO Auto-generated method stub
return size;
}
/*添加元素*/
public boolean add(Object object) {
// TODO Auto-generated method stub
/*添加元素的时候直接在LinkedList最后添加元素*/
this.addLast(object);
return true;
}
/*在LinkedList首元素位置添加元素*/
public void addFirst(Object object) {
// TODO Auto-generated method stub
Node node=new Node(null, object, null);
if(this.size==0) {
this.firstNode=node;
this.lastNode=node;
this.size++;
}else {
this.firstNode.prev=node;
node.next=this.firstNode;
this.firstNode=node;
this.size++;
}
}
/*在LinkedList尾元素位置添加元素*/
public void addLast(Object object) {
// TODO Auto-generated method stub
Node node=new Node(null, object, null);
if(this.size==0) {
this.addFirst(object);
}else {
this.lastNode.next=node;
node.prev=this.lastNode;
this.lastNode=node;
this.size++;
}
}
/*在指定下标处添加元素*/
public void add(int index, Object object) {
// TODO Auto-generated method stub
checkElementIndex(index);
if(index==0){
/*index=0为首元素插入结点*/
this.addFirst(object);
}else {
Node addＮode=new Node(null, object, null);
Node tempNode=node(index);
addＮode.prev=tempNode.prev;
addＮode.next=tempNode;
tempNode.prev.next=addＮode;
tempNode.prev=addＮode;
this.size++;
}
}
/*把另一个集合追加到本集合之后*/
public void addAll(List anotherExtList) {
// TODO Auto-generated method stub
for (int i = 0; i < anotherExtList.size(); i++) {
add(anotherExtList.get(i));
}
}
/*将指定集合元素插入到下标index位置*/
/*方法１：构建新链表存储List数据然后整体插入*/
public void addAll(int index,List anotherExtList) {
checkElementIndex(index);
if(index==0) {
LinkedList tempLinkedList=new LinkedList();
/*先构建一个链表tempLinkedList存放anotherExtList的数据*/
for(int i=0;i<anotherExtList.size();i++) {
tempLinkedList.add(anotherExtList.get(i));
}
this.firstNode.prev=tempLinkedList.lastNode;
tempLinkedList.lastNode.next=this.firstNode;
this.firstNode=tempLinkedList.firstNode;
this.size=this.size+anotherExtList.size();
}else {
LinkedList tempLinkedList=new LinkedList();
/*先构建一个链表tempLinkedList存放anotherExtList的数据*/
for(int i=0;i<anotherExtList.size();i++) {
tempLinkedList.add(anotherExtList.get(i));
}
/*获取要插入的位置结点*/
Node tempNode=this.node(index);
/*让首结点前驱等于下标index结点的直接前驱，让尾结点后继等于下标为index的结点*/
tempLinkedList.firstNode.prev=tempNode.prev;
tempLinkedList.lastNode.next=tempNode;
tempNode.prev.next=tempLinkedList.firstNode;
tempNode.prev=tempLinkedList.lastNode;
this.size=this.size+anotherExtList.size();
}
}
/*将指定集合元素插入到下标index位置*/
/*方法２：循环遍历anotherExtList，把anotherExtList一个一个往index位置插入，每插入一次的同时执行一次index+1*/
// public void addAll(int index,List anotherExtList) {
// checkElementIndex(index);
// for(int i=0;i<anotherExtList.size();i++) {
// this.add(index, anotherExtList.get(i));
// /*index如果不后移，接下来插入的元素是在新的index位置插入，相当于把原先的集合倒叙插入，与实际情况不符，实际情况是继续插入在原先的index的位置上*/
// index++;
// }
// }
/*移除指定下标元素*/
public void remove(int index) {
// TODO Auto-generated method stub
checkElementIndex(index);
/*相当于移除首元素结点*/
if(index==0) {
this.removeFirst();
}else if(index==this.size-1) {/*相当于移除尾元素结点*/
this.removeLast();
}else {
Node tempDelNode=this.node(index);
tempDelNode.prev.next=tempDelNode.next;
tempDelNode.next.prev=tempDelNode.prev;
tempDelNode.prev=null;
tempDelNode.data=null;
tempDelNode.next=null;
this.size--;
}
}
/*移除LinkedList首元素*/
public void removeFirst() {
/*创建一个结点对象指向首结点*/
Node tempDelFirstNode=this.firstNode;
/*链表首结点对象指向原首结点的直接后继，此时原首结点的直接后继变为链表现在的首结点对象*/
this.firstNode=tempDelFirstNode.next;
/*现在的首结点的prev置为null*/
this.firstNode.prev=null;
/*将原先的首结点的next置null*/
tempDelFirstNode.next=null;
/*将原先的首结点的data置null*/
tempDelFirstNode.data=null;
/*链表长度减１*/
this.size--;
}
/*移除LinkedList尾元素*/
public void removeLast() {
/*创建一个结点对象指向尾结点*/
Node tempDelLastNode=this.lastNode;
/*链表尾结点对象指向原尾结点的直接前驱，此时原尾结点的直接前驱变为链表现在的尾结点对象*/
this.lastNode=tempDelLastNode.prev;
/*现在的尾结点的next置为null*/
this.lastNode.next=null;
/*将原先的尾结点的prev置null*/
tempDelLastNode.prev=null;
/*原先尾结点data清空*/
tempDelLastNode.data=null;
/*链表长度减１*/
this.size--;
}
/*清空LinkedList*/
public void clear() {
// TODO Auto-generated method stub
/*遍历链表挨个清空*/
for(Node node=this.firstNode;node!=null;) {
/*创建一个结点对象指向当前结点的直接后继*/
Node next=node.next;
/*把当前结点清空*/
node.prev=null;
node.data=null;
node.next=null;
node=next;
}
this.firstNode=this.lastNode=null;
this.size=0;
}
// /*根据下标找节点：从头遍历*/
// private Node node(int index) {
// //先判断index是否合法
// checkElementIndex(index);
// int tag=0;
// /*用来循环统计在链表中从头查找结点所经历的结点个数
// 也可以理解为是手动给结点做下标，
// 比如查第一个结点经历了０个结点，所以第一个结点的tag是０；
// 查找第二个结点经历了１个结点，所以第二个结点的tag是１以此类推，
// 可以理解成结点的下标*/
// Node tempNode=null;//用来指向查找到的结点返回
// /*从首结点往后遍历*/
// for(Node n=this.firstNode;n!=null;n=n.next) {
// /*判断查找的第几个结点是index*/
// if(tag==index) {
// temp=n;
// break;
// }
// tag++;
// }
// return temp;
// }
/*根据下标找节点：二分法查找*/
/*优点：是从头查找的普通方法的时间复杂度的一半，程序效率是普通从头遍历方法的二倍*/
private Node node(int index) {
//先判断index是否合法
checkElementIndex(index);
/*集合长度右移一位，相当于除以２*/
// 从效率上看，使用移位指令有更高的效率，因为移位指令占2个机器周期，而乘除法指令占4个机器周期。
// 从硬件上看，移位对硬件更容易实现，所以会用移位
if(index<(size>>1)) {
/*前半部分从头找*/
Node node=this.firstNode;
for(int i=0;i<index;i++) {
node=node.next;
}
return node;
}else {
/*后半部分从末尾找*/
Node node=this.lastNode;
for(int i=size-1;i>index;i--) {
node=node.prev;
}
return node;
}
/*根据下标获取链表元素*/
public Object get(int index) {
/*先调用node(index)方法，根据下标查找节点，再返回节点的值*/
return this.node(index).data;
}
/*返回数组对象*/
public Object[] toArray() {
// TODO Auto-generated method stub
Object[] result = new Object[this.size];
int i = 0;
for (Node x = this.firstNode; x != null; x = x.next)
result[i++] = x.data;
return result;
}
/*打印输出集合中元素的值*/
public void printList() {
// TODO Auto-generated method stub
String msg = "｛";
for (int i = 0; i < this.size; i++) {
msg += this.get(i);
if (i < this.size - 1) {
msg += ", ";
}
}
msg += "｝";
System.out.println(msg);
}
/*在LinkedList中查找指定下标元素，修改元素值*/
public void set(int index, Object object) {
// TODO Auto-generated method stub
checkElementIndex(index);
this.node(index).data=object;
}
/*调用isElementIndex方法，判断输入下标是否合法，不合法时抛出异常*/
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+this.size);
}
/*判断输入下标是否合法，供checkElementIndex方法调用，不合法时由checkElementIndex方法抛出异常*/
private boolean isElementIndex(int index) {
/*表达式index >= 0 && index < size成立返回true，不成立返回false*/
return index >= 0 && index < size;
}
}
重写后LinkedList类方法的测试类LinkedListTest
代码
package list.iface.LinkedListInterface;
import org.junit.Test;
import list.ext.LinkedList;
import list.iface.List;
/**
* @author 作者 水寒轩
* @version 1.0
创建时间：2019年12月4日 下午12:04:40
* 类说明
*/
public class LinkedListTest {
/*添加首元素*/
@Test
public void addFirst() {
LinkedList list=new LinkedList();
for(int i=0;i<5;i++) {
list.addFirst(i);
}
list.printList();
}
/*添加尾元素*/
@Test
public void addLast() {
LinkedList list=new LinkedList();
for(int i=0;i<5;i++) {
list.add(i);
}
list.printList();
System.out.println();
list.addLast(6);
list.printList();
}
/*添加元素*/
@Test
public void add() {
List list=new LinkedList();
for(int i=0;i<5;i++) {
list.add(i);
list.printList();
}
}
/*在指定下标处添加元素*/
@Test
public void addIndex() {
List list = new LinkedList();
for (int i = 0; i < 12; i++) {
list.add(i);
}
list.printList();
list.add(6, "测试元素");
// list.add(12, "测试元素");//测试非法下标
System.out.println();
list.printList();
}
/*将一个集合添加到Linkedlist中去*/
@Test
public void addAll() {
List list = new LinkedList();
for (int i = 0; i < 12; i++) {
list.add(i);
}
list.printList();
System.out.println();
List list1=new LinkedList();
for(int i=23;i<29;i++) {
list1.add(i);
}
list1.printList();
System.out.println();
list1.addAll(list);
System.out.println();
list1.printList();
}
/*将一个list集合添加到一个LinkedList集合指定的下标处*/
/*方法１：构建新链表存储List集合数据然后整体插入*/
@Test
public void addAll01() {
/*这里其实只要是List类型集合都可以实现，但是由于我重写了List接口，
同时只重写了LinkedList类而没有重写ArraysList类，所以无法用ArraysList类型集合测试*/
List list = new LinkedList();
for (int i = 0; i < 12; i++) {
list.add(i);
}
list.printList();
System.out.println();
List list1=new LinkedList();
for(int i=23;i<29;i++) {
list1.add(i);
}
list1.printList();
System.out.println();
list1.addAll(3, list);
list1.printList();
}
/*将一个list集合添加到一个LinkedList集合指定的下标处*/
/*方法２：循环遍历list集合，把list集合的数据一个一个往LinkedList集合的index位置插入，插入一次，执行index+1*/
@Test
public void addAll02() {
/*这里其实只要是List类型集合都可以实现，但是由于我重写了List接口，
同时只重写了LinkedList类而没有重写ArraysList类，所以无法用ArraysList类型集合测试*/
List list = new LinkedList();
for (int i = 0; i < 12; i++) {
list.add(i);
}
list.printList();
System.out.println();
List list1=new LinkedList();
for(int i=23;i<29;i++) {
list1.add(i);
}
list1.printList();
System.out.println();
list1.addAll(3, list);
list1.printList();
}
/*移除指定下标元素*/
@Test
public void remove() {
List list = new LinkedList();
for (int i = 0; i < 12; i++) {
list.add(i);
}
list.printList();
System.out.println();
list.remove(5);
System.out.println();
list.printList();
}
/*移除首元素*/
@Test
public void removeFirst() {
LinkedList list = new LinkedList();
for (int i = 0; i < 12; i++) {
list.add(i);
}
list.printList();
System.out.println();
list.removeFirst();
System.out.println();
list.printList();
}
/*移除尾元素*/
@Test
public void removeLast() {
LinkedList list = new LinkedList();
for (int i = 0; i < 12; i++) {
list.add(i);
}
list.printList();
System.out.println();
list.removeLast();
System.out.println();
list.printList();
}
/*清空集合*/
@Test
public void clear() {
LinkedList list = new LinkedList();
for (int i = 0; i < 12; i++) {
list.add(i);
}
list.printList();
System.out.println();
list.clear();
System.out.println();
list.printList();
}
/*返回数组对象*/
@Test
public void toArray() {
List list = new LinkedList();
for (int i = 0; i < 12; i++) {
list.add(i);
}
Object[] array = list.toArray();
for (Object object : array) {
System.out.println(object);
}
}
/*在LinkedList中查找指定下标元素，修改元素值*/
@Test
public void set() {
List list = new LinkedList();
for (int i = 0; i < 12; i++) {
list.add(i);
}
list.printList();
list.set(6, "测试元素");
list.printList();
}
}
总结
至此，Java简单重写JDK中双向链表结构的LinkedList方法详解到此结束。关于本文章从文字到代码都是我一个字一个字码的，图片是用画图自己动手一个一个画的，画的不好，有空会专门学习下专业的画图软件，完成文章花费时间挺长，属实不易，第一次写文章，没什么经验，不喜勿喷，不足之处还望各位大佬在评论区予以指正，同时也欢迎各路大佬进行技术交流，如若转载请注明出处。
上一篇： 第十一章：串
下一篇： Java中的构造方法