Java LinkedList – LinkedList ב-Java

מדריכים
Java

Java LinkedList היא יישום של ממשקי ה-List וה-Deque. זהו אחד ממחלקות היישום של הרשימה המשמשות בתדירות. הוא מרחיב את AbstractSequentialList ומיישם את ממשקי ה-List וה-Deque. זוהי אוסף מסודר ותומך באיברים כפולים. הוא מאחסן איברים בסדר ההכנסה. הוא תומך בהוספת איברים בערכים ריקים. הוא תומך בפעולות בהתבסס על אינדקס. אם ברצונך ללמוד עוד על יסודות הרשימה, אנא עבור דרך הפוסט הזה: Java List.

Post Brief Table of Content

בפוסט הזה אנו הולכים לדון במושגים הבאים.

  • Java LinkedList
  • Java LinkedList Class Diagram
  • Java LinkedList List Methods
  • Java LinkedList Deque Methods
  • Java LinkedList Basic Example
  • Java LinkedList Generics
  • Java Array to LinkedList
  • Java LinkedList to Array
  • Java LinkedList Real-time Usecases
  • Internal Representation of Java LinkedList
  • How Insertion works in Java LinkedList?
  • How Deletion works in Java LinkedList?
  • Java LinkedList Deque Operations
  • Java SE 8: Java LinkedList to Stream
  • Java SE 9 LinkedList

Java LinkedList

בסעיף זה, נדון בכמה מנקודות החשובות על LinkedList ב-Java:

  • קבוצת Java LinkedList היא חלק מסגנון הקולקציות של Java.
  • זו יישום של ממשקי List ו-Deque.
  • בפנים, הוא מיושם באמצעות מבנה נתונים של רשימה מקושרת דו-כיוונית.
  • הוא תומך באיברים כפולים.
  • הוא שומר או מתחזק את איבריו בסדר הכנסה.
  • אנו יכולים להוסיף כל מספר של איברים null.
  • הוא אינו מסונכרן, כלומר הוא אינו בטוח לשימוש רק בתהליכים.
  • ניתן ליצור LinkedList מסונכרן באמצעות שימוש בשיטה synchronizedList() של Collections.
  • ביישומי Java, אנו יכולים להשתמש בו כרשימה, מחסנית או תור.
  • הוא לא מיישם את ממשק ה-RandomAccess. לכן, אנו יכולים לגשת לאיברים בסדר רציף בלבד. הוא אינו תומך בגישה אקראית לאיברים.
  • כאשר אנו מנסים לגשת לאיבר מתוך LinkedList, החיפוש אחר האיבר מתחיל מההתחלה או הסוף של LinkedList בהתאם לאיפה האיבר הוא זמין.
  • אנו יכולים להשתמש ב-ListIterator כדי לעבור על איברי LinkedList.
  • החל מ-Java SE 8 ואילך, אנו יכולים להמיר LinkedList לזרם ולהיפך.
  • Java SE 9 מתכוון להוסיף מספר של שיטות מפעל ליצירת LinkedList לא משתנה.

תרשים כיתה של Java LinkedList

כפי שאנו יודעים, LinkedList של Java הוא אחד ממחלקות המימוש של List. זה גם מממש Deque. כפי שמוצג בתרשים הכיתה למטה, זה אינו מרחיב ישירות מקבוצת המחלקות AbstractList. זה מרחיב מחלקת AbstractSequentialList.

שיטות רשימת LinkedList של Java

