Представяме Ви колекцията LinkedList

1. История наLinkedList

Java има друг клас колекция Java, наследен от езика C++. Това е LinkedListкласът, който имплементира "свързан списък".

Външно a LinkedListизглежда същото като ArrayList. Класът LinkedListима всички същите методи като ArrayListкласа. По принцип винаги можете да използвате a LinkedListinstead of an ArrayListи всичко ще работи.

Така че защо се нуждаем от друг клас списък?

Отговорът има всичко общо с вътрешната структура на LinkedListкласа. Вместо масив, той използва двойно свързан списък . Ще обясним Howво е това малко по-късно.

Различната вътрешна структура на класа LinkedListго прави най-бърз при вмъкване на елементи в средата на списъка.

В интернет често можете да намерите сравнения на ArrayListи LinkedListкласове:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

Всичко изглежда достатъчно ясно: ако трябва често да вмъквате елементи в списъка, използвайте LinkedList; ако рядко, използвайте ArrayList. Но реалността е малко по-различна.

2. Никой не използваLinkedList

Никой не използва LinkedList.

Дори авторът на LinkedListкласа наскоро туитна: „Някой използва ли всъщност LinkedList? Аз го написах и никога не го използвам.“

И така, Howва е сделката?

Първо, класът ArrayListзапочна да може много бързо да вмъква елементи в средата на списъка. Когато вмъквате елемент в средата на списъка, трябва да изместите всички елементи след точката на вмъкване с 1 към края на списъка. Преди това отнемаше време.

Но сега всичко се промени. Всички елементи на масива са близо един до друг в един и същ блок от паметта, така че операцията за изместване на елементите се извършва от много бърза команда от ниско ниво: .System.arraycopy()

В допълнение, днешните процесори имат голям кеш, който обикновено може да побере целия масив, което позволява елементите на масива да се преместват вътре в кеша, а не в паметта. Мorон елемента лесно се преместват за една мorсекунда.

Второ, класът LinkedListможе да вмъква елементи бързо, ако ги вмъкнете с помощта на итератор. Ако използвате итератор, за да преминете през a LinkedListи постоянно да вмъквате нови елементи (or премахвате съществуващи), операцията е супер бърза.

Ако просто добавите елементи към LinkedListобект вътре в цикъл, тогава всяка операция за бързо вмъкване е придружена от бавна операция "получаване на елемент".

Реалността е много по-близо до това:

add(value)

add(index, value)

get(index)

set(index, value)

remove(index)

it.add(value)

it.remove()

Защо получаването на елемент от LinkedListтакава бавна операция?

Можете да отговорите на този въпрос, след като се запознаете малко с това How LinkedListе структурирано.

3. Как LinkedListе структурирана

LinkedListима различна вътрешна структура от ArrayList. Няма вътрешен масив за съхранение на елементи. Вместо това той използва структура от данни, наречена списък с двойно мастило .

Всеки елемент от двойно свързан списък съхранява препратка към предишния елемент и следващия елемент. Това е нещо като опашка в магазин, където всеки човек помни човека, който стои пред него, Howто и този, който стои зад него.

Ето How изглежда такъв списък в паметта:

Главата и опашката (клетки със сив фон) са променливите firstи last, които съхраняват препратки към Nodeобекти.

В средата имате верига от Nodeобекти (обекти, не променливи). Всеки от тях се състои от три полета:

• prev— съхранява препратка (връзка) към предишния Nodeобект (клетки с жълт фон).
• value— съхранява стойността на този елемент от списъка (клетки със зелен фон).
• next— съхранява препратка (връзка) към следващия Nodeобект (клетки със син фон)

Вторият обект (address F24) е следващият ( next) за първия обект и предходният ( prev) за третия обект. Жълтото поле на третия обект съдържа address F24, а синьото поле на първия обект съдържа address F24.

Стрелките от първия и третия обект сочат към същия втори обект. Така че би било по-правилно да нарисувате стрелките така.

4. Вмъкване на елемент към свързан списък

За да добавите някого в подобна линия, просто трябва да получите разрешението на двама души, стоящи един до друг. Първият човек помни новодошлия като "човека зад мен", а вторият ги помни като "човека пред мен".

Всичко, което трябва да направите, е да промените препратките на двата съседни обекта:

Добавихме нов елемент към нашия списък, като променихме препратките на втория и третия обект. Новият обект е следващият за стария втори обект и предишният за стария трети обект. И, разбира се, самият нов обект трябва да съхранява правилните препратки: неговият предишен обект е старият втори обект, а следващият му обект е старият трети обект.

Премахването на елемент е още по-лесно: Ако искаме да премахнем, да кажем, 100-ия обект от списъка, просто трябва да променим полето nextза 99-ия обект, така че да сочи към 101-ия обект, и да променим полето prevза 101-ия обект, така че да сочи към 99-то. Това е.

Но получаването на 100-ия обект не е толкова лесно.

5. Премахване на елемент от списък

За да получите 100-ия елемент от свързан списък, трябва да:

Вземете първия обект: Правите това, като използвате firstпроменливата в LinkedListобекта. Полето nextна 1-ви обект съхранява препратка към 2-ри обект. Така получаваме втория обект. Вторият обект има препратка към третия и т.н.

Ако трябва да получим препратка към 100-ия обект, трябва последователно да преминем през всички обекти от 1-ви до 100-ти. И ако имаме нужда от мorонния елемент в списък, трябва да итерираме над мorон обекта един след друг!

И ако тези обекти са бor добавени към списъка по различно време, те ще бъдат разположени в различни части на паметта и е малко вероятно да се озоват в кеша на процесора по едно и също време. Това означава, че итерацията върху елементите на свързан списък е не просто бавна, а много бавна.

С това си имаме работа.

Така че защо ви учим How LinkedListработи това бавно?

Е, по време на интервюта за работа ще ви попитат How LinkedListсе различава отArrayList . Определено.