Связанный список Java

Связанный список Java

В этом руководстве мы подробно узнаем о Java LinkedList с помощью примеров.

LinkedList класс платформы коллекций Java обеспечивает функциональность структуры данных связанного списка (двойной связанный список).

<рисунок>

Каждый элемент в связанном списке называется узлом. . Он состоит из 3 полей:

• Предыдущая - сохраняет адрес предыдущего элемента в списке. Это null для первого элемента
• Далее - сохраняет адрес следующего элемента в списке. Это null для последнего элемента
• Данные - сохраняет фактические данные

<час>

Создание связанного списка Java

Вот как мы можем создавать связанные списки в Java:

LinkedList<Type> linkedList = new LinkedList<>();

Здесь Введите указывает тип связанного списка. Например,

// create Integer type linked list
LinkedList<Integer> linkedList = new LinkedList<>();

// create String type linked list
LinkedList<String> linkedList = new LinkedList<>();

<час>

Пример:создание LinkedList в Java

import java.util.LinkedList;

class Main {
  public static void main(String[] args){

    // create linkedlist
    LinkedList<String> animals = new LinkedList<>();

    // Add elements to LinkedList
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Cow");
    System.out.println("LinkedList: " + animals);
  }
}

Вывод

LinkedList: [Dog, Cat, Cow]

В приведенном выше примере мы создали LinkedList названные животные .

Здесь мы использовали add() метод для добавления элементов в LinkedList. Мы узнаем больше о add() метод далее в этом руководстве.

<час>

Работа со связанным списком Java

Элементы в связанных списках не сохраняются последовательно. Вместо этого они разбросаны и связаны ссылками (Предыдущая и Далее ).

<рисунок>

Здесь у нас есть 3 элемента в связанном списке.

• Собака - это первый элемент, который содержит null как предыдущий адрес и адрес Cat как следующий адрес
• Кот - это второй элемент, который содержит адрес Dog как предыдущий адрес и адрес Cow как следующий адрес
• Корова - это последний элемент, содержащий адрес Cat как предыдущий адрес и null как следующий элемент

Чтобы узнать больше, посетите страницу «Структура данных LinkedList».

<час>

Методы связанного списка Java

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

• Добавить элементы
• Доступ к элементам
• Изменить элементы
• Удалить элементы

<час>

1. Добавить элементы в LinkedList

Мы можем использовать add() метод для добавления элемента (узла) в конец LinkedList. Например,

import java.util.LinkedList;

class Main {
  public static void main(String[] args){
    // create linkedlist
    LinkedList<String> animals = new LinkedList<>();

    // add() method without the index parameter
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Cow");
    System.out.println("LinkedList: " + animals);

    // add() method with the index parameter
    animals.add(1, "Horse");
    System.out.println("Updated LinkedList: " + animals);
  }
}

Вывод

LinkedList: [Dog, Cat, Cow]
Updated LinkedList: [Dog, Horse, Cat, Cow]

В приведенном выше примере мы создали LinkedList с именем animals. . Здесь мы использовали add() метод добавления элементов в животных .

Обратите внимание на заявление,

animals.add(1, "Horse");

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

Чтобы узнать больше о добавлении элементов в LinkedList, посетите программу Java для добавления элементов в LinkedList.

<час>

2. Доступ к элементам LinkedList

get() Метод класса LinkedList используется для доступа к элементу из LinkedList. Например,

import java.util.LinkedList;

class Main {
  public static void main(String[] args) {
    LinkedList<String> languages = new LinkedList<>();

    // add elements in the linked list
    languages.add("Python");
    languages.add("Java");
    languages.add("JavaScript");
    System.out.println("LinkedList: " + languages);

    // get the element from the linked list
    String str = languages.get(1);
    System.out.print("Element at index 1: " + str);
  }
}

Вывод

LinkedList: [Python, Java, JavaScript]
Element at index 1: Java

В приведенном выше примере мы использовали get() метод с параметром 1 . Здесь метод возвращает элемент с индексом 1. .

Мы также можем получить доступ к элементам LinkedList, используя iterator() и listIterator() метод. Чтобы узнать больше, посетите программу Java для доступа к элементам LinkedList.

<час>

3. Изменить элементы LinkedList

set() метод LinkedList класс используется для изменения элементов LinkedList. Например,

import java.util.LinkedList;

class Main {
  public static void main(String[] args) {
    LinkedList<String> languages = new LinkedList<>();

    // add elements in the linked list
    languages.add("Java");
    languages.add("Python");
    languages.add("JavaScript");
    languages.add("Java");
    System.out.println("LinkedList: " + languages);

    // change elements at index 3
    languages.set(3, "Kotlin");
    System.out.println("Updated LinkedList: " + languages);
  }
}

Вывод

LinkedList: [Java, Python, JavaScript, Java]
Updated LinkedList: [Java, Python, JavaScript, Kotlin]

В приведенном выше примере мы создали именованный список языков LinkedList. Обратите внимание на строку,

languages.set(3, "Kotlin");

Здесь set() метод изменяет элемент с индексом 3 в Котлин .

<час>

4. Удалить элемент из LinkedList

remove() метод LinkedList класс используется для удаления элемента из LinkedList. Например,

import java.util.LinkedList;

class Main {
  public static void main(String[] args) {
    LinkedList<String> languages = new LinkedList<>();

    // add elements in LinkedList
    languages.add("Java");
    languages.add("Python");
    languages.add("JavaScript");
    languages.add("Kotlin");
    System.out.println("LinkedList: " + languages);

    // remove elements from index 1
    String str = languages.remove(1);
    System.out.println("Removed Element: " + str);

    System.out.println("Updated LinkedList: " + languages);
  }
}

