โครงสร้างข้อมูลรายการเชื่อมโยงในภาษาจาวา

โครงสร้างข้อมูลที่แตกต่างกันถูกสร้างขึ้นเพื่อวัตถุประสงค์ที่แตกต่างกัน คุณอาจทราบเกี่ยวกับArrayList (หากยังไม่ทราบ เราขอแนะนำให้คุณอ่านก่อน) ในบทความนี้ เราจะมาเรียนรู้เกี่ยวกับLinkedListและทราบว่าคอลเล็กชันนี้มีประโยชน์อย่างไร หากคุณดูซอร์สโค้ดคลาส LinkedList Java 8 (หรือเวอร์ชันที่ใหม่กว่าของภาษา) (บนเว็บไซต์ Oracle หรือใน IDE ของคุณ ในกรณีของ IDEA: crtl+B บนชื่อคลาส) คุณจะเห็นการประกาศถัดไป:

public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable

ในขณะนี้ ข้อมูลที่สำคัญที่สุดจากโค้ดคือข้อเท็จจริงที่ว่าLinkedListใช้อินเทอร์เฟซListและDeque ส่วนต่อประสานรายการจะรักษาลำดับของการเพิ่มรายการและอนุญาตให้เข้าถึงรายการด้วยดัชนี คิว "ปกติ" รองรับการเพิ่มองค์ประกอบที่ส่วนท้ายและแยกองค์ประกอบออกจากจุดเริ่มต้น Deque เป็นคิวแบบสองทางและรองรับการเพิ่มและลบองค์ประกอบจากทั้งสองด้าน คุณอาจคิดว่าเป็นการผสมผสานระหว่างสแต็กและคิว ดังนั้น LinkedList จึงเป็นการดำเนินการของทั้งสองสิ่งนี้ และช่วยให้เราสามารถสร้างคิวแบบสองทิศทางที่ประกอบด้วยวัตถุใด ๆ รวมทั้งค่าว่าง รายการที่เชื่อมโยงเป็นการรวบรวมองค์ประกอบ เราสามารถเห็นได้ในซอร์สโค้ดของคลาส คราวนี้ให้ความสนใจกับฟิลด์:

transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;

ทุกองค์ประกอบ ซึ่งโดยปกติแล้วเราเรียกมันว่าโหนดจะมีออบเจกต์หนึ่งรายการและอ้างอิงถึงออบเจ็กต์ที่อยู่ใกล้เคียงสองรายการ — รายการก่อนหน้าและรายการถัดไป ดังนั้นจึงไม่ค่อยมีประสิทธิภาพในแง่ของการใช้หน่วยความจำ เนื่องจาก จริงๆ แล้ว LinkedListเป็นโครงสร้างแบบสองทิศทาง เราจึงสามารถเพิ่มหรือลบองค์ประกอบจากทั้งสองด้านได้อย่างง่ายดาย

ตัวสร้างรายการที่เชื่อมโยง

กลับไปที่ซอร์สโค้ด เราจะพบว่าLinkedListมีตัวสร้างสองตัว

• LinkedList()ที่ไม่มีพารามิเตอร์ใช้เพื่อสร้างรายการว่าง
• >LinkedList(Collection<? ขยาย E> c)มีไว้สำหรับสร้างรายการที่มีองค์ประกอบของคอลเล็กชันที่ระบุ ลำดับจะถูกส่งกลับโดยตัววนซ้ำของคอลเล็กชัน

ประกาศ LinkedList

ในความเป็นจริง รายการที่เชื่อมโยง (Java หรือในภาษาอื่น ๆ) ประกอบด้วยลำดับของโหนด ทุกโหนดได้รับการออกแบบให้เก็บออบเจกต์ประเภทที่กำหนดไว้เมื่อสร้าง ดังนั้นในการสร้างLinkedListโค้ด Java จึงเป็นสิ่งถัดไป:

LinkedList<Integer> myList = new LinkedList<>();

เรามีวัตถุที่จะเก็บลำดับของจำนวนเต็มและลิงก์ไปยังเพื่อนบ้าน อย่างไรก็ตาม มันว่างเปล่าในขณะนี้

การดำเนินงานหลักของ LinkedList

ตามปกติ ในกรณีของคอลเล็กชัน คุณสามารถใส่องค์ประกอบลงในLinkedList (ที่ส่วนท้ายหรือตรงกลาง) ลบออกจากที่นั่น และรับองค์ประกอบตามดัชนี ดังนั้นนี่คือ:

