Связанный список Java

Связанный список Java

В предыдущей главе вы узнали о ArrayListклассе. Класс LinkedListпочти идентичен ArrayList:

// Import the LinkedList class
import java.util.LinkedList;

public class Main {
  public static void main(String[] args) {
    LinkedList<String> cars = new LinkedList<String>();
    cars.add("Volvo");
    cars.add("BMW");
    cars.add("Ford");
    cars.add("Mazda");
    System.out.println(cars);
  }
}

ArrayList против LinkedList

Класс LinkedList— это коллекция, которая может содержать множество объектов одного типа, как и класс ArrayList.

Класс LinkedListимеет все те же методы, что и ArrayListкласс, потому что они оба реализуют Listинтерфейс. Это означает, что вы можете добавлять элементы, изменять элементы, удалять элементы и очищать список таким же образом.

Однако, хотя ArrayListкласс и LinkedListкласс можно использовать одинаково, они строятся совершенно по-разному.

Как работает ArrayList

Внутри ArrayListкласса есть обычный массив. Когда элемент добавляется, он помещается в массив. Если массив недостаточно велик, создается новый массив большего размера для замены старого, а старый удаляется.

Как работает LinkedList

Магазин LinkedListхранит свои предметы в «контейнерах». В списке есть ссылка на первый контейнер, и каждый контейнер имеет ссылку на следующий контейнер в списке. Чтобы добавить элемент в список, этот элемент помещается в новый контейнер, и этот контейнер связывается с одним из других контейнеров в списке.

Методы связанного списка

Во многих случаях метод ArrayListболее эффективен, так как обычно требуется доступ к случайным элементам в списке, но он LinkedListпредоставляет несколько методов для более эффективного выполнения определенных операций: