Вступление:
LinkedList — это линейная структура данных, состоящая из узлов. В односвязном списке каждый узел содержит данные и ссылку. Здесь эталонная часть ссылается на следующий узел в связанном списке.
С другой стороны, в двусвязном списке у нас есть данные и ссылки как на предыдущий, так и на следующий узлы. Java предоставляет реализацию LinkedList — java.util.LinkedList <T>, которая работает с двусвязным списком. Этот класс наследуется от класса AbstractList и реализует интерфейсы List <T> и Deque <T> . В этом кратком руководстве мы научимся работать с классом LinkedList в Java.
Создайте LinkedList :
Мы можем создать связанный список в Java одним из следующих способов:
Ява
1
2
3
|
LinkedList<Integer> intList = new LinkedList<>(); LinkedList<Integer> intList1 = new LinkedList<>(intList); |
т.е. этот класс предоставляет два конструктора:
- LinkedList (): создает пустой связанный список
- LinkedList (Коллекция c): создает связанный список и инициализирует его с содержимым c в качестве его элементов
Добавление элементов:
Чтобы добавить элементы в LinkedList , мы можем использовать разновидности метода add () из интерфейса List <T> . Мы также можем использовать addFirst () или addLast (), который добавляет элемент в начало или конец соответственно.
Ява
1
2
3
|
intList.add( 1 ); // [1] intList.addFirst( 2 ); // [2, 1] intList.addLast( 3 ); // [2, 1, 3] |
Удаление элементов:
Аналогичным образом, чтобы удалить элемент, мы можем использовать методы remove (index), remove (obj) из интерфейса List . Или же, мы также можем выбрать метод removeFirst () или removeLast () :
Ява
1
2
|
int firstElement = intList.removeFirst(); int lastElement = intList.removeLast(); |
Эти методы как удаляют, так и возвращают удаленное значение.
Класс Java LinkedList также предоставляет методы removeFirstOccurrence (Object obj) и removeLastOccurrence (Object obj) для удаления первого и последнего вхождения данного значения соответственно. Эти методы возвращают false, если в нашем списке такого значения нет.
1
|
boolean removed = intList.removeFirstOccurrence( 1 ); |
Запрашиваемые элементы:
У нас есть методы getFirst () и getLast () в классе LinkedList для запроса первого или последнего элемента нашего связанного списка:
Ява
1
2
|
int firstElement = intList.getFirst(); int lastElement = intList.getLast(); |
Поскольку это реализация двусвязного списка, getFirst () и getLast () являются операциями постоянного времени.
Если нам известен индекс извлекаемого элемента, мы также можем использовать метод get (int index) интерфейса List :
Ява
1
|
int elementAtIndex1 = intList.get( 1 ); |
Итерация по LinkedList :
Мы будем перебирать связанный список, как и любую другую форму списка:
Ява
01
02
03
04
05
06
07
08
09
10
11
12
13
|
//Using a for loop for ( int num : intList) { System.out.println(num); } //Using iterator ListIterator itr = intList.listIterator(); while (itr.hasNext()) { System.out.println(itr.next()); } //Using forEach construct intList.forEach( value -> System.out.println(value); ); |
LinkedList против ArrayList:
Давайте наметим различия между классами Java LinkedList и ArrayList :
LinkedList | ArrayList |
---|---|
Использует двусвязное представление списка | Использует концепцию динамических массивов |
Реализует оба списка
и Deque интерфейсы |
Только реализует список
интерфейс |
Не подходит для произвольного доступа | Отлично подходит для произвольного доступа. Если мы знаем индекс, это займет всего O (1) времени для поиска |
O (1) вставки / удаления в начале и конце связанного списка Java | Вставка элементов в ArrayList может привести к изменению размера резервного массива, поэтому амортизированная стоимость O (n). Кроме того, вставка в начале ArrayList потребует от нас смещения всех элементов вправо на одну позицию. |
Затраты памяти на хранение ссылок на предыдущий и следующий узел | Нет необходимости хранить дополнительную информацию |
Не стесняйтесь узнать больше о ArrayList в этой статье. Все методы в классе ArrayList, унаследованные от интерфейса List <T> , также доступны в Java LinkedList .
Вывод:
В этом кратком руководстве мы рассмотрели некоторые из самых популярных методов класса Java LinkedList . Мы также рассмотрели разницу между Java ArrayList и LinkedList .
Оставьте первый комментарий.
Опубликовано на Java Code Geeks с разрешения Шубхры Шриваставы, партнера нашей программы JCG . Смотрите оригинальную статью здесь: LinkedList In Java Мнения, высказанные участниками Java Code Geeks, являются их собственными. |