• เพิ่ม (องค์ประกอบ E)ผนวกองค์ประกอบที่ระบุต่อท้ายรายการนี้
• เพิ่ม (ดัชนี int, องค์ประกอบ E)แทรกองค์ประกอบที่ดัชนี ตำแหน่งที่ระบุ ;
• รับ (ดัชนี int)ส่งกลับองค์ประกอบในตำแหน่งที่ระบุในรายการนี้
• ลบ (ดัชนี int)ลบองค์ประกอบที่ดัชนีตำแหน่ง;
• ลบ (วัตถุ o)ลบการเกิดขึ้นครั้งแรกของ ? oองค์ประกอบจากรายการนี้ถ้ามี
• remove()ดึงและลบองค์ประกอบแรกของรายการ

การใช้งานรายการที่เชื่อมโยงใน Java การเพิ่มและลบองค์ประกอบ ตัวอย่าง

ลองดำเนินการเหล่านี้ในทางปฏิบัติ อันดับแรก การใช้งาน Java LinkedList: การสร้าง LinkedList ของ Strings โดยเพิ่มองค์ประกอบ 3 รายการ จากนั้นเอาอันหนึ่งออก แล้วเพิ่มอันหนึ่งตรงกลาง

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

ผลลัพธ์ของการเรียกใช้โปรแกรมนี้:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]

LinkedList เป็นส่วนหนึ่งของ เฟรมเวิ ร์กคอลเลก ชัน คุณสามารถใช้ Iterator เพื่อ ลบองค์ประกอบเช่นเดียวกับตัววนซ้ำพิเศษสำหรับรายการ - ListIterator ยิ่งกว่านั้น การดำเนินการกับ iterator ให้ประโยชน์หลักของ คลาส LinkedList : ประสิทธิภาพที่ดีของการดำเนินการแทรก/ลบ การใช้ Iterator คุณอาจได้รับเวลาคงที่สำหรับพวกเขา ในบทความนี้ เราจะเขียนตัวอย่างโค้ดเพื่อเปรียบเทียบArrayListและLinkedList+Iterator

• Iterator.remove()ลบองค์ประกอบสุดท้ายที่ส่งคืนโดย iterator นี้
• ListIterator.add(องค์ประกอบ E)แทรกองค์ประกอบลงในรายการ

ตัวอย่าง Java LinkedList: วิธีการทำงานของ Iterator

ที่นี่เรามีโค้ดตัวอย่าง Java LinkedList ขนาดเล็ก ที่เราลองเพิ่มและลบผ่าน Iterator

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
 
       Iterator i = linkedList.iterator();
       String str = "";
       while (i.hasNext()) {
           str = (String)i.next();
           if (str.equals("favorite")) {
               i.remove();
               break;
           }
       }

       System.out.println("linkedList after removing element via Iterator:");
       System.out.println(linkedList);
       ListIterator listIterator = linkedList.listIterator();
       listIterator.add("I've got");
       System.out.println("linkedList after adding the element via ListIterator");
       System.out.println(linkedList);
 
   }
}

ผลลัพธ์ของการเรียกใช้โปรแกรมนี้:

linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]

การทำงานของ Java LinkedList เพิ่มเติม:

• addFirst() , addLast() เพิ่มองค์ประกอบที่จุดเริ่มต้น/จุดสิ้นสุดของรายการ
• clear()ลบองค์ประกอบทั้งหมดออกจากรายการ
• มี (วัตถุ o)คืนค่าจริงหากรายการมีองค์ประกอบ o
• indexOf(Object o)ส่งคืนดัชนีของการเกิดขึ้นครั้งแรกขององค์ประกอบ o หรือ -1 หากไม่มีอยู่ในรายการ
• set(int index, E element)แทนที่องค์ประกอบที่ตำแหน่งดัชนีด้วยองค์ประกอบ
• size() ส่งกลับจำนวนขององค์ประกอบในรายการ
• toArray()ส่งคืนอาร์เรย์ที่มีองค์ประกอบของรายการทั้งหมดตั้งแต่องค์ประกอบแรกจนถึงองค์ประกอบสุดท้าย

BTW เป็นคิวสองขนาดLinkedListใน Java มีการดำเนินการเฉพาะสแต็ก:

• pop()ที่ดึงองค์ประกอบจากสแต็ก (แสดงโดยรายการ)
• push(E e)ที่ผลักองค์ประกอบไปยังสแต็ก (แสดงโดยรายการนี้)

วิธีย้อนกลับ LinkedList: ตัวอย่าง

