記得在一個公司面試上有一道題备典，寫一個雙向鏈表异旧，包含鏈表的基本操作，插入提佣，刪除吮蛹，獲取長度等操作，由于時間匆忙拌屏，代碼寫的比較亂潮针，連自己都沒眼看了，后來細想自己從來都沒有細心的寫過數(shù)據(jù)結(jié)構(gòu)倚喂，總覺得只要原理明白了就萬事大吉了每篷，事實證明，理論和實踐還是有很大差距的务唐。
水平有限雳攘，如果有錯誤，還請不吝賜教
定義一個內(nèi)部類Node用于存儲節(jié)點元素
class Node {
private Node previous;//前驅(qū)節(jié)點
private Node next;//后繼節(jié)點
private E e;//泛型元素值
public Node(Node previous, Node next, E e) {
this.previous = previous;
this.next = next;
this.e = e;
}
雙向鏈表的關(guān)鍵在于節(jié)點指針的轉(zhuǎn)移
下面以removeElement(E value)為例簡單介紹
public void removeElement(E value){
Node index=this.first;//創(chuàng)建index節(jié)點指向first節(jié)點
while(index!=null){
if(index.e==value)break;
index=index.next;
}//while循環(huán)用于遍歷整個鏈表來獲取指向要刪除的節(jié)點指針
index.previous.next=index.next;
index.next.previous=index.previous;
length--;
}
index.previous表示要刪除節(jié)點的前驅(qū)節(jié)點
index.previous.next=index.next;意思是將前驅(qū)節(jié)點的后項指針指向要刪除節(jié)點的后繼節(jié)點
同理index.next表示要刪除節(jié)點的后繼節(jié)點
index.next.previous=index.previous;意思是將后繼節(jié)點的前向指針指向要刪除節(jié)點的前驅(qū)節(jié)點
可能有點繞枫笛，簡單畫個鏈表結(jié)構(gòu)圖就可以很明了了
insertNext(E baseElement,E value)和insertPrevious(E baseElement,E value)同理吨灭，這里不再贅述
DoubleLinkedList包含兩個節(jié)點指針（偽指針，java中沒有指針的概念）first和last刑巧，分別指向鏈表的第一個元素和最后一個元素
整體代碼
public class DoubleLinkedList<E> {
private Node first;//指向第一個元素
private Node last;//指向最后一個元素
private int length=0;//鏈表長度
class Node {
private Node previous;
private Node next;
private E e;
public Node(Node previous, Node next, E e) {
this.previous = previous;
this.next = next;
this.e = e;
}
}
/***
* 向頭節(jié)點添加元素喧兄，節(jié)點結(jié)構(gòu)對外應(yīng)該是不可見的，所以這里只傳遞一個泛型的值e
*/
public void addFirst(E e) {
if (first == null) {//鏈表為空判斷
Node node = new Node(null, null, e);//創(chuàng)建一個新的節(jié)點啊楚，前驅(qū)和后繼都為空
this.first = node;
this.last=node;//將first和last指針指向鏈表的第一個元素
length++;//鏈表長度自增一吠冤，下同
}else{
Node node=new Node(null,first,e);//鏈表不為空創(chuàng)建一個前驅(qū)為空，后繼為當前first節(jié)點的節(jié)點恭理，值為傳入的參數(shù)e
this.first.previous=node;//當前first的前驅(qū)設(shè)置為node
this.first=node;//將first指針指向新節(jié)點
length++;
}
}
/***
*addLast同addFirst
*/
public void addLast(E e) {
if (last == null) {
Node node = new Node(null, null, e);
this.first = node;
this.last=node;
length++;
}else{
Node node=new Node(last,null,e);
this.last.next=node;
this.last=node;
length++;
}
}
public void insertPrevious(E baseElement,E value){
Node index=this.first;
while(index!=null){
if(index.e==baseElement)break;
index=index.next;
}
Node insertValue=new Node(index.previous,index,value);
index.previous.next=insertValue;
index.previous=insertValue;
length++;
}
public void insertNext(E baseElement,E value){
Node index=this.first;
while(index!=null){
if(index.e==baseElement)break;
index=index.next;
}
Node insertValue=new Node(index,index.next,value);
index.next.previous=insertValue;
index.next=insertValue;
length++;
}
public void removeElement(E value){
Node index=this.first;
while(index!=null){
if(index.e==value)break;
index=index.next;
}
index.previous.next=index.next;
index.next.previous=index.previous;
length--;
}
public int getLength(){
return length;
}
@Override
public String toString() {
StringBuffer sb=new StringBuffer();
Node current=this.first;
while(current!=null){
sb.append(current.e+"->");
current=current.next;
}
return sb.toString();
}
public static void main(String[] args) {
DoubleLinkedList<String> list=new DoubleLinkedList<>();
list.addLast("value1");
list.addLast("value2");
list.addLast("value3");
list.addLast("value4");
list.addFirst("value0");
list.insertPrevious("value3","insertValue");
list.insertNext("value3","insertValue2");
System.out.println(list.toString());
System.out.println("鏈表的長度是"+list.getLength());
list.removeElement("value3");
System.out.println(list.toString());
System.out.println("鏈表的長度是"+list.getLength());
}
}
