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)站的支持!
- Java數(shù)據(jù)結構之鏈表詳解
- Java數(shù)據(jù)結構之單鏈表詳解
- Java 單鏈表數(shù)據(jù)結構的增刪改查教程
- Java數(shù)據(jù)結構之鏈表、棧、隊列、樹的實現(xiàn)方法示例
- Java描述數(shù)據(jù)結構學習之鏈表的增刪改查詳解
- Java數(shù)據(jù)結構之簡單鏈表的定義與實現(xiàn)方法示例
- Java數(shù)據(jù)結構之雙端鏈表原理與實現(xiàn)方法
- java 數(shù)據(jù)結構單鏈表的實現(xiàn)
- 詳解java數(shù)據(jù)結構與算法之雙鏈表設計與實現(xiàn)
- java 數(shù)據(jù)結構之刪除鏈表中的元素實例代碼
- JAVA 數(shù)據(jù)結構鏈表操作循環(huán)鏈表
- Java 數(shù)據(jù)結構鏈表操作實現(xiàn)代碼
- Java模擬有序鏈表數(shù)據(jù)結構的示例
- Java模擬單鏈表和雙端鏈表數(shù)據(jù)結構的實例講解
- java數(shù)據(jù)結構之實現(xiàn)雙向鏈表的示例
- java實現(xiàn)數(shù)據(jù)結構單鏈表示例(java單鏈表)
- Java數(shù)據(jù)結構之鏈表的增刪查改詳解
相關文章
Java中用Socket實現(xiàn)HTTP文件上傳實例
本篇文章主要介紹了Java中用Socket實現(xiàn)HTTP文件上傳實例,詳細的介紹了通過讀取Socket的輸入流來實現(xiàn)一個文件上傳的功能,有興趣的同學可以一起了解一下2017-04-04云服務器環(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),文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2020-05-05Intellij IDEA導入JAVA項目并啟動(圖文教程)
這篇文章主要介紹了Intellij IDEA導入JAVA項目并啟動,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2020-08-08Spring中的注解之@Override和@Autowired
看別人寫的代碼,經(jīng)常會用到 @Override 和 @Autowired 這兩個注解.這邊總結一下這兩個注解的作用,對正在學習java的小伙伴們有很好地幫助,需要的朋友可以參考下2021-05-05