Вывод

LinkedList: [Java, Python, JavaScript, Kotlin]
Removed Element: Python
New LinkedList: [Java, JavaScript, Kotlin]

Здесь remove() Метод принимает номер индекса в качестве параметра. И удаляет элемент, указанный номером индекса.

Чтобы узнать больше об удалении элементов из связанного списка, посетите программу Java для удаления элементов из LinkedList..

<час>

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

Методы	Описание
contains()	проверяет, содержит ли LinkedList элемент
indexOf()	возвращает индекс первого вхождения элемента
lastIndexOf()	возвращает индекс последнего вхождения элемента
clear()	удаляет все элементы LinkedList
iterator()	возвращает итератор для перебора LinkedList

<час>

LinkedList как Deque и Queue

Поскольку LinkedList класс также реализует интерфейс Queue и Deque, он также может реализовывать методы этих интерфейсов. Вот некоторые из часто используемых методов:

Методы	Описания
addFirst()	добавляет указанный элемент в начало связанного списка
addLast()	добавляет указанный элемент в конец связанного списка
getFirst()	возвращает первый элемент
getLast()	возвращает последний элемент
removeFirst()	удаляет первый элемент
removeLast()	удаляет последний элемент
peek()	возвращает первый элемент (заголовок) связанного списка
poll()	возвращает и удаляет первый элемент из связанного списка
offer()	добавляет указанный элемент в конец связанного списка

Пример:Java LinkedList как очередь

import java.util.LinkedList;
import java.util.Queue;

class Main {
  public static void main(String[] args) {
    Queue<String> languages = new LinkedList<>();

    // add elements
    languages.add("Python");
    languages.add("Java");
    languages.add("C");
    System.out.println("LinkedList: " + languages);

    // access the first element
    String str1 = languages.peek();
    System.out.println("Accessed Element: " + str1);

    // access and remove the first element
    String str2 = languages.poll();
    System.out.println("Removed Element: " + str2);
    System.out.println("LinkedList after poll(): " + languages);

    // add element at the end
    languages.offer("Swift");
    System.out.println("LinkedList after offer(): " + languages);
  }
}

Вывод

LinkedList: [Python, Java, C]
Accessed Element: Python
Removed Element: Python
LinkedList after poll(): [Java, C]
LinkedList after offer(): [Java, C, Swift]

<час>

Пример:LinkedList как очередь

import java.util.LinkedList;
import java.util.Deque;

class Main {
  public static void main(String[] args){
    Deque<String> animals = new LinkedList<>();

    // add element at the beginning
    animals.add("Cow");
    System.out.println("LinkedList: " + animals);

    animals.addFirst("Dog");
    System.out.println("LinkedList after addFirst(): " + animals);

    // add elements at the end
    animals.addLast("Zebra");
    System.out.println("LinkedList after addLast(): " + animals);

    // remove the first element
    animals.removeFirst();
    System.out.println("LinkedList after removeFirst(): " + animals);

    // remove the last element
    animals.removeLast();
    System.out.println("LinkedList after removeLast(): " + animals);
  }
}

Вывод

LinkedList: [Cow]
LinkedList after addFirst(): [Dog, Cow]
LinkedList after addLast(): [Dog, Cow, Zebra]
LinkedList after removeFirst(): [Cow, Zebra]
LinkedList after removeLast(): [Cow]

<час>

Итерация по LinkedList

Мы можем использовать цикл for-each в Java для перебора LinkedList. Например,

import java.util.LinkedList;

class Main {
    public static void main(String[] args) {
        // Creating a linked list
        LinkedList<String> animals = new LinkedList<>();
        animals.add("Cow");
        animals.add("Cat");
        animals.add("Dog");
        System.out.println("LinkedList: " + animals);

        // Using forEach loop
        System.out.println("Accessing linked list elements:");
        for(String animal: animals) {
            System.out.print(animal);
            System.out.print(", ");
        }
    }
}

Вывод

LinkedList: [Cow, Cat, Dog]
Accessing linked list elements:
Cow, Cat, Dog,

<час>

LinkedList vs. Список массивов

И Java ArrayList, и LinkedList реализует List интерфейс Collections рамки. Однако между ними существует некоторая разница.

Связанный список	Список массивов
Реализует List , Queue и Deque интерфейсы.	Реализует List интерфейс.
Сохраняет 3 значения (предыдущий адрес , данные и следующий адрес ) в одной позиции.	Сохраняет одно значение в одной позиции.
Предоставляет реализацию двусвязного списка.	Предоставляет реализацию массива с изменяемым размером.
Каждый раз, когда добавляется элемент, prev и next адрес изменен.	Всякий раз, когда добавляется элемент, все элементы после этой позиции сдвигаются.
Чтобы получить доступ к элементу, нам нужно выполнить итерацию от начала до элемента.	Может произвольно обращаться к элементам с помощью индексов.

<час>

Примечание :Мы также можем создать LinkedList, используя интерфейсы в Java. Например,

// create linkedlist using List
List<String> animals1 = new LinkedList<>();

// creating linkedlist using Queue
Queue<String> animals2 = new LinkedList<>();

// creating linkedlist using Deque
Deque<String> animals3 = new LinkedList<>();

Здесь, если LinkedList создается с использованием одного интерфейса, мы не можем использовать методы, предоставляемые другими интерфейсами. То есть животные1 нельзя использовать методы, специфичные для Queue и Deque интерфейсы.