Как написать свой linkedlist в java

Реализация методов в LinkedList

Всем добрый вечер. Прошу помощи в таком вопросе: у меня есть LinkedList с реализованными в нем методами, не получается реализовать 3 метода: public boolean remove(int index) — удаление элемента по индексу; public boolean removeElement(int element) — удаление самого элемента и public void set(int index, int element) — замена элемента. Помогите кто чем может, заранее благодарен.

package com.inguarus; public class IntLinkedList extends BaseList implements IntList < private Node first; private Node last; private static class Node < int element; Node next; Node previous; public Node(int element) < this.element = element; >> @Override public void add(int element) < Node newNode = new Node(element); if (first == null) < newNode.next = null; newNode.previous = null; first = newNode; last = newNode; >else < last.next = newNode; newNode.previous = last; last = newNode; >size++; > @Override public void add(int index, int element) < if (index < 0 || index >= size) < throw new IndexOutOfBoundsException(); >Node newNode = new Node(element); if (index == 0) < add(element); >if (index == size) < last.next = newNode; last = newNode; >Node oldNode = first; for (int i = 0; i < index; i++) < oldNode = oldNode.next; >Node oldPrevious = oldNode.previous; oldPrevious.next = newNode; oldNode.previous = newNode; newNode.previous = oldPrevious; newNode.next = oldNode; size++; > @Override public void clear() < first = null; last = null; size = 0; >@Override public boolean contains(int element) < for (int i = 0; i < size; i++) < if (get(i) == element) < return true; >> return false; > @Override public int get(int index) < if (index < 0 || index >= size) < throw new IndexOutOfBoundsException(); >Node result = first; for (int i = 0; i < index; i++) < result = result.next; >return result.element; > @Override public boolean isEmpty() < return size == 0; >@Override public boolean remove(int index) < if (index < 0 || index >= size) < throw new IllegalArgumentException(); >return false; > @Override public boolean removeElement(int element) < return false; >@Override public void set(int index, int element) < >>

Отслеживать

23.4k 3 3 золотых знака 49 49 серебряных знаков 70 70 бронзовых знаков

задан 8 июн 2018 в 15:14

85 1 1 серебряный знак 8 8 бронзовых знаков

1 ответ 1

Сортировка: Сброс на вариант по умолчанию

Реализовал нужные мне методы с помощью дополнительных методов:

public boolean remove(int index) < if (index < 0 || index >size - 1) < throw new IllegalArgumentException(); >if (index == 0) < first = first.next; >else < Node node = findNodeBeforeByIndex(index); Node tmp = findByIndex(index); node.next = tmp.next; >size--; return false; > public boolean removeElement(int element) < if (size == 0) < return false; >else if (size == 1) < first = null; last = null; size = 0; return true; >Node nodeBefore = findNodeBefore(element); if (nodeBefore.element == 0) < first = first.next; size--; return true; >else if (nodeBefore != null) < if (last.element == element) < nodeBefore.next = null; last = nodeBefore; >else < nodeBefore.next = nodeBefore.next.next; >size--; return true; > return false; > private Node findByIndex(int index) < if (index < 0 || index >size - 1) < throw new IndexOutOfBoundsException(); >int tmpIndex = 0; if (first == null) < throw new IndexOutOfBoundsException(); >if (index == 0) < return first; >Node node = first; while (node.next != null) < node = node.next; tmpIndex++; if (tmpIndex == index) < return node; >> throw new IndexOutOfBoundsException(); > private Node findNodeBefore(int value) < if (first.element == value) < return new Node(); >Node node = first; while (node.next != null) < if (node.next.element == value) < return node; >node = node.next; > return null; > private Node findNodeBeforeByIndex(int index) < if (index size - 1) < return null; >int count = 0; Node node = first; while (node.next != null) < if (count == index - 1) < return node; >count++; node = node.next; > return null; >

#2 — Коллекции данных ArrayList и LinkedList

#2 - Коллекции данных ArrayList и LinkedList

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

Видеоурок

В языке Java можно создавать как простые массивы данных, так и динамические массивы данных, что также называются коллекциями. Работа с простыми типами массивов была рассмотрена в курсе по основам языка Java. Посмотреть соответсвующий урок можно здесь .

Коллекции в языке Java