นี่เป็นตัวอย่างเล็กๆ น้อยๆ ซึ่งเป็นที่นิยมแต่เป็นเรื่องง่ายสำหรับผู้เริ่มต้น เรามีLinkedListและควรย้อนกลับ อัลกอริทึมที่ง่ายที่สุดคือการผ่านLinkedListในลำดับย้อนกลับและใส่องค์ประกอบทั้งหมดลงในองค์ประกอบใหม่ อย่างไรก็ตาม บางทีคุณอาจจะพบวิธีที่ดีกว่านี้? นี่คือรหัสของโปรแกรม java รายการที่เชื่อมโยงย้อนกลับ:

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println(linkedList);
       System.out.println("Reversed LinkedList:");
       System.out.println(reverseLinkedList(linkedList));
   }
   public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
   {
       LinkedList<String> LinkedList = new LinkedList<String>();
       for (int i = list.size() - 1; i >= 0; i--) {
           LinkedList.add(list.get(i));
       }
       return LinkedList;
   }
}

ผลลัพธ์:

[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]

LinkedList vs ArrayList: เมื่อใดควรใช้อันแรก

ทั้ง LinkedListและArrayListเป็นการใช้งานอินเทอร์เฟซรายการ LinkedListนำไปใช้กับรายการที่เชื่อมโยงเป็นสองเท่า ArrayListใช้งานโดยใช้อาร์เรย์ที่ปรับขนาดแบบไดนามิก อย่างที่คุณทราบอยู่แล้ว ทุกโหนดของLinkedListมีออบเจกต์และการอ้างอิงสองรายการไปยังเพื่อนบ้าน นั่นหมายถึงต้นทุนหน่วยความจำเพิ่มเติมสำหรับการจัดเก็บการ อ้างอิงระหว่างองค์ประกอบในกรณีของ Java LinkedList ArrayListนำไปใช้กับอาร์เรย์ที่ปรับขนาดแบบไดนามิก การดำเนินการของ LinkedListและArrayListบางอย่างมีลักษณะเหมือนกัน แต่ทำงานต่างกัน ในArrayListกรณีที่คุณจัดการกับอาร์เรย์ภายในในLinkedList — พร้อมการอ้างอิง ArrayListเป็นการใช้งานList ที่ได้รับความนิยมสูงสุด คุณควรใช้ArrayListเมื่อการเข้าถึงดัชนีมีความสำคัญเนื่องจากการดำเนินการเหล่านี้จะดำเนินการในเวลาคงที่ การเพิ่มไปยังส่วนท้ายของรายการโดยเฉลี่ยจะทำในเวลาคงที่เช่นกัน ยิ่งกว่านั้นArrayListไม่มีค่าใช้จ่ายเพิ่มเติมสำหรับการจัดเก็บองค์ประกอบจำนวนมาก คุณอาจนับเป็นข้อเสียของความเร็วในการแทรกและลบการดำเนินการเมื่อทำเสร็จแล้วไม่ได้อยู่ที่ส่วนท้ายของรายการ รายการที่เชื่อมโยงมีประโยชน์มากกว่าในกรณีของการดำเนินการแทรกและลบในบางวิธี: หากคุณใช้ตัววนซ้ำ มันจะเกิดขึ้นในเวลาคงที่ การดำเนินการเข้าถึงโดยดัชนีดำเนินการโดยการค้นหาจากจุดเริ่มต้นของจุดสิ้นสุด (แล้วแต่ว่าระยะใดจะใกล้กว่า) ไปยังองค์ประกอบที่ต้องการ อย่างไรก็ตาม อย่าลืมเกี่ยวกับค่าใช้จ่ายเพิ่มเติมสำหรับการจัดเก็บข้อมูลอ้างอิงระหว่างองค์ประกอบต่างๆ นี่คือ การดำเนินการ LinkedListและArrayList มาตรฐาน พร้อมรันไทม์อัลกอริทึม N หมายถึงจำนวนของรายการที่มีอยู่แล้วในรายการ O(N)หมายความว่า ในกรณีที่เลวร้ายที่สุด เราควร "เดิน" ไปตามรายการทั้งหมดจนกว่าจะพบตำแหน่งที่ต้องการ เช่น สำหรับการแทรกองค์ประกอบใหม่ลงในรายการ โอ(1)หมายความว่าการดำเนินการเกิดขึ้นในเวลาคงที่ โดยไม่ขึ้นกับจำนวนรายการ

ความซับซ้อนของเวลา LinkedList

