Java LinkedList – LinkedList В Java

Учебники
Java

Java LinkedList – это реализация интерфейсов List и Deque на языке программирования Java. Это один из часто используемых классов реализации списка. Он расширяет AbstractSequentialList и реализует интерфейсы List и Deque. Это упорядоченная коллекция, поддерживающая дублирующие элементы и хранящая их в порядке вставки. Поддерживается добавление элементов со значением null и операции, основанные на индексе. Если вы хотите узнать больше о основах работы с List, пожалуйста, изучите этот пост: Java List.

Краткое содержание поста

В этом посте мы обсудим следующие концепции.

  • Java LinkedList
  • Диаграмма классов Java LinkedList
  • Методы списка Java LinkedList
  • Методы деки Java LinkedList
  • Простой пример использования Java LinkedList
  • Обобщения в Java LinkedList
  • Преобразование массива Java в LinkedList
  • Преобразование Java LinkedList в массив
  • Реальные примеры использования Java LinkedList
  • Внутреннее представление Java LinkedList
  • Как работает вставка в Java LinkedList?
  • Как работает удаление в Java LinkedList?
  • Операции деки Java LinkedList
  • Java SE 8: Преобразование Java LinkedList в Stream
  • Java SE 9: LinkedList

Java LinkedList

В этом разделе мы обсудим несколько важных моментов о Java LinkedList:

  • Класс Java LinkedList является членом Java Collections Framework.
  • Это реализация интерфейсов List и Deque.
  • Внутренне он реализован с использованием структуры данных Doubly Linked List.
  • Поддерживает дублирующие элементы.
  • Хранит свои элементы в порядке вставки.
  • Мы можем добавлять любое количество пустых элементов.
  • Он не синхронизирован, что означает, что он не является потокобезопасным.
  • Мы можем создать синхронизированный LinkedList, используя метод Collections.synchronizedList().
  • В приложениях Java мы можем использовать его как список, стек или очередь.
  • Он не реализует интерфейс RandomAccess. Поэтому мы можем получать доступ к элементам только последовательно. Он не поддерживает произвольный доступ к элементам.
  • При попытке доступа к элементу из LinkedList поиск этого элемента начинается с начала или конца LinkedList в зависимости от того, где этот элемент доступен.
  • Мы можем использовать ListIterator для итерации по элементам LinkedList.
  • С Java SE 8 и выше мы можем преобразовывать LinkedList в Stream и наоборот.
  • Java SE 9 собирается добавить несколько фабричных методов для создания Immutable LinkedList.

Диаграмма класса Java LinkedList

Как мы знаем, Java LinkedList – это один из классов реализации List. Он также реализует Deque. Как показано на диаграмме классов ниже, он НЕ наследует непосредственно от класса AbstractList. Он наследует класс AbstractSequentialList.

Методы списка Java LinkedList

В этом разделе мы обсудим некоторые из полезных и часто используемых методов Java LinkedList. Следующие методы унаследованы от интерфейса 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. boolean retainAll(Collection c): Сохраняет только элементы в этом списке, которые содержатся в указанной коллекции.
  9. void 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 listIterator(): Возвращает итератор списка по элементам в списке.
  13. List subList(int fromIndex, int toIndex): Возвращает представление части этого списка между указанным индексом fromIndex включительно и toIndex исключительно. Возвращенный список поддерживается этим списком, поэтому неструктурные изменения в возвращенном списке отражаются в этом списке и наоборот.

Методы Java LinkedList Deque

Следующие методы специфичны для класса LinkedList, который унаследован от интерфейса Deque:

  1. void addFirst(E e): Вставляет указанный элемент в начало этого списка.
  2. void 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. boolean offerFirst(E e): Вставляет указанный элемент в начало этого списка.
  8. boolean 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.

Простой пример Java LinkedList

В этом разделе мы рассмотрим простой пример базового Java LinkedList. Мы также исследуем несколько более полезных операций в следующих разделах. Пример:

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() используется для получения количества элементов в списке. ПРИМЕЧАНИЕ: Без использования обобщений Java LinkedList поддерживает гетерогенные элементы. Однако не рекомендуется использовать коллекции без обобщений. Давайте рассмотрим преимущества и использование обобщений Java в следующем разделе на примере.

Обобщения Java LinkedList

В этом разделе мы обсудим, как использовать обобщения с Java LinkedList. Как известно, обобщения 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");
        // Нельзя добавлять, кроме строк
        // 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 с обобщениями и добавили 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]

Java LinkedList в массив

В этом разделе мы рассмотрим, как преобразовать 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]

Реальные сценарии использования Java LinkedList

В этом разделе мы обсудим, какие сценарии использования являются наилучшими и какие – наихудшими для использования LinkedList в приложениях Java. Лучший сценарий использования:-

  • Когда наша часто используемая операция – добавление или удаление элементов в середине списка, LinkedList – лучший класс для использования.

Почему? Потому что нам не нужно выполнять много сдвигов для добавления или удаления элементов в середине списка. Пожалуйста, обратитесь к разделу “Как работает вставка в Java LinkedList?” для более подробного понимания. Худший сценарий использования:-

  • Когда наша часто используемая операция – извлечение элементов из списка, тогда LinkedList – худший выбор.

Почему? Потому что LinkedList поддерживает только последовательный доступ, НЕ поддерживает произвольный доступ. Пожалуйста, обратитесь к разделу “Как работает удаление в Java LinkedList?” для более подробного понимания. ПРИМЕЧАНИЕ:- LinkedList реализует интерфейсы List, Deque, Cloneable и Serializable. Но он НЕ реализует интерфейс RandomAccess.

Внутреннее представление Java LinkedList

Как мы знаем, внутренне Java LinkedList реализован с использованием Двусвязного списка. Таким образом, Java LinkedList представляет свои элементы в виде узлов. Каждый узел разделен на 3 части, как показано ниже. Здесь каждый узел используется для определенной цели.

  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. Мы используем эти операции для реализации очередей или стеков. Мы обсудим, как работает стек или очереди подробно в моих будущих сообщениях. Пример:-

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: Преобразование Java LinkedList в поток

Здесь мы рассмотрим, как преобразовать объект LinkedList в концепцию потока 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);
		
	//преобразовать список в поток
	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