Структура на данни от свързани списъци в Java

Създават се различни структури от данни за различни цели. Може да знаете за ArrayList (ако все още не знаете, препоръчваме ви първо да прочетете за него). В тази статия ще научим за LinkedList и ще разберем за Howво е добра тази колекция. Ако погледнете източника на code на класа LinkedList Java 8 (or по-нова version на езика) (на уебсайта на Oracle or във вашата IDE, в случай на IDEA: crtl+B в името на класа), ще видите следващата декларация:

public class LinkedList<E>
   extends AbstractSequentialList<E>
   implements List<E>, Deque<E>, Cloneable, java.io.Serializable

В момента най-важната информация от codeа е фактът, че LinkedList имплементира List и Deque интерфейси. Интерфейсът List запазва последователността на добавяне на елементи и позволява достъп до елемента по индекс. „Обикновената“ опашка поддържа добавяне на елементи към края и извличането им от началото. Deque е двупосочна опашка и поддържа добавяне и премахване на елементи от двете страни. Може да мислите за това като комбинация от стек и опашка. И така, LinkedList е реализация на тези две и ни позволява да създадем двупосочна опашка, състояща се от всяHowви обекти, включително null. LinkedListе колекция от елементи. Можем да го видим в изходния code на класа, този път обърнете внимание на полетата:

transient int size = 0;
/**
* Pointer to first node.
*/
transient Node<E> first;
/**
* Pointer to last node.
*/
transient Node<E> last;

Всеки елемент, обикновено го наричаме Node , съдържа обект и препратки към два съседни обекта - предишния и следващия. Следователно не е много ефективен по отношение на използването на паметта. Тъй като LinkedList всъщност е двупосочна структура, можем лесно да добавяме or премахваме елементи от двете страни.

Конструктори на LinkedList

Обратно към източника на code, можем да разберем, че LinkedList има два конструктора

• LinkedList() без параметри се използва за конструиране на празен списък.
• >LinkedList(Collection<? extends E> c) е за създаване на списък, съдържащ елементите на посочената колекция, в ред, те се връщат от итератора на колекцията.

Декларация на LinkedList

Всъщност един свързан списък (Java or на друг език) се състои от поредица от възли. Всеки възел е проектиран да съхранява обект от тип, определен при създаването. Така че, за да създадете LinkedList , Java codeът е следният:

LinkedList<Integer> myList = new LinkedList<>();

Имаме обект, който да поддържа последователност от цели числа и връзки към съседите. В момента обаче е празен.

Основни операции на LinkedList

Както обикновено, в случай на колекции можете да поставите елементи в LinkedList (до края му or в средата), да премахнете оттам и да получите елемент по индекс. И така, ето ги:

• add(E element) Добавя посочения елемент в края на този списък;
• add(int index, E element) Вмъква елемента на указаната позиция index ;
• get(int index) Връща елемента на посочената позиция в този списък;
• remove(int index) Премахва елемента, който е на позиция index;
• remove(Object o) Премахва първото срещане на ? o елемент от този списък, ако е там.
• remove() Извлича и премахва първия елемент от списъка.

Реализация на свързан списък в Java, добавяне и премахване на елементи. Пример

Нека изпробваме тези операции на практика. Първо, изпълнение на Java LinkedList: създаване на LinkedList от низове, добавяне на 3 елемента. След това премахнете един, след това добавете един в средата.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
//  LinkedList implementation in Java
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println("my list after adding 3 elements:");
       System.out.println(linkedList);
       System.out.println("element #2 of my list:");
       System.out.println(linkedList.get(2));
       linkedList.remove(1);
       System.out.println("my list after removing #1:");
       System.out.println(linkedList);
       linkedList.add(1,"first");
       System.out.println("my list after adding an element in the middle");
       System.out.println(linkedList);
   }

Резултатът от стартирането на тази програма:

my list after adding 3 elements:
[my, favorite, book]
element #2 of my list:
book
my list after removing #1:
[my, book]
my list after adding an element in the middle
[my, first, book]

LinkedList е част от рамката на колекцията , можете да използвате Iterator за премахване на елементи, Howто и специален итератор за списъци — ListIterator . Нещо повече, операциите с итератор предоставят основните предимства на класа LinkedList : добра производителност на операциите за вмъкване/изтриване. Използвайки Iterator, можете да получите постоянно време за тях. По-късно в тази статия ще напишем примерен code за сравнение на ArrayList и LinkedList+Iterator

