รายการลิงค์ที่สั่งซื้อ:
เรียงลำดับตามค่าคีย์ เมื่อลบส่วนหัวของโซ่ค่าต่ำสุด (/สูงสุด) จะถูกลบ เมื่อแทรกให้ค้นหาตำแหน่งการแทรก
เมื่อแทรกคุณจะต้องเปรียบเทียบ o (n), ค่าเฉลี่ย o (n/2) และเมื่อลบข้อมูลขั้นต่ำ (/สูงสุด) ที่หัวโซ่ประสิทธิภาพคือ o (1)
หากแอปพลิเคชันต้องการการเข้าถึงบ่อยครั้ง (แทรก/ค้นหา/ลบ) ไปยังรายการข้อมูลที่เล็กที่สุด (/สูงสุด) รายการที่เชื่อมโยงที่สั่งซื้อเป็นตัวเลือกที่ดี คิวลำดับความสำคัญสามารถใช้รายการที่เชื่อมโยงเพื่อใช้การเรียงลำดับการแทรกของรายการที่เชื่อมโยงที่สั่งซื้อ:
สำหรับอาร์เรย์ที่ไม่ได้จัดเรียงให้เรียงลำดับด้วยรายการที่เชื่อมโยงที่สั่งซื้อและระดับเวลาของการเปรียบเทียบคือ O (n^2)
ระดับเวลาการคัดลอกคือ O (2*n) เนื่องจากจำนวนสำเนามีขนาดเล็กข้อมูลในรายการที่เชื่อมโยงจะถูกย้าย n ครั้งเป็นครั้งแรกจากนั้นคัดลอกจากรายการที่เชื่อมโยงไปยังอาร์เรย์ N ครั้งในแต่ละครั้งที่มีการแทรกลิงค์ใหม่ไม่จำเป็นต้องคัดลอกข้อมูลที่เคลื่อนย้ายลิงค์เพียงหนึ่งหรือสองลิงก์จะต้องเปลี่ยนโดเมนลิงค์
นำเข้า Java.util.Arrays; นำเข้า java.util.random; / *** การแทรกอาร์เรย์ในรายการที่เชื่อมโยงที่สั่งซื้อ* @author Stone*/ คลาสสาธารณะ LinkedListInsertSort <t ขยายเปรียบเทียบ <t>> {ลิงก์ส่วนตัว <t> ก่อน; // ครั้งแรกโหนดสาธารณะ linkedListinsertSort () {} บูลีนสาธารณะ isempty () {return first == null; } โมฆะสาธารณะ sortlist (t [] ary) {ถ้า (ary == null) {return; } // แทรกองค์ประกอบอาร์เรย์ลงในรายการที่เชื่อมโยงและเรียงลำดับในรายการที่เชื่อมโยงที่สั่งซื้อสำหรับ (t data: ary) {แทรก (ข้อมูล); } //} การแทรกโมฆะสาธารณะ (ข้อมูล t) {// แทรกไปยังส่วนหัวของห่วงโซ่เรียงลำดับจากลิงก์ขนาดเล็กถึงขนาดใหญ่ <T> newLink = ลิงก์ใหม่ <t> (ข้อมูล); ลิงก์ <t> current = แรกก่อนหน้า = null; ในขณะที่ (ปัจจุบัน! = null && data.Compareto (current.data)> 0) {previous = current; current = current.next; } if (previous == null) {first = newLink; } else {previous.next = newLink; } newLink.next = ปัจจุบัน; } ลิงค์สาธารณะ <t> deleteFirst () {// ลบลิงก์ส่วนหัวของห่วงโซ่ <t> temp = ก่อน; first = first.next; // เปลี่ยนโหนดแรกเพื่อส่งคืนอุณหภูมิ; } ลิงค์สาธารณะ <t> ค้นหา (t t) {ลิงก์ <t> find = first; ในขณะที่ (ค้นหา! = null) {ถ้า (! find.data.equals (t)) {find = find.next; } else {break; }} return find; } ลิงก์สาธารณะ <t> ลบ (t t) {ถ้า (isempty ()) {return null; } else {ถ้า (first.data.equals (t)) {link <t> temp = ก่อน; first = first.next; // เปลี่ยนโหนดแรกเป็นอุณหภูมิส่งคืนโหนดถัดไป }} ลิงก์ <t> p = ก่อน; ลิงก์ <t> q = ก่อน; ในขณะที่ (! p.data.equals (t)) {if (p.next == null) {// ระบุว่าไม่พบ null return ที่ปลายโซ่; } else {q = p; p = p.next; }} q.next = p.next; กลับ P; } โมฆะสาธารณะ displayList () {// travel system.out.println ("รายการ (ครั้งแรก-> สุดท้าย):"); ลิงก์ <t> current = ก่อน; ในขณะที่ (ปัจจุบัน! = null) {current.displaylink (); current = current.next; }} โมฆะสาธารณะ displayListreverse () {// ลิงค์ข้ามผกผัน <t> p = แรก, Q = first.next, t; ในขณะที่ (q! = null) {// ตัวชี้กลับด้านลำดับข้อมูลที่ผ่านการสำรวจจะย้อนกลับ t = q.next; // no3 ถ้า (p == ก่อน) {// เมื่อเป็นส่วนหัวดั้งเดิม. next ของส่วนหัวควรว่าง p.next = null; } q.next = p; // no3 -> no1 ตัวชี้ย้อนกลับ p = q; // start คือ reverse q = t; // no3 start} // ใน IF ในลูปด้านบนก่อนหน้านี้จะว่างเปล่าและเมื่อ q เป็นโมฆะและไม่ดำเนินการลูป p คือรายการข้อมูลส่วนใหญ่ดั้งเดิม หลังจากกลับด้านแล้ว P ถูกกำหนดให้เป็นครั้งแรก = p; DisplayList (); } class link <t> {// link point t data; // ลิงค์ฟิลด์ข้อมูล <t> ถัดไป; // ตัวชี้ที่ตามมาลิงก์โดเมนโซ่โหนด (ข้อมูล t) {this.data = data; } void displayLink () {system.out.println ("ข้อมูลคือ" + data.toString ()); }} โมฆะคงที่สาธารณะหลัก (สตริง [] args) {linkedListinsertSort <integer> list = new LinkedListInsertSort <Integer> (); สุ่มสุ่ม = ใหม่สุ่ม (); int len = 5; จำนวนเต็ม [] ary = จำนวนเต็มใหม่ [len]; สำหรับ (int i = 0; i <len; i ++) {ary [i] = random.nextint (1,000); } system.out.println ("--------------"); System.out.println (array.toString (ARY)); System.out.println ("-------------------------------------------------------); list.sortlist (ary); list.displaylist ();}}
พิมพ์
--- ก่อนการเรียงลำดับ ---- [595, 725, 310, 702, 444] --- หลังจากการเรียงลำดับของรายการที่เชื่อมโยง ---- รายการ (ครั้งแรก-> สุดท้าย): ข้อมูลคือ 310 ข้อมูลคือ 444 ข้อมูลคือ 595 ข้อมูลคือ 702 ข้อมูลคือ 725
รายการที่เชื่อมโยงเดียวแบบผกผัน:
ระดับสาธารณะ singlelinkedListreverse {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {node head = new node (0); โหนดอุณหภูมิ = null; โหนด cur = null; สำหรับ (int i = 1; i <= 10; i ++) {temp = โหนดใหม่ (i); if (i == 1) {head.setNext (temp); } else {cur.setNext (temp); } cur = temp; } // 10.Next = null; โหนด h = head; ในขณะที่ (h! = null) {system.out.print (h.getData () + "/t"); h = h.getNext (); } system.out.println (); // invert 1 // h = node.Reverse1 (หัว); // ในขณะที่ (h! = null) {// system.out.print (h.getData () + "/t"); // h = h.getNext (); //} // invert 2 h = node.reverse1 (หัว); ในขณะที่ (h! = null) {system.out.print (h.getData () + "/t"); h = h.getNext (); }}}/** แต่ละโหนดของรายการที่เชื่อมโยงเดียวมีแอตทริบิวต์ที่ชี้ไปที่โหนดถัดไป*/คลาสโหนด {data object; // data object node ถัดไป; // โหนดโหนดถัดไป (วัตถุ d) {this.data = d; } โหนด (วัตถุ d, โหนด n) {this.data = d; this.next = n; } วัตถุสาธารณะ getData () {ส่งคืนข้อมูล; } โมฆะสาธารณะ setData (ข้อมูลวัตถุ) {this.data = ข้อมูล; } โหนดสาธารณะ getNext () {return next; } โมฆะสาธารณะ setNext (โหนดถัดไป) {this.next = ถัดไป; } // วิธีการ 1 หัวรีเซ็ตโหนดคงที่ reverse1 (หัวโหนด) {โหนด p = null; // หัวใหม่หลังจากโหนดผกผัน Q = หัว; // ผลการหมุน: 012,123,234, ...... 10 null null ในขณะที่ (head.next! = null) {p = head.next; // อันแรกจะถูกแทนที่ด้วยอันที่สองจากนั้น p หมายถึง head.next = p.next; // อันที่สองจะถูกแทนที่ด้วยอันที่สามและอันต่อไปที่มาถึงตำแหน่งแรกจะกลายเป็นครั้งแรกและอันแรกจะกลายเป็นคนแรก // อันใหม่จะถูกแทนที่ด้วยอันแรก} return p; } // เมธอด 2 หัวไม่รีเซ็ตโหนดคงที่ reverse2 (หัวโหนด) {// ชี้ตัวชี้ของโหนดกลางไปยังโหนดก่อนหน้าคุณยังสามารถดำเนินการสำรวจรายการที่เชื่อมโยงย้อนหลังโหนด p1 = หัว, p2 = head.next, p3; // ด้านหน้า, กลางและหลัง // ผลการหมุน: 012, 123, 234, 345, 456 .... 9 10 null ในขณะที่ (p2! = null) {p3 = p2.next; p2.next = p1; // ชี้ไปข้างหลังและชี้ไปข้างหน้า p1 = p2; // 2, 3 ย้ายไปข้างหน้า p2 = p3; } head.next = null; // หัวไม่เปลี่ยนแปลง เมื่อเอาต์พุตถึง 0 ให้ขอ 0.Next ถึง 1 return p1; -