ความซับซ้อนของเวลา ArrayList

เมื่อใดควรใช้ LinkedList: ตัวอย่าง

แน่นอนว่าArrayList เป็นการ ใช้งานListที่ได้รับความนิยมมากที่สุด อย่างไรก็ตาม คุณอาจพบกับสถานการณ์เมื่อจำเป็นต้องดำเนินการเพิ่ม/ลบบ่อยเกินไป ในกรณีนั้นLinkedListร่วมกับ Iterator อาจเป็นประโยชน์ นี่คือตัวอย่าง เรามีรายการยาว และเราควรลบทุกรายการออกจากรายการนี้ มาทำภารกิจนี้ด้วยArrayListและLinkedList + Iterator เราเปรียบเทียบเวลาของการดำเนินการทุกครั้งและพิมพ์ลงในคอนโซล นี่คือรหัส:

import java.util.*;
import java.util.function.BiPredicate;
 
public class ListTest2 {
 
   static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
       // start navigation from end to preserve indexes of removed items
       ListIterator<Double> iterator = list.listIterator(list.size());
 
       while (iterator.hasPrevious()) {
           Double element = iterator.previous();
           if (predicate.test(iterator.previousIndex()+1, element)) {
               iterator.remove();
           }
       }
   }
 
   static class TestCase1 {
       public static void main(String[] args) {
           LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList1, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList1 after removeElements(..): " + testedList1);
 
           ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList2, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList2 after removeElements(..): " + testedList2);
       }
   }
 
   static class TestLinkedListPerformance {
       public static void main(String[] args) {
           LinkedList<Double> testedList = new LinkedList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
 
   static class TestArrayListPerformance {
       public static void main(String[] args) {
           ArrayList<Double> testedList = new ArrayList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
}

ผลลัพธ์สำหรับ ArrayList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414

ผลลัพธ์สำหรับรายการที่เชื่อมโยง:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458

อย่างที่คุณเห็นในกรณีนี้ LinkedList มีประสิทธิภาพมากกว่า ขอความซื่อสัตย์ ในการพัฒนาซอฟต์แวร์จริง การใช้ LinkedListเป็นเหตุการณ์ที่เกิดขึ้นได้ยาก อย่างไรก็ตาม ผู้เชี่ยวชาญควรทราบเกี่ยวกับการมีอยู่ของโครงสร้างข้อมูลนี้และข้อดีของมัน หากในรหัสจริงLinkedListเป็นแขกรับเชิญที่หายาก ในการสัมภาษณ์ Java Junior จะเป็นที่นิยมมาก และนี่คือสิ่งที่ Joshua Bloch เขียนเกี่ยวกับLinkedList :

AddOn: รายการที่เชื่อมโยงโดยลำพัง Java

ไม่มี Singly Linked Listในคอลเลกชั่น คลาสสิค ใน Java, Singly Linked Listเป็นโครงสร้างที่ทุกโหนดมี Object และการอ้างอิงไปยัง Node ถัดไป แต่ไม่ใช่สำหรับโหนดก่อนหน้า Java LinkedListเป็นแบบสองลิงก์ แต่ไม่มีใครรบกวนคุณในการสร้างโครงสร้างข้อมูลของคุณเอง เช่น แบบเดี่ยว ,code>Linked List ต่อไปนี้เป็นขั้นตอนในการแก้ปัญหาเหล่านี้:

1. สร้าง คลาส โหนดที่มีสองแอตทริบิวต์ ข้อมูล และถัดไป ถัดไปคือการอ้างอิงไปยังโหนดถัดไป
2. สร้าง คลาส FirstLastด้วยสองแอตทริบิวต์ หัว และท้าย
3. สร้างadd()วิธีการเพิ่มโหนดใหม่ในรายการ ตรวจสอบว่ารายการว่างเปล่าก่อน ( head == null ) ถ้าเป็นเช่นนั้น ส่วนหัวและส่วนท้ายหมายถึงโหนดใหม่ ถ้ารายการไม่ว่างเปล่า โหนดใหม่จะถูกเพิ่มที่ส่วนท้าย ดังนั้นแอตทริบิวต์ถัดไปของส่วนท้ายจะอ้างถึงโหนดที่เพิ่ม และโหนดใหม่จะกลายเป็นส่วนท้ายของรายการ

โดยวิธีการที่คุณอาจลองสร้าง LinkedList ของคุณเอง เป็นแบบฝึกหัดได้เช่นกัน ขอให้โชคดีในการเรียนรู้ของคุณ