摘要:記得在一個公司面試上有一道題,寫一個雙向鏈表,包含鏈表的基本操作,插入,刪除,獲取長度等操作,由于時間匆忙,代碼寫的比較亂,連自己都沒眼看了,后來細想自己從來都沒有細心的寫過數據結構,總覺得只要原理明白了就萬事大吉了,事實證明,理論和實踐還
記得在一個公司面試上有一道題,寫一個雙向鏈表,包含鏈表的基本操作,插入,刪除,獲取長度等操作,由于時間匆忙,代碼寫的比較亂,連自己都沒眼看了,后來細想自己從來都沒有細心的寫過數據結構,總覺得只要原理明白了就萬事大吉了,事實證明,理論和實踐還是有很大差距的。
水平有限,如果有錯誤,還請不吝賜教
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; }雙向鏈表的關鍵在于節點指針的轉移
下面以removeElement(E value)為例簡單介紹
public void removeElement(E value){ Node index=this.first;//創建index節點指向first節點 while(index!=null){ if(index.e==value)break; index=index.next; }//while循環用于遍歷整個鏈表來獲取指向要刪除的節點指針 index.previous.next=index.next; index.next.previous=index.previous; length--; }
index.previous表示要刪除節點的前驅節點
index.previous.next=index.next;意思是將前驅節點的后項指針指向要刪除節點的后繼節點
同理index.next表示要刪除節點的后繼節點
index.next.previous=index.previous;意思是將后繼節點的前向指針指向要刪除節點的前驅節點
可能有點繞,簡單畫個鏈表結構圖就可以很明了了
insertNext(E baseElement,E value)和insertPrevious(E baseElement,E value)同理,這里不再贅述
DoubleLinkedList包含兩個節點指針(偽指針,java中沒有指針的概念)first和last,分別指向鏈表的第一個元素和最后一個元素
整體代碼public class DoubleLinkedList如果不太了解雙向鏈表的結構可以在紙上畫出每個Node以及指向關系{ 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; } } /*** * 向頭節點添加元素,節點結構對外應該是不可見的,所以這里只傳遞一個泛型的值e */ public void addFirst(E e) { if (first == null) {//鏈表為空判斷 Node node = new Node(null, null, e);//創建一個新的節點,前驅和后繼都為空 this.first = node; this.last=node;//將first和last指針指向鏈表的第一個元素 length++;//鏈表長度自增一,下同 }else{ Node node=new Node(null,first,e);//鏈表不為空創建一個前驅為空,后繼為當前first節點的節點,值為傳入的參數e this.first.previous=node;//當前first的前驅設置為node this.first=node;//將first指針指向新節點 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 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()); } }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/66831.html
摘要:底層基于拉鏈式的散列結構,并在中引入紅黑樹優化過長鏈表的問題。在其之上,通過維護一條雙向鏈表,實現了散列數據結構的有序遍歷。 原文地址 LinkedHashMap LinkedHashMap繼承自HashMap實現了Map接口。基本實現同HashMap一樣,不同之處在于LinkedHashMap保證了迭代的有序性。其內部維護了一個雙向鏈表,解決了 HashMap不能隨時保持遍歷順序和插...
摘要:若遇到哈希沖突,則將沖突的值加到鏈表中即可。之后相比于之前的版本,之后在解決哈希沖突時有了較大的變化,當鏈表長度大于閾值默認為時,將鏈表轉化為紅黑樹,以減少搜索時間。有序,唯一紅黑樹自平衡的排序二叉樹。 本文是最最最常見Java面試題總結系列第三周的文章。主要內容: Arraylist 與 LinkedList 異同 ArrayList 與 Vector 區別 HashMap的底層...
閱讀 4361·2021-11-22 09:34
閱讀 2690·2021-11-12 10:36
閱讀 742·2021-08-18 10:23
閱讀 2636·2019-08-30 15:55
閱讀 3111·2019-08-30 15:53
閱讀 2081·2019-08-30 15:44
閱讀 1361·2019-08-29 15:37
閱讀 1401·2019-08-29 13:04