ในบทความก่อนหน้านี้เราวิเคราะห์การใช้งาน ArrayList และรู้ว่าการใช้งาน ArrayList นั้นขึ้นอยู่กับอาร์เรย์ดังนั้นจึงมีลักษณะของการค้นหาและการดัดแปลงที่รวดเร็วในขณะที่การแทรกและการลบช้า LinkedList ที่แนะนำในบทความนี้เป็นอีกการใช้งานส่วนต่อประสานรายการ ชั้นพื้นฐานของมันขึ้นอยู่กับรายการที่เชื่อมโยงแบบสองทิศทาง ดังนั้นจึงมีลักษณะของการแทรกอย่างรวดเร็วและการลบในขณะที่การค้นหาและการดัดแปลงช้า นอกจากนี้ฟังก์ชั่นของคิวและสแต็คสามารถรับรู้ได้ผ่านการดำเนินการของรายการที่เชื่อมโยงแบบสองทิศทาง โครงสร้างพื้นฐานของ LinkedList จะแสดงในรูปด้านล่าง
F หมายถึงการอ้างอิงโหนดหัว L หมายถึงการอ้างอิงโหนดหางและแต่ละโหนดในรายการที่เชื่อมโยงมีสามองค์ประกอบคือการอ้างอิงโหนดไปข้างหน้า (P), ค่าองค์ประกอบโหนด (E) และการอ้างอิงโหนดที่ตามมา (N) โหนดจะถูกแทนด้วยโหนดชั้นในให้ดูที่โครงสร้างภายในของมัน
// โหนดคลาสภายในคลาสส่วนตัวระดับเอกชน <E> {E รายการ; // Element Node <E> ถัดไป; // โหนดโหนดถัดไป <E> ก่อนหน้า; // โหนดก่อนหน้าโหนด (โหนด <E> ก่อนหน้า, องค์ประกอบ e, โหนด <E> ถัดไป) {this.Item = องค์ประกอบ; this.next = ถัดไป; this.prev = prev; -โหนดคลาสภายในนั้นง่ายมากโดยมีตัวแปรสมาชิกเพียงสามตัวและตัวสร้าง รายการแสดงค่าของโหนดถัดไปคือการอ้างอิงถึงโหนดถัดไปและก่อนหน้านี้คือการอ้างอิงถึงโหนดก่อนหน้า ค่าทั้งสามนี้จะถูกส่งผ่านตัวสร้าง จากนั้นมาดูตัวแปรสมาชิกและตัวสร้างของ LinkedList
// จำนวนขององค์ประกอบที่ตั้งค่าคือการแปลขนาด int = 0; // โหนดส่วนหัวอ้างอิงโหนดชั่วคราว <e> ก่อน; // โหนดหางอ้างอิงโหนดชั่วคราว <e> สุดท้าย; // ตัวเชื่อมต่อ parameterless publicor linkedList () {} // constructor ที่ผ่านการสะสม addall (c);}LinkedList มีการอ้างอิงถึงโหนดส่วนหัวและอ้างอิงถึงโหนดหาง มันมีตัวสร้างสองตัวหนึ่งตัวคือตัวสร้างที่ไม่มีพารามิเตอร์และอีกตัวเป็นตัวสร้างที่ส่งผ่านไปยังคอลเลกชันภายนอก LinkedList ไม่ได้ระบุตัวสร้างขนาดเริ่มต้นซึ่งแตกต่างจาก ArrayList ตรวจสอบวิธีการเพิ่มลบแก้ไขและค้นหา
// เพิ่ม (เพิ่ม) บูลีนสาธารณะเพิ่ม (e e) {// เพิ่ม linklast (e); return true;} // เพิ่ม (แทรก) โมฆะสาธารณะเพิ่ม (ดัชนี int, องค์ประกอบ e) {checkPositionIndex (ดัชนี); if (index == ขนาด) {// เพิ่ม linkLast (องค์ประกอบ); } else {// แทรก linkbefore (องค์ประกอบ, โหนด (ดัชนี)); }} // ลบ (ให้ดัชนี) สาธารณะ e ลบ (ดัชนี int) {// ตรวจสอบว่าตัวห้อยเป็นคำสั่งทางกฎหมาย legalelementIndex (ดัชนี); return unlink (node (index));} // delete (องค์ประกอบที่กำหนด) บูลีนสาธารณะลบ (object o) {ถ้า (o == null) {สำหรับ (node <e> x = แรก; x! = null; x = x.next) {ถ้า (x.item == null) {unlink (x); กลับมาจริง; }}} else {// รายการลิงก์ความเงียบสงบสำหรับ (Node <e> x = แรก; x! = null; x = x.next) {ถ้า (o.equals (x.item)) {// ลบ Unlink (x); กลับมาจริง; }}} return false;} // เปลี่ยน public e set (INT INDEX, E -Element) {// ตรวจสอบว่าตัวห้อยเป็น leg leg ทางกฎหมาย legal leglementIndex (ดัชนี); // รับการอ้างอิงโหนดของโหนดตัวห้อยที่ระบุ <E> x = โหนด (ดัชนี); // รับค่าของโหนดตัวห้อยที่ระบุ e oldval = x.item; // ตั้งค่าองค์ประกอบโหนดเป็นค่าใหม่ x.item = องค์ประกอบ; // ส่งคืนค่าก่อนหน้า return oldval;} // ตรวจสอบสาธารณะ e get (int index) {// ตรวจสอบว่าตัวห้อยเป็น checkelementIndex ทางกฎหมาย (ดัชนี); // ส่งคืนค่าของโหนดของโหนดส่งคืนตัวห้อยที่ระบุ (ดัชนี) .item;}วิธีการเพิ่มองค์ประกอบใน LinkedList ส่วนใหญ่เรียกใช้สองวิธี LinkLast และ LinkBefore วิธี LinkLast คือการเชื่อมโยงองค์ประกอบที่อยู่เบื้องหลังรายการที่เชื่อมโยงและวิธี LinkBefore คือการแทรกองค์ประกอบที่อยู่ตรงกลางของรายการที่เชื่อมโยง วิธีการลบของ LinkedList จะลบองค์ประกอบออกจากรายการที่เชื่อมโยงโดยเรียกใช้วิธี Unlink มาดูรหัสหลักของการแทรกและการลบการดำเนินการของรายการที่เชื่อมโยง
// ก่อนที่จะเชื่อมโยงไปยังโหนดที่ระบุโมฆะ linkBefore (e e, โหนด <e> succ) {// รับการอ้างอิงโหนดก่อนหน้าของโหนดสุดท้ายโหนดสุดท้าย <e> pred = succ.prev; // สร้างโหนดใหม่การอ้างอิงโหนดก่อนหน้าของจุดโหนดใหม่จุดไปยังโหนดก่อนหน้าของโหนดที่กำหนด // การอ้างอิงของโหนดถัดไปของคะแนนโหนดใหม่จุดไปยังโหนดสุดท้ายโหนดสุดท้าย <e> newNode = new node <> (pred, e, succ); // ชี้การอ้างอิงโหนดก่อนหน้าของโหนดที่กำหนดไปยังโหนดใหม่ succ.prev = newNode; // ถ้าโหนดก่อนหน้าของโหนดที่กำหนดว่างเปล่านั่นหมายความว่าโหนดที่กำหนดคือโหนดส่วนหัวถ้า (pred == null) {// ชี้โหนดส่วนหัวอ้างอิงไปยังโหนดใหม่แรก = newNode; } else {// มิฉะนั้นให้ชี้การอ้างอิงโหนดถัดไปไปที่โหนดใหม่ pred.next = newNode; } // เพิ่มจำนวนองค์ประกอบชุดหนึ่งขนาด ++; // เพิ่มจำนวนการแก้ไขหนึ่ง modcount ++; } // ยกเลิกการโหลดโหนดที่ระบุ E Unlink (Node <E> x) {// รับองค์ประกอบของโหนดสุดท้ายที่กำหนด E Element E = X.Item; // รับการอ้างอิงไปยังโหนดถัดไปของโหนดสุดท้ายโหนดสุดท้าย <e> next = x.next; // รับการอ้างอิงไปยังโหนดก่อนหน้าของโหนดสุดท้ายโหนดสุดท้าย <e> prev = x.prev; // ถ้าโหนดก่อนหน้าของโหนดที่กำหนดว่างเปล่าคำอธิบาย: โหนดที่กำหนดคือโหนดส่วนหัวถ้า (prev == null) {// ชี้โหนดส่วนหัวอ้างอิงไปยังโหนดถัดไปของโหนดที่กำหนดเป็นครั้งแรก = ถัดไป; } else {// อ้างอิงโหนดผู้สืบทอดของโหนดก่อนหน้าชี้ไปที่โหนดที่ตามมาของโหนดที่กำหนด prev.next = ถัดไป; // อ้างอิงโหนดก่อนหน้าของโหนดที่กำหนด x.prev = null; } // ถ้าโหนดถัดไปของโหนดที่กำหนดว่างเปล่าหมายความว่าโหนดที่กำหนดเป็นโหนดหางถ้า (ถัดไป == null) {// ชี้โหนดหางอ้างอิงไปยังโหนดก่อนหน้าของโหนดที่กำหนดสุดท้าย = ก่อนหน้า; } else {// อ้างอิงโหนดไปข้างหน้าของโหนดถัดไปที่ชี้ไปที่โหนดก่อนหน้าของโหนดที่กำหนด next.prev = prev; x.next = null; } // ล้างองค์ประกอบของโหนดที่กำหนด x.item = null; // ลบจำนวนองค์ประกอบที่ตั้งไว้ตามขนาด-; // เพิ่ม modcount ++; องค์ประกอบกลับ;} Linkbefore และ Unlink เป็นการดำเนินการตัวแทนของการเชื่อมโยงโหนดและการถอนการติดตั้งโหนด วิธีอื่น ๆ ของการเชื่อมโยงและการถอนการติดตั้งโหนดที่ปลายทั้งสองมีความคล้ายคลึงกันดังนั้นเราจึงมุ่งเน้นไปที่วิธีการเชื่อมโยงและไม่เชื่อมโยง
กระบวนการแผนภาพของวิธีการเชื่อมโยงก่อน:
กระบวนการไดอะแกรมของวิธี Unlink:
ผ่านภาพประกอบด้านบนความซับซ้อนของเวลาของการแทรกและการลบการดำเนินการของรายการที่เชื่อมโยงคือ O (1) และการดำเนินการค้นหาและปรับเปลี่ยนของรายการที่เชื่อมโยงนั้นจำเป็นต้องมีการสำรวจรายการที่เชื่อมโยงเพื่อค้นหาองค์ประกอบ การดำเนินการทั้งสองนี้เรียกว่าวิธีโหนด (ดัชนี Int) เพื่อค้นหาองค์ประกอบเพื่อดูว่ามันค้นหาองค์ประกอบผ่านตัวห้อยได้อย่างไร
// รับโหนดโหนด <e> โหนด (ดัชนี int) {// ถ้าดัชนีอยู่ในครึ่งแรกของรายการที่เชื่อมโยงให้ตรวจสอบจากจุดเริ่มต้นถ้า (ดัชนี <(ขนาด >> 1)) {node <e> x = ก่อน; สำหรับ (int i = 0; i <index; i ++) {x = x.next; } return x; } else {// ถ้าดัชนีอยู่ในช่วงครึ่งหลังของรายการที่เชื่อมโยงให้ตรวจสอบจากโหนดปลาย <e> x = ล่าสุด; สำหรับ (int i = size-1; i> index; i--) {x = x.prev; } return x; - เมื่อวางตำแหน่งตัวห้อยก่อนอื่นให้พิจารณาว่าอยู่ในครึ่งบนหรือครึ่งล่างของรายการที่เชื่อมโยง หากอยู่ในครึ่งบนเริ่มจากจุดเริ่มต้นและถ้ามันเป็นครึ่งล่างให้เริ่มจากจุดสิ้นสุด ดังนั้นความซับซ้อนของเวลาของการทำงานของการค้นหาและแก้ไขตัวห้อยคือ O (N/2) ผ่านการดำเนินการของรายการที่เชื่อมโยงแบบสองทิศทางฟังก์ชั่นของคิวรายการเดี่ยวคิวสองทางและสแต็คสามารถรับรู้ได้
การดำเนินการคิวทางเดียว:
// รับส่วนหัวโหนดสาธารณะ e peek () {โหนดสุดท้าย <e> f = ก่อน; return (f == null)? NULL: f.Item;} // รับส่วนหัวของโหนด public e Element () {return getFirst ();} // ป๊อปอัพโหนดส่วนหัว public e poll () {โหนดสุดท้าย <e> f = ก่อน; return (f == null)? NULL: unlinkFirst (f);} // ลบโหนดส่วนหัวสาธารณะ e ลบ () {return removeFirst ();} // เพิ่มโหนดในตอนท้ายของข้อเสนอบูลีนสาธารณะ (e) {return add (e);};การดำเนินการคิวสองทาง:
// เพิ่ม Boolean Public Boolean First (e e) {addfirst (e); RETURN TRUE;} // เพิ่ม Boolean Public Boolean OfferLast (E E) {AddLast (E); return true;} // รับส่วนหัวโหนดสาธารณะ e peekfirst () {โหนดสุดท้าย <e> f = ก่อน; return (f == null)? NULL: F.ITEM; } // รับโหนดหางสาธารณะ e peeklast () {โหนดสุดท้าย <e> l = สุดท้าย; return (l == null)? NULL: L.ITEM;}การดำเนินการสแต็ก:
// การวางโมฆะสาธารณะสแต็ก (e e) {addfirst (e);} // วางสแต็กสาธารณะ e pop () {return removefirst ();} ไม่ว่าจะเป็นคิวแบบทางเดียวคิวสองทางหรือสแต็กพวกเขาทำงานบนหัวและส่วนท้ายของรายการที่เชื่อมโยง การใช้งานของพวกเขาจะขึ้นอยู่กับสี่วิธี: addfirst (), addlast (), removefirst () และ removelast () การดำเนินการของพวกเขาคล้ายกับ Linkbefore () และ unlink () ยกเว้นว่าจะทำงานที่ปลายทั้งสองของรายการที่เชื่อมโยงและอีกรายการหนึ่งคือการทำงานที่อยู่ตรงกลางของรายการที่เชื่อมโยง อาจกล่าวได้ว่าวิธีการทั้งสี่นี้เป็นกรณีพิเศษของ LinkBefore () และวิธีการ Unlink () ดังนั้นจึงไม่ยากที่จะเข้าใจการใช้งานภายในของพวกเขาดังนั้นฉันจะไม่แนะนำพวกเขาที่นี่ ณ จุดนี้การวิเคราะห์ LinkedList ของเรากำลังจะจบลงและเราจะสรุปประเด็นสำคัญในข้อความทั้งหมด:
1. LinkedList ถูกนำไปใช้ตามรายการที่เชื่อมโยงสองทาง ไม่ว่าจะเป็นการเพิ่มการลบการดัดแปลงและวิธีการค้นหาหรือการใช้คิวและสแต็กสามารถนำไปใช้ได้ผ่านโหนดการดำเนินการ
2. LinkedList ไม่จำเป็นต้องระบุความสามารถล่วงหน้าเนื่องจากขึ้นอยู่กับการดำเนินการของรายการที่เชื่อมโยงความสามารถของคอลเลกชันจะเพิ่มขึ้นโดยอัตโนมัติเมื่อเพิ่มองค์ประกอบ
3. หน่วยความจำที่ถูกครอบครองโดยคอลเลกชันหลังจาก LinkedList ถูกลบจะลดลงโดยอัตโนมัติและไม่จำเป็นต้องเรียกวิธีการ trimtosize () เช่น ArrayList
4. วิธีการทั้งหมดของ LinkedList ไม่ได้ซิงโครไนซ์ดังนั้นจึงไม่ปลอดภัยกับเธรดและควรหลีกเลี่ยงในสภาพแวดล้อมแบบมัลติเธรด
5. การวิเคราะห์ข้างต้นขึ้นอยู่กับ JDK1.7 และรุ่นอื่น ๆ จะมีความแตกต่างบางอย่างดังนั้นจึงไม่สามารถสรุปได้
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่ามันจะเป็นประโยชน์ต่อการเรียนรู้ของทุกคนและฉันหวังว่าทุกคนจะสนับสนุน wulin.com มากขึ้น