בסעיף זה נדון בחלק מהשיטות השימושיות והנפוצות ביותר של LinkedList של Java. השיטות הבאות מורשות מממשק List או Collection:

  1. int size(): לקבלת מספר האיברים ברשימה.
  2. boolean isEmpty(): לבדיקה אם הרשימה ריקה או לא.
  3. boolean contains(Object o): מחזיר true אם הרשימה מכילה את האיבר המסוים.
  4. Iterator iterator(): מחזיר מאיץ על האיברים ברשימה בסדר נכון.
  5. Object[] toArray(): מחזיר מערך המכיל את כל האיברים ברשימה בסדר נכון.
  6. boolean add(E e): מוסיף את האיבר המסוים לסוף הרשימה.
  7. boolean remove(Object o): מסיר את המופע הראשון של האיבר המסוים מהרשימה.
  8. הפונקציה `retainAll(Collection c)` מחזירה את האיברים ברשימה שנמצאים גם באוסף המסופק.
  9. הפונקציה `clear()` מסירה את כל האיברים מהרשימה.
  10. E get(int index): Returns the element at the specified position in the list.
  11. E set(int index, E element): Replaces the element at the specified position in the list with the specified element.
  12. הפונקציה `listIterator()` מחזירה מעבר רשימה על האיברים ברשימה.
  13. הפונקציה `subList(int fromIndex, int toIndex)` מחזירה תצוגה של החלק של הרשימה בין המפתח fromIndex, כולל, ולמפתח toIndex, לא כולל. הרשימה שמוחזרת מחזיקה קישור לרשימה זו, כך ששינויים לא-מבניים ברשימה שמוחזרת משקפים ברשימה זו, ולהיפך.

שיטות Deque LinkedList של Java

השיטות הבאות מיוחדות למחלקת LinkedList ונירשו מממשק Deque:

  1. הפונקציה `addFirst(E e)` מכניסה את האיבר הנתון בתחילת הרשימה הזו.
  2. הפונקציה `addLast(E e)` מכניסה את האיבר הנתון בסוף הרשימה הזו.
  3. E getFirst(): Retrieves, but does not remove, the first element of this list. This method differs from peekFirst only in that it throws an exception if this list is empty.
  4. E getLast(): Retrieves, but does not remove, the last element of this list. This method differs from peekLast only in that it throws an exception if this list is empty.
  5. E remvoeFirst(): Removes and returns the first element from this list.
  6. E removeLast(): Removes and returns the last element from this list.
  7. הפונקציה `offerFirst(E e)` מכניסה את האיבר הנתון בתחילת הרשימה הזו.
  8. הפונקציה `offerLast(E e)` מכניסה את האיבר הנתון בסוף הרשימה הזו.
  9. E pollFirst(): Retrieves and removes the first element of this list, or returns null if this list is empty.
  10. E pollLast(): Retrieves and removes the last element of this list, or returns null if this list is empty.
  11. E peekFirst(): Retrieves, but does not remove, the first element of this list, or returns null if this list is empty.
  12. E peekLast(): Retrieves, but does not remove, the last element of this list, or returns null if this list is empty.

דוגמה בסיסית על LinkedList ב-Java

בסעיף זה, נדבר על דוגמה בסיסית של LinkedList ב-Java. נחקור כמה פעולות נוספות שימושיות בסעיפים הבאים.
דוגמה:-

import java.util.LinkedList;
import java.util.List;

public class LinkedListDemo 
{
  public static void main(String[] args) 
  {
	List names = new LinkedList();
	names.add("Rams");
	names.add("Posa");
	names.add("Chinni");
        names.add(2011);
			
	System.out.println("LinkedList content: " + names);
	System.out.println("LinkedList size: " + names.size());
  }
}

פלט:-

LinkedList content: [Rams, Posa, Chinni, 2011]
LinkedList size: 4

כאן יצרנו אובייקט LinkedList והוספנו 4 פריטים. כפי שדיברנו, בשימוש בשיטת LinkedList.size() ניתן לקבל את מספר האלמנטים ברשימה.
הערה:- בלי להשתמש ב-Generics, LinkedList ב-Java תומך באלמנטים הטרוגניים. מבחינת המומלץ לא להשתמש באוסף ללא Generics. נחקור את היתרונות והשימוש ב-Generics ב-Java בסעיף הבא עם דוגמה פשוטה.

Generics ב-Java LinkedList

בסעיף זה, נדון כיצד להשתמש ב-Generics עם LinkedList ב-Java. כפי שאנו יודעים, Generics ב-Java שימושיים לכתיבת תכנות בטיחות סוג ולביצוע בדיקות סוג חזקות יותר בזמן הקידום. הם גם שימושיים להסרת העלות של המרה.
דוגמה:-

import java.util.LinkedList;
import java.util.List;

