Java LinkedList (с примери)

В този урок ще научим подробно за Java LinkedList с помощта на примери.

В LinkedListкласа на колекции рамките на Java осигурява функционалността на свързан списък структура данни (двойно LinkedList).

Двойно свързан списък на Java

Всеки елемент в свързан списък е известен като възел . Състои се от 3 полета:

  • Prev - съхранява адрес на предишния елемент в списъка. Това е nullза първия елемент
  • Next - съхранява адрес на следващия елемент в списъка. То е nullза последния елемент
  • Данни - съхранява действителните данни

Създаване на Java LinkedList

Ето как можем да създадем свързани списъци в Java:

 LinkedList linkedList = new LinkedList();

Тук Type показва типа на свързания списък. Например,

 // create Integer type linked list LinkedList linkedList = new LinkedList(); // create String type linked list LinkedList linkedList = new LinkedList();

Пример: Създайте LinkedList в Java

 import java.util.LinkedList; class Main ( public static void main(String() args)( // create linkedlist LinkedList animals = new LinkedList(); // Add elements to LinkedList animals.add("Dog"); animals.add("Cat"); animals.add("Cow"); System.out.println("LinkedList: " + animals); ) )

Изход

 LinkedList: (куче, котка, крава)

В горния пример създадохме LinkedListиме на животни.

Тук използвахме add()метода за добавяне на елементи към LinkedList. Ще научим повече за add()метода по-късно в този урок.

Работа на Java LinkedList

Елементите в свързаните списъци не се съхраняват последователно. Вместо това те са разпръснати и свързани чрез връзки ( Prev и Next ).

Внедряване на Java LinkedList

Тук имаме 3 елемента в свързан списък.

  • Куче - това е първият елемент, който съдържа null като предишен адрес и адреса на Cat като следващ адрес
  • Котка - това е вторият елемент, който съдържа адрес на Куче като предишен адрес и адрес на Крава като следващ адрес
  • Крава - това е последният елемент, който съдържа адреса на Cat като предишен адрес и null като следващ елемент

За да научите повече, посетете структурата на данните LinkedList.

Методи на Java LinkedList

LinkedListпредоставя различни методи, които ни позволяват да извършваме различни операции в свързани списъци. В този урок ще разгледаме четири често използвани оператора LinkedList:

  • Добавете елементи
  • Елементи за достъп
  • Промяна на елементи
  • Премахване на елементи

1. Добавете елементи към LinkedList

Можем да използваме add()метода за добавяне на елемент (възел) в края на LinkedList. Например,

 import java.util.LinkedList; class Main ( public static void main(String() args)( // create linkedlist LinkedList animals = new LinkedList(); // add() method without the index parameter animals.add("Dog"); animals.add("Cat"); animals.add("Cow"); System.out.println("LinkedList: " + animals); // add() method with the index parameter animals.add(1, "Horse"); System.out.println("Updated LinkedList: " + animals); ) )

Изход

 LinkedList: (Куче, котка, крава) Актуализиран LinkedList: (куче, кон, котка, крава)

В горния пример създадохме LinkedList, наречен животни. Тук използвахме add()метода за добавяне на елементи към животни.

Забележете изявлението,

 animals.add(1, "Horse");

Тук използвахме параметъра номер на индекса . Това е незадължителен параметър, който определя позицията, където се добавя новият елемент.

За да научите повече за добавянето на елементи към LinkedList, посетете програмата Java, за да добавите елементи към LinkedList.

2. Достъп до LinkedList елементи

В get()метода от класа на LinkedList се използва за достъп елемент от LinkedList. Например,

 import java.util.LinkedList; class Main ( public static void main(String() args) ( LinkedList languages = new LinkedList(); // add elements in the linked list languages.add("Python"); languages.add("Java"); languages.add("JavaScript"); System.out.println("LinkedList: " + languages); // get the element from the linked list String str = languages.get(1); System.out.print("Element at index 1: " + str); ) )

Изход

 LinkedList: (Python, Java, JavaScript) Елемент в индекс 1: Java

In the above example, we have used the get() method with parameter 1. Here, the method returns the element at index 1.

We can also access elements of the LinkedList using the iterator() and the listIterator() method. To learn more, visit the Java program to access elements of LinkedList.

3. Change Elements of a LinkedList

The set() method of LinkedList class is used to change elements of the LinkedList. For example,

 import java.util.LinkedList; class Main ( public static void main(String() args) ( LinkedList languages = new LinkedList(); // add elements in the linked list languages.add("Java"); languages.add("Python"); languages.add("JavaScript"); languages.add("Java"); System.out.println("LinkedList: " + languages); // change elements at index 3 languages.set(3, "Kotlin"); System.out.println("Updated LinkedList: " + languages); ) )

Output

 LinkedList: (Java, Python, JavaScript, Java) Updated LinkedList: (Java, Python, JavaScript, Kotlin)

In the above example, we have created a LinkedList named languages. Notice the line,

 languages.set(3, "Kotlin");

Here, the set() method changes the element at index 3 to Kotlin.

4. Remove element from a LinkedList

The remove() method of the LinkedList class is used to remove an element from the LinkedList. For example,

 import java.util.LinkedList; class Main ( public static void main(String() args) ( LinkedList languages = new LinkedList(); // add elements in LinkedList languages.add("Java"); languages.add("Python"); languages.add("JavaScript"); languages.add("Kotlin"); System.out.println("LinkedList: " + languages); // remove elements from index 1 String str = languages.remove(1); System.out.println("Removed Element: " + str); System.out.println("Updated LinkedList: " + languages); ) )

Output

 LinkedList: (Java, Python, JavaScript, Kotlin) Removed Element: Python New LinkedList: (Java, JavaScript, Kotlin)

Here, the remove() method takes the index number as the parameter. And, removes the element specified by the index number.

To learn more about removing elements from the linkedlist, visit the Java program to remove elements from LinkedList…

Other Methods

Methods Description
contains() checks if the LinkedList contains the element
indexOf() returns the index of the first occurrence of the element
lastIndexOf() returns the index of the last occurrence of the element
clear() removes all the elements of the LinkedList
iterator() returns an iterator to iterate over LinkedList

LinkedList as Deque and Queue

Since the LinkedList class also implements the Queue and the Deque interface, it can implement methods of these interfaces as well. Here are some of the commonly used methods:

Methods Descriptions
addFirst() adds the specified element at the beginning of the linked list
addLast() adds the specified element at the end of the linked list
getFirst() returns the first element
getLast() returns the last element
removeFirst() removes the first element
removeLast() removes the last element
peek() returns the first element (head) of the linked list
poll() returns and removes the first element from the linked list
offer() adds the specified element at the end of the linked list

Example: Java LinkedList as Queue

 import java.util.LinkedList; import java.util.Queue; class Main ( public static void main(String() args) ( Queue languages = new LinkedList(); // add elements languages.add("Python"); languages.add("Java"); languages.add("C"); System.out.println("LinkedList: " + languages); // access the first element String str1 = languages.peek(); System.out.println("Accessed Element: " + str1); // access and remove the first element String str2 = languages.poll(); System.out.println("Removed Element: " + str2); System.out.println("LinkedList after poll(): " + languages); // add element at the end languages.offer("Swift"); System.out.println("LinkedList after offer(): " + languages); ) )

Output

 LinkedList: (Python, Java, C) Accessed Element: Python Removed Element: Python LinkedList after poll(): (Java, C) LinkedList after offer(): (Java, C, Swift)

Example: LinkedList as Deque

 import java.util.LinkedList; import java.util.Deque; class Main ( public static void main(String() args)( Deque animals = new LinkedList(); // add element at the beginning animals.add("Cow"); System.out.println("LinkedList: " + animals); animals.addFirst("Dog"); System.out.println("LinkedList after addFirst(): " + animals); // add elements at the end animals.addLast("Zebra"); System.out.println("LinkedList after addLast(): " + animals); // remove the first element animals.removeFirst(); System.out.println("LinkedList after removeFirst(): " + animals); // remove the last element animals.removeLast(); System.out.println("LinkedList after removeLast(): " + animals); ) )

Output

 LinkedList: (Cow) LinkedList after addFirst(): (Dog, Cow) LinkedList after addLast(): (Dog, Cow, Zebra) LinkedList after removeFirst(): (Cow, Zebra) LinkedList after removeLast(): (Cow)

Iterating through LinkedList

We can use the Java for-each loop to iterate through LinkedList. For example,

 import java.util.LinkedList; class Main ( public static void main(String() args) ( // Creating a linked list LinkedList animals = new LinkedList(); animals.add("Cow"); animals.add("Cat"); animals.add("Dog"); System.out.println("LinkedList: " + animals); // Using forEach loop System.out.println("Accessing linked list elements:"); for(String animal: animals) ( System.out.print(animal); System.out.print(", "); ) ) )

Output

 LinkedList: (Cow, Cat, Dog) Accessing linked list elements: Cow, Cat, Dog,

LinkedList Vs. ArrayList

Both the Java ArrayList and LinkedList implements the List interface of the Collections framework. However, there exists some difference between them.

LinkedList ArrayList
Implements List, Queue, and Deque interfaces. Implements List interface.
Stores 3 values (previous address, data, and next address) in a single position. Съхранява единична стойност в една позиция.
Осигурява двойно свързаното изпълнение на списъка. Осигурява променяща се реализация на масив.
Винаги, когато се добавя елемент prevи nextсе променят адресите. Всеки път, когато се добави елемент, всички елементи след тази позиция се изместват.
За да осъществим достъп до елемент, трябва да извършим итерация от началото до елемента. Може да получава произволен достъп до елементи, използвайки индекси.

Забележка : Можем също да създадем LinkedList, използвайки интерфейси в Java. Например,

 // create linkedlist using List List animals1 = new LinkedList(); // creating linkedlist using Queue Queue animals2 = new LinkedList(); // creating linkedlist using Deque Deque animals3 = new LinkedList();

Тук, ако LinkedList е създаден с помощта на един интерфейс, тогава не можем да използваме методи, предоставени от други интерфейси. Тоест животните1 не могат да използват специфични методи Queueи Dequeинтерфейси.

Интересни статии...