Стандартные массивы предоставляют лишь небольшой функционал по работе с элементами. Если мы захотим добавить 10 элемент в массив что состоит из 9 элементов, то будет выдана ошибка. Такой подход совсем неудобен, ведь не позволяет динамично управлять данными в массиве.

На помощь приходят коллекции данных. В языке Java есть множество интерфейсов по работе с коллекциями. Все такие интерфейсы представлены ниже:

Как видно из фото, каждая коллекция представляет из себя именно интерфейс, а не класс. Основным интерфейсом является Collection.

Вы можете создать коллекцию (другими словами: массив данных) на основе Collection или же на основе других интерфейсов, что являются наследниками интерфейса Collection.

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

Основные коллекции

Помимо главного интерфейса Collection есть три других главных формата:

List — коллекция для создания массивов данных, где индексами являются числа (0, 1, 2 и так далее);
Set — тоже самое что List, вот только в Set нельзя установить повторяющиеся элементы;
Map — коллекция для создания массивов данных, где индексами являются ключи («one», «2», «three» и так далее).

У каждого интерфейса есть интерфейсы наследники, что дополняют функциями базовый интерфейс. К примеру, можно создать коллекцию на основе класса List, а можно расширить её функционал за счёт создания коллекции на основе LinkedList.

Создание коллекций на основе разных интерфейсов очень схоже, поэтому в видео уроке были рассмотрены лишь ArrayList и LinkedList.

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

Работа с коллекциями

Для работы с коллекциями необходимо подключить соответсвующие интерфейсы из java.util .

При создании коллекции необходимо указать тип данных, имя, а также выделение памяти:

ArrayList numbers = new ArrayList<>(1); LinkedList names = new LinkedList<>();

Для работы с элементами существует множество методов. Наиболее часто используемые представлены ниже:

add() — добавление элемента в конец массива;
remove() — удаление элемента из массива по его индексу;
clear() — очистка всего массива;
size() — получение размера массива (количество элементов);
addFirst() — добавление элемента в начало массива;
addLast() — добавление элемента в конец;
clone() — выполняет клонирование массива;
get() — возвращает элемент по индексу;
getFirst() — возвращает первый элемент в массиве;
getLast() — возвращает последний элемент в массиве;
set(index, element) — меняет значение элемента по индексу.

Весь код будет доступен после подписки на проект!

31.8. Java – Класс LinkedList

Класс LinkedList в Java расширяет AbstractSequentialList и реализует интерфейс List. Он предоставляет структуру данных связанных списков.

Конструкторы

Ниже приведены конструкторы, поддерживаемые классом LinkedList.

№	Конструктор и описание
1	LinkedList( ) Этот конструктор создает пустой связанный список.
2	LinkedList(Collection c) Этот конструктор создает связанный список, который инициализируется элементами коллекции c.

Методы

Помимо применения методов, унаследованных от родительских классов, LinkedList определяет следующие методы:

№	и описание
1	void add(int index, Object element) Вставляет указанный элемент в указанный указатель позиции в этом списке. Вызывает IndexOutOfBoundsException, если указанный индекс выходит за допустимые пределы (index size()).
2	boolean add(Object o) Добавляет указанный элемент в конец этого списка.
3	boolean addAll(Collection c) Добавляет все элементы в указанной коллекции в конец этого списка в том порядке, в котором они возвращаются итератором указанной коллекции. Выбрасывает NullPointerException, если указанная коллекция имеет значение null (нуль).
4	boolean addAll(int index, Collection c) Вставляет все элементы указанной коллекции в этот список, начиная с указанной позиции. Вызывает NullPointerException, если указанная коллекция имеет значение null (нуль).
5	void addFirst(Object o) Вставляет данный элемент в начало этого списка.
6	void addLast(Object o) Добавляет данный элемент в конец этого списка.
7	void clear() Удаляет все элементы из этого списка.
8	Object clone() Возвращает мелкую копию этого LinkedList.
9	boolean contains(Object o) Возвращает true, если этот список содержит указанный элемент. Если точнее, то возвращает true тогда и только тогда, когда этот список содержит хотя бы один элемент e такой, что (o==null ? e==null : o.equals(e)).
10	Object get(int index) Возвращает элемент в указанной позиции в этом списке. Вызывает IndexOutOfBoundsException, если указанный индекс выходит за допустимые пределы (index = size()).
11	Object getFirst() Возвращает первый элемент в этом списке. Вызывает исключение NoSuchElementException, если этот список пуст.
12	Object getLast() Возвращает последний элемент в этом списке. Вызывает исключение NoSuchElementException, если этот список пуст.
13	int indexOf(Object o) Возвращает индекс в этом списке первого упоминания указанного элемента или -1, если список не содержит этот элемент.
14	int lastIndexOf(Object o) Возвращает индекс в этом списке последнего упоминания указанного элемента или -1, если список не содержит этот элемент.
15	ListIterator listIterator(int index) Возвращает список-итератор элементов в этом списке (в правильной последовательности), начиная с указанной позиции в списке. Вызывает IndexOutOfBoundsException, если указанный индекс выходит за пределы диапазона (index = size()).
16	Object remove(int index) Удаляет элемент в указанной позиции в этом списке. Вызывает исключение NoSuchElementException, если этот список пуст.
17	boolean remove(Object o) Удаляет первое упоминание указанного элемента в этом списке. Вызывает исключение NoSuchElementException, если этот список пуст. Вызывает IndexOutOfBoundsException, если указанный индекс выходит за пределы диапазона (index = size()).
18	Object removeFirst() Удаляет и возвращает первый элемент из этого списка. Выбрасывает исключение NoSuchElementException, если этот список пуст.
19	Object removeLast() Удаляет и возвращает последний элемент из этого списка. Вызывает исключение NoSuchElementException, если этот список пуст.
20	Object set(int index, Object element) Заменяет элемент в указанной позиции в этом списке указанным элементом. Вызывает IndexOutOfBoundsException, если указанный индекс выходит за пределы диапазона (index = size()).
21	int size() Возвращает количество элементов в этом списке.
22	Object[] toArray() Возвращает массив, содержащий все элементы в этом списке в правильном порядке. Выбрасывает NullPointerException, если указанный массив равен null (нулю).
23	Object[] toArray(Object[] a) Возвращает массив, содержащий все элементы в этом списке в правильном порядке; тип выполнения возвращаемого массива — тип указанного массива.

Пример

Следующая программа показывает реализацию некоторых методов, поддерживаемые LinkedList в Java:

import java.util.*; public class LinkedListDemo < public static void main(String args[]) < // Создаём LinkedList LinkedList ll = new LinkedList(); // Добавляем элементы в LinkedList ll.add("F"); ll.add("B"); ll.add("D"); ll.add("E"); ll.add("C"); ll.addLast("Z"); ll.addFirst("A"); ll.add(1, "A2"); System.out.println("Изначальное содержание ll: " + ll); // Удаляем элементы из LinkedList ll.remove("F"); ll.remove(2); System.out.println("Содержание ll после удаления: " + ll); // Удаляем первый и последний элементы ll.removeFirst(); ll.removeLast(); System.out.println("ll после удаления первого и последнего: " + ll); // Получаем и устанавливаем значение Object val = ll.get(2); ll.set(2, (String) val + " Изменено"); System.out.println("ll после изменения: " + ll); >>

Получим следующий результат:

Изначальное содержание ll: [A, A2, F, B, D, E, C, Z] Содержание ll после удаления: [A, A2, D, E, C, Z] ll после удаления первого и последнего: [A2, D, E, C] ll после изменения: [A2, D, E Изменено, C]

