Пользователь
0,0
рейтинг
22 сентября 2011 в 11:32

Разработка → Структуры данных в картинках. LinkedList

JAVA*
Приветствую вас, хабражители!

Продолжаю начатое, а именно, пытаюсь рассказать (с применением визуальных образов) о том как реализованы некоторые структуры данных в Java.



В прошлый раз мы говорили об ArrayList, сегодня присматриваемся к LinkedList.

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



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


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

Footprint{Objects=2, References=4, Primitives=[int x 2]}
Object size: 48 bytes

Только что созданный объект list, содержит свойства header и size.

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

header.next = header.prev = header;





Добавление элементов


list.add("0");

Footprint{Objects=5, References=8, Primitives=[int x 5, char]}
Object size: 112 bytes

Добавление элемента в конец списка с помощью методом add(value), addLast(value)
и добавление в начало списка с помощью addFirst(value) выполняется за время O(1).

Внутри класса LinkedList существует static inner класс 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;
    }
}

Каждый раз при добавлении нового элемента, по сути выполняется два шага:

1) создается новый новый экземпляр класса Entry


Entry newEntry = new Entry("0", header, header.prev);




2) переопределяются указатели на предыдущий и следующий элемент


newEntry.prev.next = newEntry;
newEntry.next.prev = newEntry;
size++;




Добавим еще один элемент

list.add("1");

Footprint{Objects=8, References=12, Primitives=[int x 8, char x 2]}
Object size: 176 bytes

1)

// header.prev указывает на элемент с индексом 0
Entry newEntry = new Entry("1", header, header.prev);



2)




Добавление элементов в «середину» списка


Для того чтобы добавить элемент на определенную позицию в списке, необходимо вызвать метод add(index, value). Отличие от add(value) состоит в определении элемента перед которым будет производиться вставка

(index == size ? header : entry(index))

Метод entry(index) пробегает по всему списку в поисках элемента с указанным индексом. Направление обхода определяется условием (index < (size >> 1)). По факту получается что для нахождения нужного элемента перебирается не больше половины списка, но с точки зрения асимптотического анализа время на поиск растет линейно — O(n).


private Entry<E> entry(int index)
{
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);

    Entry<E> e = header;

    if (index < (size >> 1))
    {
        for (int i = 0; i <= index; i++)
            e = e.next;
    }
    else
    {
        for (int i = size; i > index; i--)
            e = e.prev;
    }

    return e;
}

Как видно, разработчик может словить IndexOutOfBoundsException, если указанный индекс окажется отрицательным или большим текущего значения size. Это справедливо для всех методов где в параметрах фигурирует индекс.

list.add(1, "100");

Footprint{Objects=11, References=16, Primitives=[int x 11, char x 5]}
Object size: 248 bytes

1)

// entry указывает на элемент с индексом 1, entry.prev на элемент с индексом 0
Entry newEntry = new Entry("100", entry, entry.prev);



2)




Удаление элементов


Удалять элементы из списка можно несколькими способами:
— из начала или конца списка с помощью removeFirst(), removeLast() за время O(1);
— по индексу remove(index) и по значению remove(value) за время O(n).

Рассмотрим удаление по значению

list.remove("100");

Footprint{Objects=8, References=12, Primitives=[int x 8, char x 2]}
Object size: 176 bytes

Внутри метода remove(value) просматриваются все элементы списка в поисках нужного. Удален будет лишь первый найденный элемент.

В общем, удаление из списка можно условно разбить на 3 шага:

1) поиск первого элемента с соответствующим значением



2) переопределяются указатели на предыдущий и следующий элемент


// Значение удаляемого элемента сохраняется
// для того чтобы в конце метода вернуть его
E result = e.element;
e.prev.next = e.next;
e.next.prev = e.prev;



3) удаление указателей на другие элементы и предание забвению самого элемента


e.next = e.prev = null;
e.element = null;
size--;





Итераторы


Для собственноручного перебора элементов можно воспользоваться «встроенным» итератором. Сильно углубляться не буду, процессы протекающие внутри, очень похожи на то что описано выше.


ListIterator<String> itr = list.listIterator();

Приведенный выше код поместит указатель в начало списка. Так же можно начать перебор элементов с определенного места, для этого нужно передать индекс в метод listIterator(index). В случае, если необходимо начать обход с конца списка, можно воспользоваться методом descendingIterator().

Стоит помнить, что ListIterator свалится с ConcurrentModificationException, если после создания итератора, список был изменен не через собственные методы итератора.

Ну и на всякий случай примитивный пример перебора элементов:


while (itr.hasNext())
    System.out.println(itr.next());



Итоги


— Из LinkedList можно организовать стэк, очередь, или двойную очередь, со временем доступа O(1);
— На вставку и удаление из середины списка, получение элемента по индексу или значению потребуется линейное время O(n). Однако, на добавление и удаление из середины списка, используя ListIterator.add() и ListIterator.remove(), потребуется O(1);
— Позволяет добавлять любые значения в том числе и null. Для хранения примитивных типов использует соответствующие классы-оберки;
— Не синхронизирован.


Ссылки


Исходники LinkedList
Исходники LinkedList из JDK7
Исходники JDK OpenJDK & trade 6 Source Release — Build b23

Объем занимаемой памяти измерялся с помощью инструмента memory-measurer. Для его использования также понадобится Guava (Google Core Libraries).
@tarzan82
карма
92,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (18)

  • +1
    Спасибо — очень просто написано и легко для понимания.

    Nibbler порадовал :-)
  • 0
    Хороший цикл статей. Спасибо!
  • +5
    В связи со статьей возник вопрос: кто-нибудь в реальном проекте когда-либо использовал LinkedList?

    Из своего опыта скажу, что даже в тех случаях, когда он по идее должен был дать прирост в производительности — т.е. большой список с частым удалением и добавлением элементов в середину и начало списка — ArrayList все равно оказывался быстрее.

    Объяснение простое: ArrayList внутри себя использует System.arrayCopy — нативную функцию, которая отрабатывает на удивление шустро. В то же время для LinkedList'а приходится переопределять несколько указателей, но это не самое главное. Все эти указатели на предыдущего и следующего обходятся сборщиком мусора. Из-за этого растет время, необходимое для стадии маркинга, а с учетом того, что в одном списке оказываются элементы из разных поколений, вся процедура затягивается еще больше.

    В единственный раз, когда LinkedList почти догнал ArrayList по производительности, я решил попробовать PersistentVector из Clojure, и тот оказался в полтора раза быстрее обоих. PersistentVector внутри представляет из себя дерево массивов, поэтому операции вставки приводят к изменению только одного или нескольких сегментов дерева, т.е. одной или нескольким операциям arrayCopy, которая для небольших массивов остается непревзойденной по скорости.

    Так что остается ощущение, что LinkedList остается в JDK только для того, чтобы у кандидатов на интервью про его эффективность вопросы задавать.
    • +5
      В LinkedList добавление в конец или начало списка будет производиться всегда за одинаковое время независимо от текущего размера списка. Если вы не знаете какого размера будет ваш список заранее, то (ИМХО) для операции составления больших списков, лучше использовать LinkedList.
      • 0
        Да, это ясно, но ведь список будет какое-то время жить в рантайме, по нему нужно будет итерироваться, и с учетом того, что мы добавляем туда элементы, итерироваться придется неоднократно. А это довольно дорогая операция по сравнению с ArrayList'ом.

        Если нам так уж нужно, чтобы элементы находились в определенном порядке, не лучше ли формализовать этот порядок в виде компаратора и использовать SortedSet?

        А если порядок не нужен, почему бы не добавлять элементы в конец списка?

        А если ожидаемое количество элементов известно, не проще ли создать ArrayList с заданным первоначальным размером?

        А если все-таки, несмотря на все вышеперечисленные предложения, больше подходит LinkedList, не стоит ли посмотреть в сторону B-деревьев?

        Есть только один сценарий, при котором LinkedList уместен — когда он стоит в основе реализации очереди, используемой несколькими потоками.
        • 0
          В бинарных деревьях удобно искать, а не добавлять. Процесс добавления может иногда может вызывать перестроение дерева, что «дорого».
          В LinkedList же все наоборот, по крайней мере при добавлении в конец(начало).
          • +2
            Думаю, что от связанных списков вообще важна идея ) а в качестве отдельных элементов подоблного списка уже давно используют массивы.
    • +1
      Я использовал. LinkedList реализует Queue. Там где нет потенциальных состязаний LinkedList меня устраивает.
      • +1
        ArrayList тоже устроит, не так ли? :-)
    • 0
      Точно такой же вопрос возник с самого начала статьи. Помню времена, когда на еще на Паскале я делал разные динамические структуры в качестве задания… Кольцевой LinkedList я использовал для хранения виджетов в контейнере, чтобы удобней было Tab-ом фокус переключать.

      Вообще LinkedList не позволяет random-access и может обрабатываться только последовательно. Поэтому область его применения сильно ограничена. ArrayList реально работает и быстрее и эффективнее.
    • 0
      Согласен, что очень специфичный и редко используемый контейнер. Для интереса запустил поиск по исходникам, которые когда-то писал… Примеры нашёл, хотя везде бы и ArrayList нормально сработал.

      Вот пример: история введённых URL в программе с GUI. При введении нового адреса надо добавить его в начало списка, а если он уже был где-то в списке, то старый элемент удалить (чтобы не было дубликатов).

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

      Еще нашёлся пример с задачкой с diofant.ru: в алгоритме надо было в списке городов часто удалять из середины города по известному названию.
      • +1
        В LinkedList итерирование займет больше, чем копирование части массива в ArrayList. Это утверждение верно как минимум для <=1024 элементов (проверено)
        • 0
          В обоих случаях (ArrayList и LinkedList) удаление дубликата потребует линейного времени.
          Здесь подойдет LinkedHashSet: как и в списке, порядок элементов сохраняется, а удаление и добавление занимают постоянное время.
  • 0
    В итогах опечаточка. O(1) — из концов списка.
    • 0
      Если вы про
      на добавление и удаление из середины списка, используя ListIterator.add() и ListIterator.remove(), потребуется O(1)
      то здесь всё верно написано. Загляните в исходник, в этих методах нет перебора элементов.
      • 0
        O(1), когда итератор уже «дошел» до нужного элемента. Если посмотреть в доку, то там сказано, что будет удален последний элемент, возвращенный методом next() (или previous()). А вот чтобы дойти до нужного элемента потребуется О(n/2) = O(n).
  • 0
    Однозначно в закладки. И периодически пересчитывать. Отличный цикл статей где можно сжато почитать о многом и освежевать в памяти забытые знания.
    • +3
      Знания всё-таки освежают, освежевывать их — это как-то уж слишком сурово :)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.