public class LinkedListGenericsDemo
{
  public static void main(String[] args) 
  {
	List names = new LinkedList<>();
	names.add("Rams");
	names.add("Posa");
	names.add("Chinni");
        // אין אפשרות להוסיף דברים אחרים מלבד Strings
        // names.add(2011);
			
	System.out.println("LinkedList content: " + names);
	System.out.println("LinkedList size: " + names.size());
  }
}

פלט:-

LinkedList content: [Rams, Posa, Chinni]
LinkedList size: 3

כאן יצרנו אובייקט LinkedList עם Generics והוספנו 3 פריטים. כאשר ננסה להוסיף מספר ל-LinkedList, הוא משיב עם שגיאת זמן קידום.

מערך Java ל-LinkedList

בסעיף זה, נבחן איך להמיר מערך Java לאובייקט LinkedList. ניתן לעשות זאת בכמה דרכים, אך אני מציע כאן רק גישה אחת. דוגמה:-


import java.util.LinkedList;
import java.util.List;

public class JavaArrayToLinkedListDemo 
{
	public static void main(String[] args) 
	{
		Integer[] numbers = {1,2,3,4,5};
		List<Integer> numbersList = new LinkedList<>();
		for(Integer s : numbers){
			numbersList.add(s);
		}
		System.out.println(numbersList);
	}
}

פלט:-

[1, 2, 3, 4, 5]

LinkedList של Java למערך

בסעיף זה, נבחן איך להמיר LinkedList של Java למערך. ניתן לעשות זאת בכמה דרכים, אך אני מציע כאן רק גישה אחת. דוגמה:-

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class LinkedListToJavaArrayDemo 
{
	public static void main(String[] args) 
	{		
		List<Integer> numbersList = new LinkedList<>();
		numbersList.add(1);
		numbersList.add(2);
		numbersList.add(3);
		numbersList.add(4);
		numbersList.add(5);
		Integer[] numbers = new Integer[numbersList.size()];
		
		numbers = numbersList.toArray(numbers);
		System.out.println(Arrays.toString(numbers));

	}
}

פלט:-

[1, 2, 3, 4, 5]

LinkedList של Java בשימוש בזמן אמת

בסעיף זה, נדון במהו המקרה הטוב והמקרה הגרוע ביותר לשימוש ב-LinkedList ביישומי Java. תרחיש שימוש הטוב ביותר:-

  • כאשר הפעולה שאנו משתמשים בה בתדירות היא הוספת או הסרת איברים באמצע הרשימה, LinkedList היא הכיתה הטובה ביותר לשימוש.

למה? מפני שאין צורך לבצע מספר רב של הזזות כדי להוסיף או להסיר איברים באמצע הרשימה. יש להתייחס לסעיף "איך ההוספה עובדת ב-LinkedList של Java?" כדי להבין את זה בפרטיות. תרחיש שימוש הגרוע ביותר:-

  • כאשר הפעולה שאנו משתמשים בה בשכיחות היא לאחזר אלמנטים מרשימה, LinkedList היא הבחירה הגרועה ביותר.

למה? מכיוון ש-LinkedList תומכת רק בגישה סדרתית, ואינה תומכת בגישה אקראית. אנא עיין בקטע "איך מחיקה עובדת ב- Java LinkedList?" כדי להבין זאת בפרטיות. הערה:- LinkedList מיישמת את הממשקים List, Deque, Cloneable ו-Serializable. אך היא לא מיישמת את ממשק ה-RandomAccess.

ייצוג פנימי של Java LinkedList

כפי שאנו יודעים, בפנימיה, Java LinkedList מיושמת באמצעות Doubly Linked List. כך ש-LinkedList של Java מייצגת את אלמנטיה כצמתים. כל צומת מחולק לשלושה חלקים כמצוין למטה. כל צומת משמש למטרה ספציפית.

  1. חלק הצומת בצד שמאל משמש לצורך הפנייה לצומת (או אלמנט) הקודם ב-LinkedList.
  2. חלק הצומת בצד ימין משמש לצורך הפנייה לצומת (או אלמנט) הבא ב-LinkedList.
  3. חלק הצומת באמצע משמש לאחסון נתונים אמיתיים.