1. Java – Самоучитель для начинающих
2. Java – Обзор языка
3. Java – Установка и настройка
4. Java – Синтаксис
5. Java – Классы и объекты
6. Java – Конструкторы
7. Java – Типы данных и литералы
8. Java – Типы переменных
9. Java – Модификаторы
10. Java – Операторы
11. Java – Циклы и операторы цикла
11.1. Java – Цикл while
11.2. Java – Цикл for
11.3. Java – Улучшенный цикл for
11.4. Java – Цикл do..while
11.5. Java – Оператор break
11.6. Java – Оператор continue
12. Java – Операторы принятия решений
12.1. Java – Оператор if
12.2. Java – Оператор if..else
12.3. Java – Вложенный оператор if
12.4. Java – Оператор switch..case
12.5. Java – Условный оператор (? 🙂
13. Java – Числа
13.1. Java – Методы byteValue(), shortValue(), intValue(), longValue(), floatValue(), doubleValue()
13.2. Java – Метод compareTo()
13.3. Java – Метод equals()
13.4. Java – Метод valueOf()
13.5. Java – Метод toString()
13.6. Java – Метод parseInt()
13.7. Java – Метод Math.abs()
13.8. Java – Метод Math.ceil()
13.9. Java – Метод Math.floor()
13.10. Java – Метод Math.rint()
13.11. Java – Метод Math.round()
13.12. Java – Метод Math.min()
13.13. Java – Метод Math.max()
13.14. Java – Метод Math.exp()
13.15. Java – Метод Math.log()
13.16. Java – Метод Math.pow()
13.17. Java – Метод Math.sqrt()
13.18. Java – Метод Math.sin()
13.19. Java – Метод Math.cos()
13.20. Java – Метод Math.tan()
13.21. Java – Метод Math.asin()
13.22. Java – Метод Math.acos()
13.23. Java – Метод Math.atan()
13.24. Java – Метод Math.atan2()
13.25. Java – Метод Math.toDegrees()
13.26. Java – Метод Math.toRadians()
13.27. Java – Метод Math.random()
14. Java – Символы
14.1. Java – Метод Character.isLetter()
14.2. Java – Метод Character.isDigit()
14.3. Java – Метод Character.isWhitespace()
14.4. Java – Метод Character.isUpperCase()
14.5. Java – Метод Character.isLowerCase()
14.6. Java – Метод Character.toUpperCase()
14.7. Java – Метод Character.toLowerCase()
14.8. Java – Метод Character.toString()
15. Java – Строки
15.1. Java – Метод charAt()
15.2. Java – Метод compareTo()
15.3. Java – Метод compareToIgnoreCase()
15.4. Java – Метод concat()
15.5. Java – Метод contentEquals()
15.6. Java – Метод copyValueOf()
15.7. Java – Метод endsWith()
15.8. Java – Метод equals()
15.9. Java – Метод equalsIgnoreCase()
15.10. Java – Метод getBytes()
15.11. Java – Метод getChars()
15.12. Java – Метод hashCode()
15.13. Java – Метод indexOf()
15.14. Java – Метод intern()
15.15. Java – Метод lastIndexOf()
15.16. Java – Метод length()
15.17. Java – Метод matches()
15.18. Java – Метод regionMatches()
15.19. Java – Метод replace()
15.20. Java – Метод replaceAll()
15.21. Java – Метод replaceFirst()
15.22. Java – Метод split()
15.23. Java – Метод startsWith()
15.24. Java – Метод subSequence()
15.25. Java – Метод substring()
15.26. Java – Метод toCharArray()
15.27. Java – Метод toLowerCase()
15.28. Java – Метод toString()
15.29. Java – Метод toUpperCase()
15.30. Java – Метод trim()
15.31. Java – Метод valueOf()
15.32. Java – Классы StringBuilder и StringBuffer
15.32.1. Java – Метод append()
15.32.2. Java – Метод reverse()
15.32.3. Java – Метод delete()
15.32.4. Java – Метод insert()
15.32.5. Java – Метод replace()
16. Java – Массивы
17. Java – Дата и время
18. Java – Регулярные выражения
19. Java – Методы
20. Java – Потоки ввода/вывода, файлы и каталоги
20.1. Java – Класс ByteArrayInputStream
20.2. Java – Класс DataInputStream
20.3. Java – Класс ByteArrayOutputStream
20.4. Java – Класс DataOutputStream
20.5. Java – Класс File
20.6. Java – Класс FileReader
20.7. Java – Класс FileWriter
21. Java – Исключения
21.1. Java – Встроенные исключения
22. Java – Вложенные и внутренние классы
23. Java – Наследование
24. Java – Переопределение
25. Java – Полиморфизм
26. Java – Абстракция
27. Java – Инкапсуляция
28. Java – Интерфейсы
29. Java – Пакеты
30. Java – Структуры данных
30.1. Java – Интерфейс Enumeration
30.2. Java – Класс BitSet
30.3. Java – Класс Vector
30.4. Java – Класс Stack
30.5. Java – Класс Dictionary
30.6. Java – Класс Hashtable
30.7. Java – Класс Properties
31. Java – Коллекции
31.1. Java – Интерфейс Collection
31.2. Java – Интерфейс List
31.3. Java – Интерфейс Set
31.4. Java – Интерфейс SortedSet
31.5. Java – Интерфейс Map
31.6. Java – Интерфейс Map.Entry
31.7. Java – Интерфейс SortedMap
31.8. Java – Класс LinkedList
31.9. Java – Класс ArrayList
31.10. Java – Класс HashSet
31.11. Java – Класс LinkedHashSet
31.12. Java – Класс TreeSet
31.13. Java – Класс HashMap
31.14. Java – Класс TreeMap
31.15. Java – Класс WeakHashMap
31.16. Java – Класс LinkedHashMap
31.17. Java – Класс IdentityHashMap
31.18. Java – Алгоритмы Collection
31.19. Java – Iterator и ListIterator
31.20. Java – Comparator
32. Java – Дженерики
33. Java – Сериализация
34. Java – Сеть
34.1. Java – Обработка URL
35. Java – Отправка Email
36. Java – Многопоточность
36.1. Java – Синхронизация потоков
36.2. Java – Межпоточная связь
36.3. Java – Взаимная блокировка потоков
36.4. Java – Управление потоками
37. Java – Основы работы с апплетами
38. Java – Javadoc

Что «под капотом» у LinkedList?

Как работает ArrayList, вполне понятно. Есть много статей по этому поводу, часть из них иллюстрированы замечательными картинками, так что даже новичкам становится сразу все ясно. К лучшим статьям на эту тему я отношу «Структуры данных в картинках. ArrayList», написанную tarzan82.

Этот же автор описывает принципы работы LinkedList, однако часть данных устарела еще с выходом Java 7, поэтому попытка детально разобраться, что происходит внутри этой коллекции, по рисункам tarzan82 уже сложно. Да и в других источниках я не встретила понятных картинок, потому и возникла идея написать эту статью.

Итак, LinkedList — класс, реализующий два интерфейса — List и Deque. Это обеспечивает возможность создания двунаправленной очереди из любых (в том числе и null) элементов. Каждый объект, помещенный в связанный список, является узлом (нодом). Каждый узел содержит элемент, ссылку на предыдущий и следующий узел. Фактически связанный список состоит из последовательности узлов, каждый из которых предназначен для хранения объекта определенного при создании типа.

Разберемся, что же происходит, когда мы пишем уже простые и привычные строки кода.

1. Создание связанного списка

LinkedList numbers = new LinkedList<>();

Данный код создает объект класса LinkedList и сохраняет его в ссылке numbers. Созданный объект предназначен для хранения целых чисел (Integer). Пока этот объект пуст.

Класс LinkedList содержит три поля:

// модификатор transient указывает на то, что данное свойство класса нельзя // сериализировать transient int size = 0; transient Node first; transient Node last;

2. Добавление объекта в конец связанного списка

numbers.add(8);

Данный код добавляет число 8 в конец ранее созданного списка. Под «капотом» этот метод вызывает ряд других методов, обеспечивающих создание объекта типа Integer, создание нового узла, установку объекта класса Integer в поле item этого узла, добавление узла в конец списка и установку ссылок на соседние узлы.

Для установки ссылок на предыдущий и следующий элементы LinkedList использует объекты своего вложенного класса Node:

private static class Node  < E item; Nodenext; Node prev; Node(Node prev, E element, Node next) < this.item = element; this.next = next; this.prev = prev; >>

При каждом добавлении объекта в список создается один новый узел, а также изменяются значения полей связанного списка (size, first, last).

В случае с добавлением первого элемента создается узел, у которого предыдущий и следующий элементы отсутствуют, т.е. являются null, размер коллекции увеличивается на 1, а созданный узел устанавливается как первый и последний элемент коллекции.

Добавим еще один элемент в нашу коллекцию:

numbers.add(5);

Сначала создается узел для нового элемента (число 5) и устанавливается ссылка на существующий элемент (узел с числом 8) коллекции как на предыдущий, а следующим элементом у созданного узла остается null. Также этот новый узел сохраняется в переменную связанного списка last:

Как можно увидеть на рис. 4, первый элемент коллекции (под индексом 0) пока ссылается на null как на следующий элемент. Теперь эта ссылка заменяется и первый элемент начинает ссылаться на второй элемент коллекции (под индексом 1), а также увеличивается размер коллекции:

3. Добавление объекта в середину связанного списка

numbers.add(1, 13);

LinkedList позволяет добавить элемент в середину списка. Для этого используется метод add(index, element), где index — это место в списке, куда будет вставлен элемент element.

Как и метод add(element), данный метод вызывает несколько других методов. Сначала осуществляется проверка значения index, которое должно быть положительным числом, меньшим или равным размеру списка. Если index не удовлетворит этим условиям, то будет сгенирировано исключение IndexOutOfBoundsException.

Затем, если index равен размеру коллеции, то осуществляются действия, описанные в п. 2, так как фактически необходимо вставить элемент в конец существующего списка.

Если же index не равен size списка, то осуществляется вставка перед элементом, который до этой вставки имеет заданный индекс, т.е. в данном случае перед узлом со значением 5.

Для начала с помощью метода node(index) определяется узел, находящийся в данный момент под индексом, под который нам необходимо вставить новый узел. Поиск данного узла осуществляется с помощью простого цикла for по половине списка (в зависимости от значения индекса — либо с начала до элемента, либо с конца до элемента). Далее создается узел для нового элемента (число 13), ссылка на предыдущий элемент устанавливается на узел, в котором элементом является число 8, а ссылка на следующий элемент устанавливается на узел, в котором элементом является число 5. Ссылки ранее существующих узлов пока не изменены:

Теперь последовательно заменяются ссылки: для элемента, следующего за новым элементом, заменяется ссылка на предыдущий элемент (теперь она указывает на узел со значением 13), для предшествующего новому элементу заменяется ссылка на следующий элемент (теперь она указывает на узел со значением 5). И в последнюю очередь увеличивается размер списка:

4. Удаление объекта из списка

Для удаления одного элемента из списка класс LinkedList предлагает нам аж 10 методов, различающихся по типу возвращаемого значения, наличию или отсутствию выбрасываемых исключений, а также способу указания, какой именно элемент следует удалить:

Рассмотрим удаление элемента из связанного списка по его значению. Удалим элемент со значением 5 из нижепредставленного списка:

numbers.remove(Integer.valueOf(5));

Обратите внимание, что принимаемым значением в методе remove(object) является именно объект, если же мы попытаемся удалить элемент со значением 5 следующей строкой

numbers.remove(5);

то получим IndexOutOfBoundsException, т.к. компиллятор воспримет число 5 как индекс и вызовет метод remove(index).

Итак, что же происходит при вызове метода remove(object)? Сначала искомый объект сравнивается по порядку со всеми элементами, сохраненными в узлах списка, начиная с нулевого узла. Когда найден узел, элемент которого равен искомому объекту, первым делом элемент сохраняется в отдельной переменной. Потом переопределяются ссылки соседних узлов так, чтобы они указывали друг на друга:

Затем обнуляется значение узла, который содержит удаляемый объект, а также уменьшается размер коллекции:

Теперь вернемся к тому моменту, что элемент из удаляемого узла мы сохраняли в памяти. Зачем мы это делали, спросите вы, если эти данные мы нигде дальше не использовали. Дело в том, что рассматриваемый нами метод в результате своей работу не возвращает удаленный элемент, потому данные, возврещенные вызванным в рамках работы метода unlink(node), вызванного методом remove(object), просто не понадобились. А вот когда мы используем метод remove(index), также вызывающий метод unlink(node), то значение данного элемента последовательно возвращается сначала методом unlink(node), а затем и методом remove(index). Похожая ситуация наблюдается и в остальных методах, возвращающих значение удаленного элемента, только внутри вызываются другие методы, отсоединяющие ссылку: в методах poll(), pollFirst(), remove() и removeFirst() это метод unlinkFirst(node), а в методах pollLast() и removeLast() — метод unlinkLast(node).

Итак, что следует помнить о LinkedList, решая, использовать ли данную коллекцию:

не синхронизирована;
позволяет хранить любые объекты, в том числе null и повторяющиеся;
за константное время O(1) выполняются операции вставки и удаления первого и последнего элемента, операции вставки и удаления элемента из середины списка (не учитывая время поиска позиции элемента, который осуществляется за линейное время);
за линейное время O(n) выполняются операции поиска элемента по индексу и по значению.