Связанный массив LinkedList

LinkedList — реализует интерфейсы List, Dequeue, Queue и является представителем двунаправленного списка, где каждый элемент структуры содержит указатели на предыдущий и следующий элементы. Итератор поддерживает обход в обе стороны. LinkedList реализует методы получения, удаления и вставки в начало, середину и конец списка, а также позволяет добавлять любые элементы, в том числе и null.

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

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

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

Создание LinkedList объекта

Для создания нового LinkedList объекта можно использовать один из конструкторов, например:

List<String> list = new LinkedList<String>();

В графическом виде объект можно представить в следующем виде:

Созданный объект list, содержит свойства header и size. header — это псевдоэлемент списка. Его значение всегда равно null, a свойства next и prev всегда указывают на первый и последний элемент списка соответственно. Так как список вновь созданного объекта пустой, свойства next и prev указывают сами на себя (т.е. на элемент header). Следовательно, выполняется следующее тождество.

header.next = header.prev = header;

Добавление элемента в связанный массив LinkedList

Для добавления элемента в массив LinkedList можно использовать методы

• add(value), addLast(value) - добавление в конец списка
• addFirst(value) - добавление в начало списка

Например:

list.add("Школа");

Класс LinkedList включает статический внутренний класс Entry, с помощью которого создаются новые элементы.

private static class Entry<E>
{
    E element;
    Entry<E> next;
    Entry<E> prev;
    
    Entry(E element, Entry<E> next, Entry<E> prev)
    {
        this.element = element;
        this.next = next;
        this.prev = prev;
    }
}

Для добавления нового элемента в LinkedList необходимо выполнить две итерации:

• создать экземпляр класса Entry;
• переопределить указатели на предыдущий и следующий элемент.

В результате графически объект можно представить в следующем виде:

Методы LinkedList

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

Пример связанного списка LinkedList :

import java.util.LinkedList;
 
public class CollectionApp 
{
    public static void main(String[] args)
    {
        LinkedList<String> states = new LinkedList<String>();
         
        // Добавление элементов в список
        states.add     ("Германия"      );
        states.add     ("Франция"       );
                       // добавляем элемент в конец
        states.addLast ("Великобритания");
                       // добавляем элемент в первую позицию
        states.addFirst("Испания"       );
                       // добавляем элемент с индексом 1
        states.add     (1, "Италия"     );
       
        System.out.printf("В списке %d элементов \n", 
                                       states.size());
        System.out.println(states.get(1));
        states.set(1, "Дания");
        for (String state : states){
            System.out.println(state);
        }
        // проверка на наличие элемента в списке
        if (states.contains("Германия")){
            System.out.println(
                     "Список содержит государство Германия");
        }
         
        states.remove("Германия");
        states.removeFirst(); // удаление первого элемента
        states.removeLast();  // удаление последнего элемента

        LinkedList<Person> people;
        people = new LinkedList<Person>();
        people.add     (new Person("Алекс"));
        people.addFirst(new Person("Митя" ));
        people.addLast (new Person("Прохор"));
        people.remove(1); // удаление второго элемента
         
        for(Person p : people){
            System.out.println(p.getName());
        }
        Person first = people.getFirst();
                         // вывод в консоль первого элемента
        System.out.println(first.getName());
    }
}
class Person
{
    private String name;
    public Person(String value)
    {
        name=value;
    }
    String getName()
    {
        return name;
    }
}

В примере LinkedList создаются и используются два списка: для строк и для объектов класса Person. При этом в дополнение к методам addFirst/removeLast и т.д., доступны стандартные методы, определенные интерфейсом Collection: add(), remove, contains, size и другие. Поэтому можно использовать разные методы для одного и того же действия. Например, добавление в самое начало списка можно сделать так :

states.addFirst("Испания");
// а можно сделать так: 
states.add(0, "Испания");

Отличие LinkedList от ArrayList

ArrayList - это реализованный на основе массива список объектов. LinkedList — это связный список объектов.

LinkedList выполняет вставку и удаление элементов в списке за постоянное время (определение позиции для вставки или удаления не рассматривается). В большинстве случаев LinkedList проигрывает ArrayList и по потребляемой памяти и по скорости выполнения операций.

Если в алгоритме предусмотрена активная работа (вставка/удаление) в середине списка или в случаях, когда необходимо гарантированное время добавления элемента в список, то целесообразно использовать LinkedList.