MyTetra Share
Делитесь знаниями!
LinkedList
Время создания: 18.09.2017 10:51
Текстовые метки: knowledge
Раздел: Java - DataStructures - LinedList
Запись: xintrea/mytetra_db_mcold/master/base/15057210886ft8t5f7ea/text.html на raw.githubusercontent.com

Структуры данных в картинках. 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. Для хранения примитивных типов использует соответствующие классы-оберки;
— Не синхронизирован.

 
MyTetra Share v.0.60
Яндекс индекс цитирования