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

Обобщенный класс LinkedList<E> представляет структуру данных в виде связанного списка. Он наследуется от класса AbstractSequentialList и реализует интерфейсы List, Dequeue и Queue. То есть он соединяет функциональность работы со списком и фукциональность очереди.

Класс LinkedList имеет следующие конструкторы:

• LinkedList(): создает пустой список

• LinkedList(Collection<? extends E> col): создает список, в который добавляет все элементы коллекции col

LinkedList содержит все те методы, которые определены в интерфейсах List, Queue, Deque. Некоторые из них:

• addFirst() / offerFirst(): добавляет элемент в начало списка

• addLast() / offerLast(): добавляет элемент в конец списка

• removeFirst() / pollFirst(): удаляет первый элемент из начала списка

• removeLast() / pollLast(): удаляет последний элемент из конца списка

• getFirst() / peekFirst(): получает первый элемент

• getLast() / peekLast(): получает последний элемент

Рассмотрим применение некоторых методов связанного списка. Добавление в список:

import java.util.LinkedList;
 
public class Program{
      
    public static void main(String[] args) {
          
        var people = new LinkedList<String>();
          
        // добавим в список ряд элементов
        people.add("Tom");              // Tom
        people.add("Bob");              // Tom - Bob

        // добавляем на последнее место
        people.addLast("Sam");          // Tom - Bob - Sam
        // добавляем на первое место
        people.addFirst("Alice");       // Alice - Tom - Bob - Sam
        // добавляем элемент по индексу 1
        people.add(1, "Kate");                 // Alice - Kate - Tom - Bob - Sam

        System.out.println(people);         // [Alice, Kate, Tom, Bob, Sam]

        // получаем размер списка
        System.out.printf("List has %d elements \n", people.size());
    }
}

Получение, изменение, перебор и проверка на наличие в списке:

import java.util.LinkedList;
import java.util.Collections;
 
public class Program{
      
    public static void main(String[] args) {
          
        var people = new LinkedList<String>();
        Collections.addAll(people, "Alice", "Kate", "Tom", "Bob", "Sam");

        // получаем третий элемент
        String second = people.get(2);
        System.out.println(second); // Tom

        // получаем первый элемент
        System.out.println(people.getFirst()); // Alice
        // получаем последний элемент
        System.out.println(people.getLast()); // Sam

        // Изменяем третий элемент
        people.set(2, "Tomas");

        System.out.println(people); // [Alice, Kate, Tomas, Bob, Sam]

        // перебор 
        for(var p : people){
          
            System.out.print(p + ", ");
        }
        System.out.println();

        // проверка на наличие элемента в списке
        if(people.contains("Tom")){
          
            System.out.println("List contains `Tom`");
        }
        else{
            System.out.println("List doesn`t contain `Tom`");
        }
    }
}

Удаление из списка:

import java.util.LinkedList;
import java.util.Collections;
 
public class Program{
      
    public static void main(String[] args) {
          
        var people = new LinkedList<String>();
        Collections.addAll(people, "Alice", "Kate", "Tom", "Bob", "Sam");

        System.out.println(people); // [Alice, Kate, Tomas, Bob, Sam]
        // удаляем конкретный элемент
        people.remove("Bob");    // [Alice, Kate, Tom, Sam]
        people.remove("Boby");    // если элемента нет, ничего не происходит
         // удаление первого элемента
        people.removeFirst();    // [Kate, Tom, Sam]
         // удаление последнего элемента
        people.removeLast();    // [Kate, Tom]
        System.out.println(people); // [Kate, Tom]

        // удаление всех элементов
        people.clear();
        System.out.println(people); // []
    }
}