欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java數(shù)據(jù)結構之鏈表(動力節(jié)點之Java學院整理)

 更新時間:2017年04月14日 10:01:29   投稿:mrr  
這篇文章主要介紹了Java數(shù)據(jù)結構之鏈表(動力節(jié)點之Java學院整理)的相關資料,需要的朋友可以參考下

單鏈表:

insertFirst:在表頭插入一個新的鏈接點,時間復雜度為O(1)

deleteFirst:刪除表頭的鏈接點,時間復雜度為O(1)

find:查找包含指定關鍵字的鏈接點,由于需要遍歷查找,平均需要查找N/2次,即O(N)

remove:刪除包含指定關鍵字的鏈接點,由于需要遍歷查找,平均需要查找N/2次,即O(N) 

public class LinkedList { 
   private class Data{ 
     private Object obj; 
     private Data next = null;       
     Data(Object obj){ 
       this.obj = obj; 
     } 
   } 
   private Data first = null; 
    
   public void insertFirst(Object obj){ 
     Data data = new Data(obj); 
     data.next = first; 
     first = data; 
   } 
   public Object deleteFirst() throws Exception{ 
     if(first == null) 
       throw new Exception("empty!"); 
     Data temp = first; 
     first = first.next; 
     return temp.obj; 
   }     
   public Object find(Object obj) throws Exception{ 
     if(first == null) 
       throw new Exception("LinkedList is empty!"); 
     Data cur = first; 
     while(cur != null){ 
       if(cur.obj.equals(obj)){ 
         return cur.obj; 
       } 
       cur = cur.next; 
     } 
     return null; 
   } 
   public void remove(Object obj) throws Exception{ 
     if(first == null) 
       throw new Exception("LinkedList is empty!"); 
     if(first.obj.equals(obj)){ 
       first = first.next; 
     }else{ 
       Data pre = first; 
       Data cur = first.next; 
       while(cur != null){ 
         if(cur.obj.equals(obj)){ 
           pre.next = cur.next; 
         } 
        pre = cur; 
         cur = cur.next; 
       } 
     } 
   } 
   public boolean isEmpty(){ 
     return (first == null); 
   } 
   public void display(){ 
     if(first == null) 
       System.out.println("empty"); 
     Data cur = first; 
     while(cur != null){ 
       System.out.print(cur.obj.toString() + " -> "); 
       cur = cur.next; 
     } 
     System.out.print("\n"); 
   }     
   public static void main(String[] args) throws Exception { 
     LinkedList ll = new LinkedList(); 
     ll.insertFirst(4); 
     ll.insertFirst(3); 
     ll.insertFirst(2); 
     ll.insertFirst(1); 
     ll.display(); 
     ll.deleteFirst(); 
     ll.display(); 
     ll.remove(3); 
     ll.display(); 
     System.out.println(ll.find(1)); 
     System.out.println(ll.find(4)); 
   } 
 } 
 1 -> 2 -> 3 -> 4 ->  
 2 -> 3 -> 4 ->  
 2 -> 4 ->  
 null 
 4 

雙端鏈表(不是雙向鏈表):

與單向鏈表的不同之處在保存有對最后一個鏈接點的引用(last)

insertFirst:在表頭插入一個新的鏈接點,時間復雜度O(1)

insertLast:在表尾插入一個新的鏈接點,時間復雜度O(1)

deleteFirst:刪除表頭的鏈接點,時間復雜度O(1)

