Java for Beginner

LinkedList, отличие от ArrayList

LinkedList — это одна из реализаций интерфейса List в Java. Он представляет собой двусвязный список, где каждый элемент содержит ссылки на предыдущий и следующий элементы. LinkedList подходит для сценариев, где часто выполняются операции вставки и удаления элементов в середине списка.

Особенности LinkedList

Двусвязный список:
Каждый элемент в LinkedList содержит ссылки на предыдущий и следующий элементы, что позволяет эффективно добавлять и удалять элементы в середине списка.

Доступ к элементам:
В отличие от ArrayList, доступ к элементам в LinkedList осуществляется линейным поиском, что делает его менее эффективным для операций случайного доступа.

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

Не синхронизированность:
Как и ArrayList, LinkedList не является потокобезопасной коллекцией. В многопоточных средах требуется внешняя синхронизация.

Отличие от ArrayList

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

Время доступа:
ArrayList обеспечивает быстрый доступ к элементам по индексу (O(1)), в то время как LinkedList требует линейного времени (O(n)) для доступа к элементам по индексу.

Вставка и удаление элементов:
Вставка и удаление элементов в середине списка эффективнее в LinkedList (O(1)), в то время как в ArrayList эти операции требуют сдвига элементов и выполняются за время O(n).

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

Примеры использования

import java.util.LinkedList;
import java.util.List;

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

        // Добавление элементов
        linkedList.add("Apple");
        linkedList.add("Banana");
        linkedList.add("Cherry");

        // Получение элемента
        System.out.println("First element: " + linkedList.get(0)); // Apple

        // Вставка элемента
        linkedList.add(1, "Orange");
        System.out.println("After insertion: " + linkedList); // [Apple, Orange, Banana, Cherry]

        // Удаление элемента
        linkedList.remove("Banana");
        System.out.println("After removal: " + linkedList); // [Apple, Orange, Cherry]

        // Итерация по элементам
        for (String fruit : linkedList) {
            System.out.println(fruit);
        }
    }
}

Ссылки на полезные статьи (спасибо авторам за проделанную работу) :
https://habr.com/ru/articles/127864/
https://javarush.com/groups/posts/1938-linkedlist

#Java #Training #Medium #LinkedList

Хабр

Структуры данных в картинках. LinkedList

Приветствую вас, хабражители! Продолжаю начатое, а именно, пытаюсь рассказать (с применением визуальных образов) о том как реализованы некоторые структуры данных в Java. В прошлый раз мы говорили об...

166 viewsДен, 05:24

Java for Beginner

Внутреннее устройство и основные методы LinkedList

LinkedList основан на структуре данных двусвязного списка. Каждый элемент списка представлен узлом (Node), который содержит данные и ссылки на предыдущий и следующий узлы.

Класс Node:

Класс Node — это внутренний класс LinkedList, который представляет элемент списка.

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Узлы:

LinkedList содержит ссылки на первый (first) и последний (last) узлы списка.

transient Node<E> first;
transient Node<E> last;

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

При добавлении элемента в конец списка создается новый узел, и ссылки next и prev соответствующим образом обновляются.

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

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

Удаление элемента включает обновление ссылок next и prev соседних узлов.

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

Поиск узла:

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

Node<E> node(int index) {
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

Основные методы LinkedList

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

add(E e): добавляет элемент в конец списка.
add(int index, E element): вставляет элемент по указанному индексу.

linkedList.add("Apple");
linkedList.add(1, "Orange");

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

remove(int index): удаляет элемент по указанному индексу.
remove(Object o): удаляет первое вхождение указанного элемента.

linkedList.remove(1);
linkedList.remove("Apple");

Получение элементов:

get(int index): возвращает элемент по указанному индексу.
getFirst(), getLast(): возвращают первый и последний элементы соответственно.

String first = linkedList.getFirst();
String element = linkedList.get(1);

Другие методы:

size(): возвращает количество элементов в списке.
clear(): удаляет все элементы из списка.
contains(Object o): проверяет, содержится ли указанный элемент в списке.

int size = linkedList.size();
linkedList.clear();
boolean containsApple = linkedList.contains("Apple");

#Java #Training #Medium #LinkedList

171 viewsДен, 13:50

About

Blog

Apps

Platform