отличия arraylist от linkedlist

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

Пример 1: Добавление элементов

ArrayList

При добавлении элементов в ArrayList, если массив заполнен, он должен быть увеличен, что может занять время O(n) из-за копирования элементов.

import java.util.ArrayList;

public class ArrayListExample {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();

        // Добавление элементов
        for (int i = 0; i < 100000; i++) {
            arrayList.add(i);
        }

        System.out.println("Размер ArrayList: " + arrayList.size());
    }
}

LinkedList

При добавлении элементов в LinkedList, если вы добавляете в конец, это занимает O(1), так как просто создается новый узел и обновляются ссылки.

import java.util.LinkedList;

public class LinkedListExample {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();

        // Добавление элементов
        for (int i = 0; i < 100000; i++) {
            linkedList.add(i);
        }

        System.out.println("Размер LinkedList: " + linkedList.size());
    }
}

Пример 2: Удаление элементов

ArrayList

При удалении элемента из ArrayList, все элементы после удаляемого должны быть сдвинуты, что занимает O(n).

import java.util.ArrayList;

public class ArrayListRemoveExample {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();

        // Заполнение списка
        for (int i = 0; i < 100000; i++) {
            arrayList.add(i);
        }

        // Удаление элемента
        arrayList.remove(50000); // Удаляем элемент с индексом 50000
        System.out.println("Размер ArrayList после удаления: " + arrayList.size());
    }
}

LinkedList

При удалении элемента из LinkedList, если вы знаете узел, это занимает O(1), так как просто обновляются ссылки.

import java.util.LinkedList;

public class LinkedListRemoveExample {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();

        // Заполнение списка
        for (int i = 0; i < 100000; i++) {
            linkedList.add(i);
        }

        // Удаление элемента
        linkedList.remove(50000); // Удаляем элемент с индексом 50000
        System.out.println("Размер LinkedList после удаления: " + linkedList.size());
    }
}

Пример 3: Доступ по индексу

ArrayList

Доступ к элементам по индексу в ArrayList выполняется за O(1).

import java.util.ArrayList;

public class ArrayListAccessExample {
    public static void main(String[] args) {
        ArrayList<Integer> arrayList = new ArrayList<>();

        // Заполнение списка
        for (int i = 0; i < 100000; i++) {
            arrayList.add(i);
        }

        // Доступ к элементу
        int element = arrayList.get(50000); // Получаем элемент с индексом 50000
        System.out.println("Элемент с индексом 50000: " + element);
    }
}

LinkedList

Доступ к элементам по индексу в LinkedList выполняется за O(n), так как необходимо пройти по узлам.

import java.util.LinkedList;

public class LinkedListAccessExample {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();

        // Заполнение списка
        for (int i = 0; i < 100000; i++) {
            linkedList.add(i);
        }

        // Доступ к элементу
        int element = linkedList.get(50000); // Получаем элемент с индексом 50000
        System.out.println("Элемент с индексом 50000: " + element);
    }
}

Когда использовать ArrayList, а когда LinkedList? (продолжение)

• Используйте ArrayList, когда:
• Вам нужен быстрый доступ к элементам по индексу.
• Вы часто добавляете элементы в конец списка и не планируете часто удалять элементы из середины или начала.

• Память важна, и вы хотите минимизировать накладные расходы на хранение дополнительных ссылок (как в случае с LinkedList).

• Используйте LinkedList, когда:

• Вам нужно часто добавлять или удалять элементы из начала или середины списка.
• Вы не нуждаетесь в быстром доступе по индексу и можете позволить себе время O(n) для доступа к элементам.
• Вы работаете с большими объемами данных, где частые операции вставки и удаления могут значительно повлиять на производительность ArrayList.

Заключение

В зависимости от требований вашего приложения, выбор между ArrayList и LinkedList может существенно повлиять на производительность.

• Если ваша задача требует частого доступа к элементам по индексу и вы не планируете часто изменять размер списка, ArrayList будет более эффективным выбором.
• Если же вам нужно часто добавлять и удалять элементы, особенно в начале или середине списка, LinkedList будет более подходящим вариантом.

Понимание этих различий и особенностей поможет вам принимать более обоснованные решения при выборе структуры данных для ваших приложений.