deleteLast::刪除表尾的鏈接點,由于只保存了表尾的鏈接點,而沒有保存表尾的前一個鏈接點(這里就體現(xiàn)出雙向鏈表的優(yōu)勢了),所以在刪除表尾鏈接點時需要遍歷以找到表尾鏈接點的前一個鏈接點,需查找N-1次,也就是O(N)
有了這幾個方法就可以用雙端鏈表來實現(xiàn)一個隊列了

 public class FirstLastList { 
   private class Data{ 
     private Object obj; 
     private Data next = null;       
     Data(Object obj){ 
       this.obj = obj; 
     } 
   }     
   private Data first = null; 
   private Data last = null;     
   public void insertFirst(Object obj){ 
     Data data = new Data(obj); 
     if(first == null) 
       last = data; 
     data.next = first; 
     first = data; 
   }     
   public void insertLast(Object obj){ 
     Data data = new Data(obj); 
     if(first == null){ 
       first = data; 
     }else{ 
       last.next = data;   
     } 
     last = data; 
   }     
   public Object deleteFirst() throws Exception{ 
      if(first == null) 
       throw new Exception("empty"); 
      Data temp = first; 
      if(first.next == null) 
       last = null; 
      first = first.next; 
      return temp.obj; 
  }   
   public void deleteLast() throws Exception{ 
     if(first == null) 
       throw new Exception("empty"); 
     if(first.next == null){ 
       first = null; 
       last = null; 
     }else{ 
       Data temp = first; 
       while(temp.next != null){ 
         if(temp.next == last){ 
           last = temp; 
           last.next = null; 
           break; 
        } 
        temp = temp.next; 
      } 
     } 
   } 
   public void display(){ 
     if(first == null) 
       System.out.println("empty"); 
     Data cur = first; 
     while(cur != null){ 
       System.out.print(cur.obj.toString() + " -> "); 
       cur = cur.next; 
     } 
     System.out.print("\n"); 
   } 
   public static void main(String[] args) throws Exception { 
     FirstLastList fll = new FirstLastList(); 
     fll.insertFirst(2); 
     fll.insertFirst(1); 
     fll.display(); 
     fll.insertLast(3); 
     fll.display(); 
     fll.deleteFirst(); 
     fll.display(); 
     fll.deleteLast(); 
     fll.display(); 
   } 
 } 
 1 -> 2 ->  
 1 -> 2 -> 3 ->  
 2 -> 3 ->  
 2 -> 

有序鏈表:

鏈表中的數(shù)據(jù)按從小到大排列

public class SortedList { 
   private class Data{ 
     private Object obj; 
     private Data next = null;       
     Data(Object obj){ 
       this.obj = obj; 
     } 
   }   
   private Data first = null;     
   public void insert(Object obj){ 
     Data data = new Data(obj); 
     Data pre = null; 
     Data cur = first; 
     while(cur != null && (Integer.valueOf(data.obj.toString()) 
        .intValue() > Integer.valueOf(cur.obj.toString()) 
         .intValue())){ 
       pre = cur; 
      cur = cur.next; 
     } 
     if(pre == null) 
       first = data; 
     else 
       pre.next = data; 
     data.next = cur; 
   }     
   public Object deleteFirst() throws Exception{ 
     if(first == null) 
       throw new Exception("empty!"); 
     Data temp = first; 
     first = first.next; 
     return temp.obj; 
   }     
   public void display(){ 
     if(first == null) 
       System.out.println("empty"); 
     System.out.print("first -> last : "); 
     Data cur = first; 
     while(cur != null){ 
       System.out.print(cur.obj.toString() + " -> "); 
       cur = cur.next; 
     } 
     System.out.print("\n"); 
   }     
   public static void main(String[] args) throws Exception{ 
     SortedList sl = new SortedList(); 
     sl.insert(80); 
     sl.insert(2); 
     sl.insert(100); 
     sl.display(); 
     System.out.println(sl.deleteFirst()); 
     sl.insert(33); 
     sl.display(); 
     sl.insert(99); 
     sl.display(); 
   } 
 } 
 first -> last : 2 -> 80 -> 100 ->  
 2 
 first -> last : 33 -> 80 -> 100 ->  
 first -> last : 33 -> 80 -> 99 -> 100 -> 

表的插入和刪除平均需要比較N/2次,即O(N),但是獲取最小數(shù)據(jù)項只需O(1),因為其始終處于表頭,對頻繁操作最小數(shù)據(jù)項的應用,可以考慮使用有序鏈表實現(xiàn),如:優(yōu)先級隊列和數(shù)組相比,鏈表的優(yōu)勢在于長度不受限制,并且在進行插入和刪除操作時,不需要移動數(shù)據(jù)項,故盡管某些操作的時間復雜度與數(shù)組想同,實際效率上還是比數(shù)組要高很多。劣勢在于隨機訪問,無法像數(shù)組那樣直接通過下標找到特定的數(shù)據(jù)項 。

