Java-класс LinkedList

Класс Java LinkedList — это реализация двусвязного списка интерфейсов List и Deque. Он реализует все необязательные операции со списками и разрешает все элементы(включая null).

1. Иерархия связанных списков

Класс LinkedList расширяет класс AbstractSequentialList и реализует интерфейсы List и Deque. Здесь ‘E’ — это тип значений, которые хранит linkedlist.

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

2. Возможности LinkedList

• Реализация двусвязного списка, которая реализует интерфейсы List и Deque. Поэтому его также можно использовать как Queue, Deque или Stack.
• Разрешает все элементы, включая дубликаты и NULL.
• LinkedList сохраняет порядок вставки элементов.
• Он не синхронизирован. Если несколько потоков одновременно обращаются к связанному списку и хотя бы один из потоков изменяет структуру списка, он должен быть синхронизирован извне.
• Используйте Collections.synchronizedList(new LinkedList()) для получения синхронизированного связанного списка.
• Итераторы, возвращаемые этим классом, устойчивы к сбоям и могут вызывать исключение ConcurrentModificationException.
• Он не реализует интерфейс RandomAccess. Поэтому мы можем получать доступ к элементам только в последовательном порядке. Он не поддерживает доступ к элементам в случайном порядке.
• Мы можем использовать ListIterator для перебора элементов LinkedList.

3. Конструкторы LinkedList

1. LinkedList() : инициализирует пустую реализацию LinkedList.
2. LinkedListExample(Collection c): инициализирует LinkedList, содержащий элементы указанной коллекции в том порядке, в котором они возвращаются итератором коллекции.

4. Методы LinkedList

1. boolean add(Object o) : добавляет указанный элемент в конец списка.
2. void add(int index, Object element) : вставляет указанный элемент в указанную позицию index в списке.
3. void addFirst(Object o) : вставляет заданный элемент в начало списка.
4. void addLast(Object o) : добавляет заданный элемент в конец списка.
5. int size() : возвращает количество элементов в списке
6. boolean contains(Object o) : возвращает true, если список содержит указанный элемент, в противном случае возвращает false.
7. boolean remove(Object o) : удаляет первое вхождение указанного элемента в списке.
8. Объект getFirst(): возвращает первый элемент в списке.
9. Объект getLast(): возвращает последний элемент в списке.
10. int indexOf(Object o) : возвращает индекс в списке первого вхождения указанного элемента или -1, если список не содержит указанного элемента.
11. lastIndexOf(Object o) : возвращает индекс последнего вхождения указанного элемента в списке или -1, если список не содержит указанного элемента.
12. Итератор iterator() : возвращает итератор по элементам в этом списке в правильной последовательности.
13. Object[] toArray() : возвращает массив, содержащий все элементы этого списка в правильной последовательности.
14. List subList(int fromIndex, int toIndex) : возвращает представление части этого списка между указанным fromIndex(включительно) и toIndex(исключая).

5. Пример связанного списка Java

5.1. Добавить, удалить, повторить

Программа на Java для демонстрации использования основных методов в классе связанных списков.

import java.util.LinkedList;import java.util.ListIterator;public class LinkedListExample{public static void main(String[] args){//Create linked listLinkedList<String> linkedList = new LinkedList<>();//Add elementslinkedList.add("A");linkedList.add("B");linkedList.add("C");linkedList.add("D");System.out.println(linkedList);//Add elements at specified positionlinkedList.add(4, "A");linkedList.add(5, "A");System.out.println(linkedList);//Remove elementlinkedList.remove("A"); //removes AlinkedList.remove(0); //removes BSystem.out.println(linkedList);//IterateListIterator<String> itrator = linkedList.listIterator();while(itrator.hasNext()) {System.out.println(itrator.next());}}}

Вывод программы.

[A, B, C, D][A, B, C, D, A, A][C, D, A, A]CDAA

5.2. Преобразование между массивом и связанным списком

Программа Java для преобразования LinkedList в массив и преобразования массива в связанный список.

LinkedList<String> linkedList = new LinkedList<>();linkedList.add("A");linkedList.add("B");linkedList.add("C");linkedList.add("D");//1. LinkedList to ArrayString array[] = new String[linkedList.size()];linkedList.toArray(array);System.out.println(Arrays.toString(array));//2. Array to LinkedListLinkedList<String> linkedListNew = new LinkedList<>(Arrays.asList(array));System.out.println(linkedListNew);

Вывод программы.

[A, B, C, D][A, B, C, D]

5.3 Как сортировать LinkedList

Пример Java для сортировки LinkedList с использованием метода Collections.sort(). Обратите внимание, что для пользовательской сортировки объектов мы можем использовать метод Collections.sort(linkedList, comparator).

LinkedList<String> linkedList = new LinkedList<>();linkedList.add("A");linkedList.add("C");linkedList.add("B");linkedList.add("D");//UnsortedSystem.out.println(linkedList);//1. Sort the listCollections.sort(linkedList);//SortedSystem.out.println(linkedList);//2. Custom sortingCollections.sort(linkedList, Collections.reverseOrder());//Custom sortedSystem.out.println(linkedList);

Вывод программы.

[A, C, B, D][A, B, C, D][D, C, B, A]

6. Варианты использования LinkedList

В любом настольном приложении действия можно записывать в связанный список и реализовывать функции «Отменить» и «Повторить», начиная с последнего.

Кнопки «Далее» и «Назад» браузера можно запрограммировать с помощью связанного списка.

Связанные списки(в сочетании с хеш-таблицей) действительно полезны для LRU-кэшей.

7. Эффективность LinkedList

В классе Java LinkedList манипуляция быстрая, потому что не нужно выполнять сдвиг. Так что по сути все методы добавления и удаления обеспечивают очень хорошую производительность O(1).

• Метод add(E element) имеет сложность O(1).
• Методы get(int index) и add(int index, E element) имеют сложность O(n).
• Метод remove(int index) имеет сложность O(n).
• Iterator.remove() имеет сложность O(1).
• ListIterator.add(E element) имеет сложность O(1).

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

8. ArrayList против LinkedList

Давайте перечислим несколько заметных различий между arraylist и linkedlist.

• ArrayList реализован с концепцией динамически изменяемого размера массива, тогда как LinkedList — это реализация двусвязного списка.
• ArrayList допускает произвольный доступ к своим элементам, а LinkedList — нет.
• LinkedList также реализует интерфейс Queue, который добавляет больше методов, чем ArrayList, например offer(), peek(), poll() и т. д.
• По сравнению с LinkedList, ArrayList медленнее при добавлении и удалении, но быстрее при получении, поскольку нет необходимости изменять размер массива и копировать содержимое в новый массив, если массив LinkedList заполняется.
• LinkedList потребляет больше памяти, чем ArrayList, поскольку в ArrayList каждый индекс содержит только фактический объект, а в случае LinkedList каждый узел содержит как данные, так и адрес следующего и предыдущего узла.

9. Заключение

В этом уроке по Java LinkedList мы узнали, что такое LinkedList, в чем разница между LinkedList и ArrayList, как создать LinkedList, как добавлять, удалять и искать элементы в LinkedList, а также как выполнять итерацию по LinkedList.

Если у вас возникнут вопросы, дайте мне знать.

Ссылка:

Документация Java LinkedList