Связанный массив 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 содержит ряд методов для управления элементами, среди которых можно выделить следующие:

МетодОписание
addFirst() / offerFirst() добавляет элемент в начало списка
addLast() / offerLast() добавляет элемент в конец списка
removeFirst() / pollFirst() удаляет первый элемент из начала списка
removeLast() / pollLast() удаляет последний элемент из конца списка
getFirst() / peekFirst() получает первый элемент
getLast() / peekLast() получает последний элемент

Пример связанного списка 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("Испания"       ); // добавляем элемент в первую позицию
        states.add     (1, "Италия"     ); // добавляем элемент с индексом 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 = 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.

Наверх
  Рейтинг@Mail.ru