以上所述是小編給大家介紹的Java數(shù)據(jù)結構之鏈表(動力節(jié)點之Java學院整理),希望對大家有所幫助,如果大家有任何疑問請給我留言,小編會及時回復大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持!

相關文章

  • Sprint Boot 集成MongoDB的操作方法

    Sprint Boot 集成MongoDB的操作方法

    最近接手一個Springboot項目,需要在原項目上增加一些需求,用到了mongodb。下面通過本文給大家分享Sprint Boot 集成MongoDB的操作方法,需要的朋友參考下吧
    2017-12-12
  • 全面解析Java中的引用類型

    全面解析Java中的引用類型

    在Java中對象以引用來指向JVM的內存區(qū)塊,這里我們總結了強引用、軟引用、弱引用和假象引用(幽靈引用),下面就具體來全面解析Java中的引用類型:
    2016-05-05
  • Java中用Socket實現(xiàn)HTTP文件上傳實例

    Java中用Socket實現(xiàn)HTTP文件上傳實例

    本篇文章主要介紹了Java中用Socket實現(xiàn)HTTP文件上傳實例,詳細的介紹了通過讀取Socket的輸入流來實現(xiàn)一個文件上傳的功能,有興趣的同學可以一起了解一下
    2017-04-04
  • Java System.exit()退出程序方式

    Java System.exit()退出程序方式

    這篇文章主要介紹了Java System.exit()退出程序方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2024-06-06
  • 云服務器環(huán)境搭建及部署(jdk、mysql、redis、nginx環(huán)境搭建)詳細步驟

    云服務器環(huán)境搭建及部署(jdk、mysql、redis、nginx環(huán)境搭建)詳細步驟

    這篇文章主要給大家介紹了關于云服務器環(huán)境搭建及部署(jdk、mysql、redis、nginx環(huán)境搭建)詳細步驟的相關資料,要在云服務器上搭建JDK、MySQL、Redis和Nginx的環(huán)境,可以按照以下步驟進行操作,需要的朋友可以參考下
    2024-01-01
  • 詳解SpringBoot中Controller接收對象列表實現(xiàn)

    詳解SpringBoot中Controller接收對象列表實現(xiàn)

    這篇文章主要介紹了詳解SpringBoot中Controller接收對象列表實現(xiàn),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-05-05
  • Intellij IDEA導入JAVA項目并啟動(圖文教程)

    Intellij IDEA導入JAVA項目并啟動(圖文教程)

    這篇文章主要介紹了Intellij IDEA導入JAVA項目并啟動,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-08-08
  • Java直接輸出對象變成@.....的問題及解決

    Java直接輸出對象變成@.....的問題及解決

    這篇文章主要介紹了Java直接輸出對象變成@.....的問題及解決方案,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2023-09-09
  • Java:不支持發(fā)行版本5的超詳細簡單解決方案

    Java:不支持發(fā)行版本5的超詳細簡單解決方案

    發(fā)行版本5是Java5,已經(jīng)是十多年前的版本了,現(xiàn)在已經(jīng)不再被支持,如果您使用的是舊版的Java開發(fā)工具,可能會出現(xiàn)這樣的錯誤,這篇文章主要給大家介紹了關于Java:不支持發(fā)行版本5的超詳細簡單解決方案,需要的朋友可以參考下
    2024-01-01
  • Spring中的注解之@Override和@Autowired

    Spring中的注解之@Override和@Autowired

    看別人寫的代碼,經(jīng)常會用到 @Override 和 @Autowired 這兩個注解.這邊總結一下這兩個注解的作用,對正在學習java的小伙伴們有很好地幫助,需要的朋友可以參考下
    2021-05-05

最新評論