โครงสร้างข้อมูลที่แตกต่างกันถูกสร้างขึ้นเพื่อวัตถุประสงค์ที่แตกต่างกัน คุณอาจทราบเกี่ยวกับ
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 ;
transient Node < E > first;
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 < 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
การทำงานของ LinkedList Java
ประสิทธิภาพของอัลกอริทึม
รับ (ดัชนี int)
O(n) โดยเฉลี่ย — n/4 ขั้นตอน โดยที่ n คือขนาดLinkedList
เพิ่ม (องค์ประกอบ E)
โอ(1)
เพิ่ม (ดัชนี int องค์ประกอบ E)
O(n) , โดยเฉลี่ย — n/4 ขั้นตอน; ถ้าindex = 0 แล้วO(1) ดังนั้นหากคุณต้องการเพิ่มบางอย่างในตอนต้นของรายการ LinkedList<E> อาจเป็นตัวเลือกที่ดี
ลบ (ดัชนี int)
O(n) โดยเฉลี่ย — n/4 ขั้น
Iterator.remove()
O(1) นี่คือเหตุผลหลักในการใช้LinkedList<E>
ความซับซ้อนของเวลา ArrayList
การทำงานของ LinkedList
ประสิทธิภาพของอัลกอริทึม
รับ (ดัชนี int)
O(1) หนึ่งในเหตุผลหลักในการใช้ArrayList<E>
เพิ่ม (องค์ประกอบ E)
O(n) เป็นกรณีที่แย่ที่สุดเนื่องจากอาร์เรย์ต้องปรับขนาดและคัดลอก อย่างไรก็ตาม ในทางปฏิบัติ ก็ไม่ได้เลวร้ายนัก
เพิ่ม (ดัชนี int องค์ประกอบ E)
O(n) , n/2 ก้าวโดยเฉลี่ย
ลบ (ดัชนี int)
O(n) , n/2 ก้าวโดยเฉลี่ย
Iterator.remove()
O(n) , n/2 ก้าวโดยเฉลี่ย
ListIterator.add (องค์ประกอบ E)
O(n) , n/2 ก้าวโดยเฉลี่ย
เมื่อใดควรใช้ 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) {
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 ) ) ;
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 ) ) ;
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 ( ) ;
System . out. println ( "testedList.size after removeElements(..): " + testedList. size ( ) ) ;
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 ( ) ;
System . out. println ( "testedList.size after removeElements(..): " + testedList. size ( ) ) ;
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 ต่อไปนี้เป็นขั้นตอนในการแก้ปัญหาเหล่านี้:
สร้าง คลาส โหนด ที่มีสองแอตทริบิวต์ ข้อมูล และถัดไป ถัดไปคือการอ้างอิงไปยังโหนดถัดไป
สร้าง คลาส FirstLast ด้วยสองแอตทริบิวต์ หัว และท้าย
สร้างadd() วิธีการเพิ่มโหนดใหม่ในรายการ ตรวจสอบว่ารายการว่างเปล่าก่อน ( head == null ) ถ้าเป็นเช่นนั้น ส่วนหัวและส่วนท้ายหมายถึงโหนดใหม่ ถ้ารายการไม่ว่างเปล่า โหนดใหม่จะถูกเพิ่มที่ส่วนท้าย ดังนั้นแอตทริบิวต์ถัดไปของส่วนท้ายจะอ้างถึงโหนดที่เพิ่ม และโหนดใหม่จะกลายเป็นส่วนท้ายของรายการ
โดยวิธีการที่คุณอาจลองสร้าง
LinkedList ของคุณเอง เป็นแบบฝึกหัดได้เช่นกัน ขอให้โชคดีในการเรียนรู้ของคุณ