Статьи

LinkedList в Java

Январь 2, 2019

Вступление:

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, являются их собственными.

48
Share: