Приветствую вас, хабражители!
Продолжаю начатое, а именно, пытаюсь рассказать (с применением визуальных образов) о том как реализованы некоторые структуры данных в Java.
В прошлый раз мы говорили об ArrayList, сегодня присматриваемся к LinkedList.
LinkedList — реализует интерфейс List. Является представителем двунаправленного списка, где каждый элемент структуры содержит указатели на предыдущий и следующий элементы. Итератор поддерживает обход в обе стороны. Реализует методы получения, удаления и вставки в начало, середину и конец списка. Позволяет добавлять любые элементы в том числе и null.
Только что созданный объект list, содержит свойства header и size.
header — псевдо-элемент списка. Его значение всегда равно null, a свойства next и prev всегда указывают на первый и последний элемент списка соответственно. Так как на данный момент список еще пуст, свойства next и prev указывают сами на себя (т.е. на элемент header). Размер списка size равен 0.
Добавление элемента в конец списка с помощью методом add(value), addLast(value)
и добавление в начало списка с помощью addFirst(value) выполняется за время O(1).
Внутри класса LinkedList существует static inner класс Entry, с помощью которого создаются новые элементы.
Каждый раз при добавлении нового элемента, по сути выполняется два шага:
1) создается новый новый экземпляр класса Entry
2) переопределяются указатели на предыдущий и следующий элемент
Добавим еще один элемент
1)
2)
Для того чтобы добавить элемент на определенную позицию в списке, необходимо вызвать метод add(index, value). Отличие от add(value) состоит в определении элемента перед которым будет производиться вставка
Метод entry(index) пробегает по всему списку в поисках элемента с указанным индексом. Направление обхода определяется условием (index < (size >> 1)). По факту получается что для нахождения нужного элемента перебирается не больше половины списка, но с точки зрения асимптотического анализа время на поиск растет линейно — O(n).
Как видно, разработчик может словить IndexOutOfBoundsException, если указанный индекс окажется отрицательным или большим текущего значения size. Это справедливо для всех методов где в параметрах фигурирует индекс.
1)
2)
Удалять элементы из списка можно несколькими способами:
— из начала или конца списка с помощью removeFirst(), removeLast() за время O(1);
— по индексу remove(index) и по значению remove(value) за время O(n).
Рассмотрим удаление по значению
Внутри метода remove(value) просматриваются все элементы списка в поисках нужного. Удален будет лишь первый найденный элемент.
В общем, удаление из списка можно условно разбить на 3 шага:
1) поиск первого элемента с соответствующим значением
2) переопределяются указатели на предыдущий и следующий элемент
3) удаление указателей на другие элементы и предание забвению самого элемента
Для собственноручного перебора элементов можно воспользоваться «встроенным» итератором. Сильно углубляться не буду, процессы протекающие внутри, очень похожи на то что описано выше.
Приведенный выше код поместит указатель в начало списка. Так же можно начать перебор элементов с определенного места, для этого нужно передать индекс в метод listIterator(index). В случае, если необходимо начать обход с конца списка, можно воспользоваться методом descendingIterator().
Стоит помнить, что ListIterator свалится с ConcurrentModificationException, если после создания итератора, список был изменен не через собственные методы итератора.
Ну и на всякий случай примитивный пример перебора элементов:
— Из 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).
Продолжаю начатое, а именно, пытаюсь рассказать (с применением визуальных образов) о том как реализованы некоторые структуры данных в 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).