הערה:- ב-JVM, LinkedList אינו אוחסן את האיברים שלו בסדר רציף. הוא אוחסן את האיברים שלו בכל מקום זמין והם מחוברים אחד לשני באמצעות חלקי הצד שמאל וימין כפי שמוצג בתרשים מתחת.

איך פעולת ההוספה עובדת ב-Java LinkedList?

ראינו כבר איך LinkedList מאחסן את האיברים שלו כצמתים בקטע הקודם. בקטע זה, נדון באופן שבו פעולת ההוספה ב-Java LinkedList עובדת בפנים.

  1. נניח שיש לנו LinkedList התחלתי עם הנתונים הבאים.
    3. בצע את פעולת ההוספה הבאה ב-LinkedList זהה
linkedList.add(2,54);

כאן אנו מנסים לבצע את פעולת ההוספה כדי להוסיף איבר חדש עם הערך "54" באינדקס 2.5. ה-LinkedList המעודכן נראה כך.

איך פעולת המחיקה עובדת ב-Java LinkedList?

כבר ראינו כיצד נבנית פעולת ההכנסה של LinkedList בפנים בחלק הקודם. בסעיף זה, נדבר על איך פעולת המחיקה ב-Java LinkedList פועלת בפנים.

  1. נניח שה-LinkedList ההתחלתית שלנו מכילה את המידע הבא.
    3. בצע את פעולת ההכנסה הבאה ב-LinkedList זו
linkedList.remove(3);

כאן אנו מנסים לבצע פעולת המחיקה כדי למחוק אלמנט הנמצא באינדקס 3.5. ה-LinkedList המעודכן נראה כמו שמופיע למטה.

פעולות Deque ב-Java LinkedList

כאן נחקור כיצד אובייקט LinkedList פועל כ-Deque. אנו משתמשים בפעולות אלו ליישום של תורים או מחסנים. נדון באופן מעמיק באופן שבו Stack או Queues פועלים בעומק בפוסטים הבאים שלי. דוגמה:-

import java.util.LinkedList;
import java.util.LinkedList;
import java.util.Deque;

public class LinkedListDequeOperationsDemo 
{
  public static void main(String[] args) 
  {
	Deque names = new LinkedList();
	names.add(2);
	names.addFirst(1);
	names.addLast(3);
	names.addFirst(0);
	names.addLast(4);
			
	System.out.println("LinkedList content: " + names);
	System.out.println("LinkedList size: " + names.size());
	names.removeFirst();
	names.removeLast();
	
	System.out.println("LinkedList content: " + names);
	System.out.println("LinkedList size: " + names.size());	
  }
}

פלט:-

LinkedList content: [0, 1, 2, 3, 4]
LinkedList size: 5
LinkedList content: [1, 2, 3]
LinkedList size: 3

Java SE 8: ממשק LinkedList של Java כסטרים

כאן נחקור כיצד להמיר אובייקט LinkedList למושג Stream של Java SE 8. דוגמה:-

import java.util.LinkedList;
import java.util.List;

public class LinkedListToStreamDemo 
{
  public static void main(String[] args) 
  {		
	List numbersList = new LinkedList<>();
	numbersList.add(1);
	numbersList.add(2);
	numbersList.add(3);
	numbersList.add(4);
	numbersList.add(5);
		
	//המרת List ל-stream
	numbersList.stream().forEach(System.out::println);
  }
}

הפלט:

1
2
3
4
5

Java SE 9 LinkedList

ב-Java SE 9, תוסיף חברת Oracle כמה שיטות יעילות ליצירת רשימה לא ניתנת לשינוי. אם ברצונך ללמוד אותן בעומק עם דוגמאות שימושיות, אנא ראה את הפוסט שלי ב: Java SE 9: שיטות מפעל ליצירת רשימה לא ניתנת לשינוי. זו סיום מהיר לLinkedList ב-Java. אני מקווה שדוגמאות LinkedList ב-Java יעזרו לך להתחיל תכנות עם LinkedList. תודה על קריאת המדריכים שלי. בבקשה השאירו לי תגובה אם אהבתם את המדריכים שלי או יש לכם שאלות, הצעות או שגיאות סוגים שונים.

Source:
https://www.digitalocean.com/community/tutorials/java-linkedlist-linkedlist-java