В чем разница между ArrayList и LinkedList?

ArrayList и LinkedList являются классами Collection, и оба они реализуют интерфейс List. LinkedList реализует его с двусвязным списком, в то время как ArrayList реализует его с помощью динамического массива перераспределения.

1. Операция поиска
2. Манипуляция
3. Поведение
4. Накладные расходы памяти

Операция поиска

Операция поиска в ArrayList довольно быстро по сравнению с операцией поиска LinkedList. Метод ArrayList get (int index) дает производительность O (1), в то время как производительность LinkedList равна O (n). Это связано с тем, что ArrayList позволяет произвольный доступ к элементам в списке, поскольку он работает с основанной на индексе структурой данных, в то время как LinkedList не разрешает произвольный доступ, поскольку он не имеет индексов для непосредственного доступа к элементам, он должен пересекать список для извлечения или получить доступ к элементу из списка.

Манипуляции

Манипуляция с ArrayList медленная, поскольку она внутренне использует массив. Если нам нужно вставить или удалить элемент в ArrayList, он может принимать O (n), поскольку он внутренне использует массив, и нам может потребоваться сдвинуть элементы в случае вставки или удаления. С другой стороны, манипуляции с LinkedList быстрее, чем ArrayList, потому что он использует двусвязный список, поэтому в памяти не требуется сдвиг бит. Если нам нужно вставить или удалить элемент в LinkedList, он будет принимать O (1), поскольку он внутренне использует дважды.

ArrayList - это более простая структура данных, чем LinkedList. ArrayList имеет один массив указателей в смежных ячейках памяти. Его нужно только воссоздать, если массив расширен за пределы выделенного размера. Но LinkedList состоит из цепочки узлов; каждый узел разделяется выделенным и имеет передние и задние указатели на другие узлы. Итак, если вам не нужно вставлять середину, сращивать, удалять в середине и т. Д., ArrayList обычно будет быстрее. Он нуждается в меньшем распределении памяти, имеет гораздо лучшую локальность ссылки (что важно для кэширования процессора) и т. Д.

Поведение

Arraylist ведет себя как List, поскольку он реализует список. LinkedList ведет себя как List a, а также Queue, поскольку он реализует List и Queue.

Накладные расходы памяти

ArrayList поддерживает индексы и данные элементов, в то время как LinkedList поддерживает данные элемента и два указателя для соседних узлов, следовательно, потребление памяти в LinkedList сравнительно велико.

Реализация ArrayList

 
import Java.util.*;
class TestClass {
  public static void main (String[] args) {
    // создаем список массивов Object
    ArrayList aList = new ArrayList();
    aList.add("Sunday"); // добавление элемента
    aList.add("Monday");
    aList.add("Tuesday");
    Iterator ir=aList.iterator();
    while(ir.hasNext()){
      System.out.println(ir.next());
  }
}

Выход

 
Sunday
Monday
Tuesday

Реализация LinkedList

 
import Java.util.*;
class TestClass {
  public static void main (String[] args) throws Java.lang.Exception {
    // создать новый связанный объект списка
    LinkedList days = new LinkedList();
    // добавление элементов в связанный список
    days.add("Monday");
    days.add("Tuesday");
    days.add("Wednesday");
    days.add("Thursday");
    days.addLast("Friday");
    // Отображение всего содержимого LinkedList
    Iterator < String > itr=days.iterator();
    while(itr.hasNext()){
      System.out.println(itr.next());
    }
    /*Add First and Last Element in linked list*/
    days.addFirst("Sunday");
    days.addLast("Saturday");
    System.out.println("After Addition: " + days);
    // Вставка элемента в связанный список
    days.add(0, "Days in a Week"); // добавить начало связанного списка
    days.add(4,"Middle"); // добавить в середине связанного списка
    days.add(9, "End");  // добавление в список lst связанного списка
    System.out.println("After Insertion: " + days);
  }
}

Выход

 
Monday
Tuesday
Wednesday
Thursday
Friday
After Addition: [Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday]
After Insertion: [Days in a Week, Sunday, Monday, Tuesday, Middle, Wednesday, Thursday, Friday, Saturday, End]

Источник: http://net-informations.com/Java/cJava/linkedlist.htm

(Пока оценок нет)