DoubleLinkedList独立实现，不依赖任何包

精彩继续，实现完SingleLinkedList之后，今天又实现了双向链接表，代码如下：

publicclassDoubleLinkedList< E>{

classNode< E>{

E element;
Node prev;
Node next;

publicNode( Eelement){
//constructorwithargs
this. element=element;
}

publicNode(){
//constructorwithoutargs
}

@Override
publicStringtoString(){
returnthis. element.toString();
}
}

privateNode first= null;
privateNode last= null;

/**
*链接结点到链表首部
* @param node
*/
privatevoidlinkFirst(Nodenode){
if( first== null|| last== null){
first= last=node;
}
node. next= first;
first. prev=node;
first=node;
}

/**
*链接结点到链表尾部
* @param node
*/
privatevoidlinkLast(Nodenode){
last. next=node;
node. prev= last;
last=node;
}

/**
*链接一个结点到链表中间
* @param node1 要链接的结点
* @param node2 链接点位置的结点
*example:
* [插入前]node->node2->node3
* [插入后]node->node1->node2->node3
*/
privatevoidlink(Nodenode1,Nodenode2){
Nodenode=node2. prev;
node. next=node1;
node1. prev=node;
node1. next=node2;
node2. prev=node1;

}

/**
*移除某个节点
* @param node
*/
publicvoidunlink(Nodenode){
NodeprevNode=node. prev;
NodenextNode=node. next;
prevNode. next=nextNode;
nextNode. prev=prevNode;
}

/**
*移除首结点
*/
privatevoidunlinkFirst(){
first= first. next;
first. prev= null;
}

/**
*移除尾结点
*/
privatevoidunlinkLast(){
last= last. prev;
last. next= null;
}

/**
*根据索引获取结点
* @param index
* @return
*/
privateNodegetNode( intindex){
Nodenode= first;
NodecurrentNode= newNode();
if(index== 0){
currentNode= first;
}

if(index>=size()){
thrownewIndexOutOfBoundsException(errMessage(index));
}
else{
inti= 0;
while(i<=index){
if(node!= null){
currentNode=node;
node=node. next;
}
i++;
}
}
returncurrentNode;

}

/**
*统计链表里面所有元素的个数
* @return 总的元素的个数
*/
publicintsize(){
Nodenode= first;
intcount= 0;
while(node!= null){
count++;
node=node. next;
}
returncount;
}

/**
*错误消息显示
* @param index
* @return
*/
privateStringerrMessage( intindex){
return "Size:"+size()+ ",index:"+index;
}

/**
*插入元素到链表中
* @param index
* @param element
*/
publicvoidinsert( intindex,Eelement){
Nodenode= newNode< E>(element);
if(index== 0){
linkFirst(node);
}
if(index< 0||index>=size()){
thrownewIndexOutOfBoundsException(errMessage(index));
}
if(index==size()- 1){
linkLast(node);
}
else{
Nodenode1=getNode(index);
link(node,node1);
}

}

/**
*添加元素到链表
* @param element
*/
publicvoidadd( Eelement){
Nodenode= newNode< E>(element);
linkFirst(node);
}

/**
*添加元素到链表首部
* @param element
*/
publicvoidaddFirst( Eelement){
Nodenode= newNode< E>(element);
linkFirst(node);
}

/**
*添加元素到链表尾部
* @param element
*/
publicvoidaddLast( Eelement){
Nodenode= newNode< E>(element);
linkLast(node);
}

/**
*移除指定索引下得元素
* @param index
*/
publicvoidremove( intindex){
if(index== 0){
unlinkFirst();
}
elseif(index==size()- 1){
unlinkLast();
}
elseif(index< 0||index>=size()){
thrownewIndexOutOfBoundsException(errMessage(index));
}
else{
Nodenode=getNode(index);
unlink(node);
}
}

/**
*移除最后一个元素
*/
publicvoidremoveLast(){
unlinkLast();
}

/**
*移除第一个元素
*/
publicvoidremoveFirst(){
unlinkFirst();
}

/**
*清空链表
*/
publicvoidclear(){
first= null;
}

/**
*判断链表是否为空
* @return
*/
publicbooleanisEmpty(){
return first== null;
}

/**
*重载toString方法
* @return
*/
@Override
publicStringtoString(){
Nodenode= first;
StringBuilderstringBuilder= newStringBuilder();
if(node== null){
return "{}";
}
else{
stringBuilder.append( "{");
while(node!= null){
stringBuilder.append( "["+node.toString()+ "],");
node=node. next;
}
}
Stringresult=stringBuilder.toString();
intindex=result.lastIndexOf( ",");
returnresult.substring( 0,index)+ "}";
}

/**
*判断某个元素是否在链表中
* @param element
* @return
*/
publicbooleancontains( Eelement){
returngetIndexOf(element)!=- 1;
}

/**
*获取一个元素
* @param index
* @return
*/
public Eget( intindex){
return( E)getNode(index). element;
}

/**
*获取最后一个元素
* @return
*/
public EgetLast(){
return( E) last. element;
}

/**
*获取第一个元素
* @return
*/
public EgetFirst(){
return( E) first. element;
}

/**
*替换特定索引的元素
* @param index
* @param element
*/
publicvoidreplace( intindex,Eelement){
getNode(index). element=element;
}

/**
*获取某个元素的索引,这里通常是第一次出现的索引
* @param element
* @return
*/
publicintgetIndexOf( Eelement){
intindex= 0;
if(element== null){
for(Node< E>node= first;node!= null;node=node. next){
if(node. element== null){
returnindex;
}
index++;
}
}
else{
for(Node< E>node= first;node!= null;node=node. next){
if(node. element.equals(element)){
returnindex;
}
index++;
}
}
return- 1;
}

/**
*获取某个元素最后一次出现的索引
* @param element
* @return
*/
publicintgetLastIndexOf( Eelement){
intindex=size();
if(element== null){
for(Node< E>node= last;node!= null;node=node. prev){
index--;
if(node. element== null){
returnindex;
}
}
}
else{
for(Node< E>node= last;node!= null;node=node. prev){
index--;
if(node. element.equals(element)){
returnindex;
}
}
}
return- 1;
}

/**
*移除某个元素第一次出现的位置
* @param element
*/
publicvoidremoveFirstOccurrence( Eelement){
if(element== null){
return;
}
intindex=getIndexOf(element);
remove(index);

}

/**
*移除某个元素最后一次出现的位置
* @param element
*/
publicvoidremoveLastOccurrence( Eelement){
if(element== null){
return;
}
intindex=getLastIndexOf(element);
remove(index);
}

}

测试代码：

publicclassTestDoubleLinkedList{

publicstaticvoidmain(String[]args){

DoubleLinkedList<User>list= newDoubleLinkedList<User>();
list.add( newUser( 15,"Amy","Girl"));
list.add( newUser( 14,"Tony","Boy"));
list.add( newUser( 17,"Masha","Girl"));
list.addLast( newUser( 20,"Shabby","Boy"));
list.addFirst( newUser( 11,"Sasa","Boy"));
//System.out.println(list.contains(newUser(14,"Tony","Boy")));
//list.removeFirst();
//list.removeLast();
//list.removeLastOccurrence(newUser(14,"Boy"));
//System.out.println(list.getLastIndexOf(newUser(14,"Boy")));
System. out.println(list.get( 4));
System. out.println(list.toString());
}

}

以上测试代码，所有功能均通过测试。完成！