Java模擬有序鏈表數(shù)據(jù)結(jié)構(gòu)的示例
有序鏈表:
按關(guān)鍵值排序。刪除鏈頭時(shí),就刪除最小(/最大)的值,插入時(shí),搜索插入的位置。
插入時(shí)需要比較O(N),平均O(N/2),刪除最小(/最大)的在鏈頭的數(shù)據(jù)時(shí)效率為O(1),
如果一個(gè)應(yīng)用需要頻繁的存取(插入/查找/刪除)最小(/最大)的數(shù)據(jù)項(xiàng),那么有序鏈表是一個(gè)不錯(cuò)的選擇
優(yōu)先級(jí)隊(duì)列 可以使用有序鏈表來實(shí)現(xiàn)
有序鏈表的插入排序:
對(duì)一個(gè)無序數(shù)組,用有序鏈表來排序,比較的時(shí)間級(jí)還是O(N^2)
復(fù)制時(shí)間級(jí)為O(2*N),因?yàn)閺?fù)制的次數(shù)較少,第一次放進(jìn)鏈表數(shù)據(jù)移動(dòng)N次,再?gòu)逆湵韽?fù)制到數(shù)組,又是N次
每插入一個(gè)新的鏈結(jié)點(diǎn),不需要復(fù)制移動(dòng)數(shù)據(jù),只需要改變一兩個(gè)鏈結(jié)點(diǎn)的鏈域
import java.util.Arrays; import java.util.Random; /** * 有序鏈表 對(duì)數(shù)組進(jìn)行插入排序 * @author stone */ public class LinkedListInsertSort<T extends Comparable<T>> { private Link<T> first; //首結(jié)點(diǎn) public LinkedListInsertSort() { } public boolean isEmpty() { return first == null; } public void sortList(T[] ary) { if (ary == null) { return; } //將數(shù)組元素插入進(jìn)鏈表,以有序鏈表進(jìn)行排序 for (T data : ary) { insert(data); } // } public void insert(T data) {// 插入 到 鏈頭, 以從小到大排序 Link<T> newLink = new Link<T>(data); Link<T> current = first, previous = null; while (current != null && data.compareTo(current.data) > 0) { previous = current; current = current.next; } if (previous == null) { first = newLink; } else { previous.next = newLink; } newLink.next = current; } public Link<T> deleteFirst() {//刪除 鏈頭 Link<T> temp = first; first = first.next; //變更首結(jié)點(diǎn),為下一結(jié)點(diǎn) return temp; } public Link<T> find(T t) { Link<T> find = first; while (find != null) { if (!find.data.equals(t)) { find = find.next; } else { break; } } return find; } public Link<T> delete(T t) { if (isEmpty()) { return null; } else { if (first.data.equals(t)) { Link<T> temp = first; first = first.next; //變更首結(jié)點(diǎn),為下一結(jié)點(diǎn) return temp; } } Link<T> p = first; Link<T> q = first; while (!p.data.equals(t)) { if (p.next == null) {//表示到鏈尾還沒找到 return null; } else { q = p; p = p.next; } } q.next = p.next; return p; } public void displayList() {//遍歷 System.out.println("List (first-->last):"); Link<T> current = first; while (current != null) { current.displayLink(); current = current.next; } } public void displayListReverse() {//反序遍歷 Link<T> p = first, q = first.next, t; while (q != null) {//指針反向,遍歷的數(shù)據(jù)順序向后 t = q.next; //no3 if (p == first) {// 當(dāng)為原來的頭時(shí),頭的.next應(yīng)該置空 p.next = null; } q.next = p;// no3 -> no1 pointer reverse p = q; //start is reverse q = t; //no3 start } //上面循環(huán)中的if里,把first.next 置空了, 而當(dāng)q為null不執(zhí)行循環(huán)時(shí),p就為原來的最且一個(gè)數(shù)據(jù)項(xiàng),反轉(zhuǎn)后把p賦給first first = p; displayList(); } class Link<T> {//鏈結(jié)點(diǎn) T data; //數(shù)據(jù)域 Link<T> next; //后繼指針,結(jié)點(diǎn) 鏈域 Link(T data) { this.data = data; } void displayLink() { System.out.println("the data is " + data.toString()); } } public static void main(String[] args) { LinkedListInsertSort<Integer> list = new LinkedListInsertSort<Integer>(); Random random = new Random(); int len = 5; Integer[] ary = new Integer[len]; for (int i = 0; i < len; i++) { ary[i] = random.nextInt(1000); } System.out.println("----排序前----"); System.out.println(Arrays.toString(ary)); System.out.println("----鏈表排序后----"); list.sortList(ary); list.displayList(); } }
打印
----排序前---- [595, 725, 310, 702, 444] ----鏈表排序后---- List (first-->last): the data is 310 the data is 444 the data is 595 the data is 702 the data is 725
單鏈表反序:
public class SingleLinkedListReverse { public static void main(String[] args) { Node head = new Node(0); Node temp = null; Node cur = null; for (int i = 1; i <= 10; i++) { temp = new Node(i); if (i == 1) { head.setNext(temp); } else { cur.setNext(temp); } cur = temp; }//10.next = null; Node h = head; while (h != null) { System.out.print(h.getData() + "\t"); h = h.getNext(); } System.out.println(); //反轉(zhuǎn)1 // h = Node.reverse1(head); // while (h != null) { // System.out.print(h.getData() + "\t"); // h = h.getNext(); // } //反轉(zhuǎn)2 h = Node.reverse1(head); while (h != null) { System.out.print(h.getData() + "\t"); h = h.getNext(); } } } /* * 單鏈表的每個(gè)節(jié)點(diǎn)都含有指向下一個(gè)節(jié)點(diǎn)屬性 */ class Node { Object data;//數(shù)據(jù)對(duì)象 Node next; //下一節(jié)點(diǎn) Node(Object d) { this.data = d; } Node(Object d, Node n) { this.data = d; this.next = n; } public Object getData() { return data; } public void setData(Object data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } //方法1 head被重置 static Node reverse1(Node head) { Node p = null; //反轉(zhuǎn)后新的 頭 Node q = head; //輪換結(jié)果:012,123,234,.... 10 null null while (head.next != null) { p = head.next; // 第1個(gè) 換成第2個(gè) 這時(shí)p表示原始序列頭中的next head.next = p.next; // 第2個(gè) 換成第3個(gè) p.next = q; //已經(jīng)跑到第1位置的原第2個(gè)的下一個(gè) 就要變成 原第1個(gè) q = p; //新的第1個(gè) 要變成 當(dāng)前第一個(gè) } return p; } //方法2 head沒重置 static Node reverse2(Node head) { //將中間節(jié)點(diǎn)的指針指向前一個(gè)節(jié)點(diǎn)之后仍然可以繼續(xù)向后遍歷鏈表 Node p1 = head, p2 = head.next, p3; // 前 中 后 //輪換結(jié)果 :012, 123, 234, 345, 456.... 9 10 null while (p2 != null) { p3 = p2.next; p2.next = p1; //指向后 變 指向前 p1 = p2; //2、3向前挪 p2 = p3; } head.next = null;//head沒變,當(dāng)輸出到0時(shí),再請(qǐng)求0.next 為1 return p1; } }
- java數(shù)據(jù)結(jié)構(gòu)之實(shí)現(xiàn)雙向鏈表的示例
- java實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)單鏈表示例(java單鏈表)
- Java數(shù)據(jù)結(jié)構(gòu)之簡(jiǎn)單鏈表的定義與實(shí)現(xiàn)方法示例
- Java模擬單鏈表和雙端鏈表數(shù)據(jù)結(jié)構(gòu)的實(shí)例講解
- Java 數(shù)據(jù)結(jié)構(gòu)鏈表操作實(shí)現(xiàn)代碼
- JAVA 數(shù)據(jù)結(jié)構(gòu)鏈表操作循環(huán)鏈表
- java 數(shù)據(jù)結(jié)構(gòu)之刪除鏈表中的元素實(shí)例代碼
- 詳解java數(shù)據(jù)結(jié)構(gòu)與算法之雙鏈表設(shè)計(jì)與實(shí)現(xiàn)
- Java描述數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之鏈表的增刪改查詳解
- Java數(shù)據(jù)結(jié)構(gòu)之鏈表實(shí)現(xiàn)(單向、雙向鏈表及鏈表反轉(zhuǎn))
相關(guān)文章
spring的事務(wù)傳播屬性REQUIRED_NESTED原理
這篇文章主要介紹了spring的事務(wù)傳播屬性REQUIRED_NESTED原理,在spring中,要想使用事務(wù)中的回滾點(diǎn),可以使用傳播屬性NESTED,需要的朋友可以參考下2023-05-05Java設(shè)計(jì)模式編程中的責(zé)任鏈模式使用示例
這篇文章主要介紹了Java設(shè)計(jì)模式編程中的責(zé)任鏈模式使用示例,責(zé)任鏈模式可以避免很多請(qǐng)求的發(fā)送者和接收者之間的耦合關(guān)系,需要的朋友可以參考下2016-05-05MyBatis-Plus實(shí)現(xiàn)條件查詢的三種格式例舉詳解
本文主要介紹了MyBatis-Plus三中條件查詢格式的示例,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-08-08解決IDEA中 Ctrl+ALT+V這個(gè)快捷鍵無法使用的情況
這篇文章主要介紹了解決IDEA中 Ctrl+ALT+V這個(gè)快捷鍵無法使用的情況,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2021-02-02Springboot vue導(dǎo)出功能實(shí)現(xiàn)代碼
這篇文章主要介紹了Springboot vue導(dǎo)出功能實(shí)現(xiàn)代碼,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-04-04SpringBoot整合SpringSecurity認(rèn)證與授權(quán)
在項(xiàng)目開發(fā)中,權(quán)限認(rèn)證是很重要的,尤其是一些管理類的系統(tǒng),對(duì)于權(quán)限要求更為嚴(yán)格,本文主要介紹了SpringBoot整合SpringSecurity認(rèn)證與授權(quán),感興趣的可以了解一下2023-11-11