Java实现双向链表(两个版本)
临近春节，项目都结束了，都等着回家过年了。下面是小编给大家研究数据结构的相关知识，链表算是经常用到的一种数据结构了，现将自己的实现展示如下，欢迎大神赐教。
第一个版本，没有最后一个节点，每次从根节点开始遍历
publicclassLinkedList<E>{
privateNodehead;
publicLinkedList(){
}
publicEgetFirst(){
if(head==null){
returnnull;
}
returnhead.value;
}
publicLinkedList<E>addFirst(Ee){
head.pre=newNode(e,null,head);
head=head.pre;
returnthis;
}
publicLinkedList<E>addNode(Ee){
Nodelst=head;
if(lst==null){
this.head=newNode(e,null,null);
returnthis;
}else{
while(true){
if(lst.next==null){
break;
}else{
lst=lst.next;
}
}
lst.next=newNode(e,lst,null);
returnthis;
}
}
publicLinkedList<E>remove(Ee){
Nodelst=head;
if(lst==null){
thrownewNullPointerException("theLinkedListisempty.");
}else{
while(true){
if(e.equals(lst.value)){
//移除这个元素
if(lst.pre!=null){
lst.pre.next=lst.next;
}
if(lst.next!=null){
lst.next.pre=lst.pre;
}
lst=null;
break;
}
lst=lst.next;
}
returnthis;
}
}
@Override
publicStringtoString(){
StringBufferbuff=newStringBuffer("[");
Nodelst=this.head;
while(lst!=null){
buff.append(lst.value+",");
lst=lst.next;
}
returnbuff.substring(0,buff.length()-1)+"]";
}
/**节点信息*/
privateclassNode{
publicNodepre;
publicEvalue;
publicNodenext;
publicNode(Evalue,Nodepre,Nodenext){
this.value=value;
this.pre=pre;
this.next=next;
}
}
}
第二个版本，有了最后一个节点
publicclassLinkedList<E>{
privateNodehead;
privateNodelast;
publicLinkedList(){
}
publicEgetFirst(){
if(head==null){
returnnull;
}
returnhead.value;
}
publicEgetLast(){
if(last==null){
returnnull;
}
returnlast.value;
}
publicLinkedList<E>addFirst(Ee){
head.pre=newNode(e,null,head);
head=head.pre;
returnthis;
}
publicLinkedList<E>addNode(Ee){
Nodelst=last;
if(lst==null){//如果最后一个节点是空的则这个链表就是空的
this.last=newNode(e,null,null);
this.head=this.last;
returnthis;
}else{
while(true){
if(lst.next==null){//
break;
}else{
lst=lst.next;
}
}
lst.next=newNode(e,lst,null);
last=lst.next;
returnthis;
}
}
publicLinkedList<E>remove(Ee){
Nodelst=head;
if(lst==null){
thrownewNullPointerException("theLinkedListisempty.");
}else{
while(true){
if(e.equals(lst.value)){
//移除这个元素
if(lst.pre!=null){
lst.pre.next=lst.next;
}
if(lst.next!=null){
lst.next.pre=lst.pre;
}
lst=null;
break;
}
lst=lst.next;
}
returnthis;
}
}
@Override
publicStringtoString(){
StringBufferbuff=newStringBuffer("[");
Nodelst=this.head;
while(lst!=null){
buff.append(lst.value+",");
lst=lst.next;
}
returnbuff.substring(0,buff.length()-1)+"]";
}
/**节点信息*/
privateclassNode{
publicNodepre;
publicEvalue;
publicNodenext;
publicNode(Evalue,Nodepre,Nodenext){
this.value=value;
this.pre=pre;
this.next=next;
}
}
}
注：以上两个版本都没有考虑在多线程下使用的情况。
以上所述是小编给大家介绍的Java实现双向链表(两个版本)的相关知识，希望对大家有所帮助。