• Iterator.remove() премахва последния елемент, върнат от този итератор.
• ListIterator.add(E element) вмъква елемент в списъка

Пример за Java LinkedList: How работи Iterator

Тук имаме малък примерен code на Java LinkedList , където се опитваме да добавяме и изтриваме чрез Iterator.

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
 
       Iterator i = linkedList.iterator();
       String str = "";
       while (i.hasNext()) {
           str = (String)i.next();
           if (str.equals("favorite")) {
               i.remove();
               break;
           }
       }

       System.out.println("linkedList after removing element via Iterator:");
       System.out.println(linkedList);
       ListIterator listIterator = linkedList.listIterator();
       listIterator.add("I've got");
       System.out.println("linkedList after adding the element via ListIterator");
       System.out.println(linkedList);
 
   }
}

Резултатът от стартирането на тази програма:

linkedList after removing element via Iterator:
[my, book]
linkedList after adding the element via ListIterator
[I've got, my, book]

Още операции на Java LinkedList :

• addFirst() , addLast() добавяне на елемент в началото/края на списък
• clear() премахва всички елементи от списъка
• съдържа (Object o) връща true, ако списъкът съдържа o елемента.
• indexOf(Object o) връща индекса на първото срещане на елемента o or -1, ако не е в списъка.
• set(int index, E element) замества елемента в индексна позиция с елемента
• size() Връща количеството елементи в списъка.
• toArray() връща масив, съдържащ всички елементи на списъка от първия до последния елемент.

BTW тъй като е опашка с два размера, LinkedList в Java има специфични за стека операции:

• pop() , който изважда елемент от стека (представен от списъка)
• push(E e) , който избутва елемент в стека (представен от този списък)

Как да обърнете LinkedList: пример

Ето един малък пример, популярна, но лесна задача за начинаещи. Имаме LinkedList и трябва да го обърнем. Най-лесният алгоритъм е да преминете през LinkedList в обратен ред и да поставите всеки елемент в новия. Може би обаче ще намерите по-добър начин? Ето codeа на java програма с обратно свързан списък:

public class MyLinkedTest {
   public static void main(String[] args) {
       String h1 = "my";
       String h2 = "favorite";
       String h3 = "book";
       LinkedList<String> linkedList = new LinkedList();
       linkedList.add(h1);
       linkedList.add(h2);
       linkedList.add(h3);
       System.out.println(linkedList);
       System.out.println("Reversed LinkedList:");
       System.out.println(reverseLinkedList(linkedList));
   }
   public static LinkedList<String> reverseLinkedList(LinkedList<String> list)
   {
       LinkedList<String> LinkedList = new LinkedList<String>();
       for (int i = list.size() - 1; i >= 0; i--) {
           LinkedList.add(list.get(i));
       }
       return LinkedList;
   }
}

Резултатът:

[I've got, my, book]
Reversed LinkedList:
[book, my, I've got]

LinkedList срещу ArrayList: кога да използвате първия

Както LinkedList , така и ArrayList са реализации на интерфейса List . LinkedList го прилага с двойно свързан списък. ArrayList го прилага с помощта на масив с динамично преоразмеряване. Както вече знаете, всеки възел на LinkedList съдържа обекти и две препратки към съседите. Това означава допълнителни разходи за памет за съхраняване на препратки между елементи в случая на Java LinkedList . ArrayList го прилага с динамично преоразмеряващ масив. Някои от операциите LinkedList и ArrayList изглеждат еднакви, но работят по различен начин. В ArrayListслучай, вие манипулирате с вътрешни масиви, в LinkedList — с препратки. ArrayList е най-популярната реализация на List . Определено трябва да използвате ArrayList , когато достъпът до индекс е приоритет, тъй като тези операции се извършват в постоянно време. Добавянето към края на списъка средно също се извършва в постоянно време. Нещо повече, ArrayList няма допълнителни разходи за съхранение на куп елементи. Можете да считате за минуси скоростта на операциите по вмъкване и премахване, когато това не е в края на списъка. LinkedListе по-полезен в случай на изпълнение на операциите за вмъкване и изтриване по някои начини: ако използвате итератори, това се случва в постоянно време. Операциите за достъп по индекс се извършват чрез търсене от началото на края (което е по-близо) до желания елемент. Не забравяйте обаче за допълнителните разходи за съхранение на препратки между елементите. И така, тук са стандартните операции LinkedList и ArrayList с алгоритмично време за изпълнение. N се отнася до броя елементи, които вече са в списъка. O(N) означава, че в най-лошия случай трябва да се „разходим“ през целия списък, докато се намери желаната позиция, например за вмъкване на новия елемент в списъка. О(1)означава, че операцията се извършва в постоянно време, независимо от броя на елементите.

Времева сложност на LinkedList

Времева сложност на ArrayList

Кога да използвате LinkedList: Пример

Определено ArrayList е най-популярната реализация на List . Възможно е обаче да срещнете ситуации, когато операциите за добавяне/премахване са необходими твърде често. В такъв случай LinkedList заедно с Iterator може да бъде от полза. Ето един пример. Имаме дълъг списък и трябва да изтрием всеки елемент от този списък. Нека изпълним тази задача с ArrayList и LinkedList + Iterator . Сравняваме времето на всяка операция и го отпечатваме в конзолата. Ето codeа:

import java.util.*;
import java.util.function.BiPredicate;
 
public class ListTest2 {
 
   static void removeElements(List<Double> list, BiPredicate<Integer, Double> predicate) {
       // start navigation from end to preserve indexes of removed items
       ListIterator<Double> iterator = list.listIterator(list.size());
 
       while (iterator.hasPrevious()) {
           Double element = iterator.previous();
           if (predicate.test(iterator.previousIndex()+1, element)) {
               iterator.remove();
           }
       }
   }
 
   static class TestCase1 {
       public static void main(String[] args) {
           LinkedList<Double> testedList1 = new LinkedList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList1, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList1 after removeElements(..): " + testedList1);
 
           ArrayList<Double> testedList2 = new ArrayList<>(Arrays.asList(2.0,9.0,3.0,12.0,5.0));
           removeElements(testedList2, (index, value) -> (value % 3 == 0));
           // should print `[2.0, 5.0]`
           System.out.println("testedList2 after removeElements(..): " + testedList2);
       }
   }
 
   static class TestLinkedListPerformance {
       public static void main(String[] args) {
           LinkedList<Double> testedList = new LinkedList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `0.1527659`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
 
   static class TestArrayListPerformance {
       public static void main(String[] args) {
           ArrayList<Double> testedList = new ArrayList<>();
           System.out.println("start filling testedList");
           for (int i = 0; i < 2 * 1000 * 1000 ; ++i) {
               testedList.add((double)i);
           }
 
           System.out.println("start treating testedList");
           long startTime = System.nanoTime();
           removeElements(testedList, (index, value) -> (value % 3 == 0));
           long endTime = System.nanoTime();
           // should print `1333333`
           System.out.println("testedList.size after removeElements(..): " + testedList.size());
           // could print `53.4952635`
           System.out.println("removeElements(..) takes (seconds): " + ((double)(endTime - startTime)) / 1000000000);
       }
   }
}

Резултат за ArrayList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 481.8824414

Резултат за LinkedList:

start filling testedList
start treating testedList
testedList.size after removeElements(..): 1333333
removeElements(..) takes (seconds): 0.4586458

Както можете да видите в този случай LinkedList е много по-ефективен. Нека бъдем честни. В реалната разработка на софтуер използването на LinkedList е рядко срещано събитие. Въпреки това, професионалистът трябва да знае за съществуването на тази структура от данни и нейните предимства. Ако в реалния code LinkedList е рядък гост, в интервютата на Java Junior той е много популярен. И все пак, ето Howво написа Джошуа Блок за LinkedList :

AddOn: Единично свързан списък Java

Няма единично свързан списък сред класическата колекция в Java, единично свързан списък е структура, в която всеки възел съдържа обект и препратка към следващия възел, но не и за предишния. Java LinkedList е двусвързан, но никой не ви пречи да създадете своя собствена структура от данни, като например единичен ,code>Linked List. Ето няколко стъпки за решаване на тези задачи:

1. Създайте клас Node с два атрибута, data и next. Следва препратка към следващия възел.
2. Създайте клас FirstLast с два атрибута, head и tail.
3. Създайте метод add() , за да добавите нов възел към списъка. Първо проверете дали списъкът е празен ( head == null ). Ако е така, главата и опашката се отнасят за новия възел. Ако списъкът не е празен, новият възел ще бъде добавен в края, така че следващият атрибут на опашката се отнася до добавения възел и новият възел става опашката на списъка.

Между другото можете да опитате да създадете свой собствен LinkedList като упражнение. Успех в ученето.