Вопросы о связанном списке Java

Question

Я пытаюсь понять, как связанные списки реализованы в Java.

Должен ли я создавать отдельные классы связанных списков для списков и узлов, или я могу просто вызвать import java.util.LinkedList, или нам нужны оба?

Кроме того, нам нужен итератор для печати списка?

Answer 1

Вы задали несколько разных вопросов здесь. Я думаю, что я обратился ко всем здесь, так что дайте мне знать, если я что-то пропустил:

1. Если ваша цель - быть клиентом из связанного списка, вам следует просто использовать java.util.LinkedList. Это предварительно написанная оптимизированная реализация связанного списка, которая подходит для большинства приложений.

2. Если ваша цель - реализовать связанный список, то вам, по крайней мере, понадобится класс, представляющий узел связанного списка. В зависимости от вашего варианта использования, вы также можете подумать о создании класса, который, подобно LinkedList, инкапсулирует список и экспортирует вокруг него приятный интерфейс, чтобы упростить общие задачи для клиентов. Как правило, это можно сделать, определив тип узла связанного списка как вложенный класс внутри связанного с клиентом связного списка.

3. У вас может быть программа, которая использует как собственный класс связанного списка, так и коллекцию LinkedList. Одним из вариантов использования этого было бы иметь программу, которая использует LinkedList в основном как реализацию очереди, но использует открытый, настраиваемый связанный список для других задач, где необходимо специально склеивать списки или извлекать отдельные ячейки из список. Например, если вы реализуете кучу Фибоначчи, вы, вероятно, реализуете свой собственный связанный список, даже если вы использовали LinkedList в другом месте программы. Они не являются взаимоисключающими.

4. Я не уверен, что вы подразумеваете под "итератором" в своем последнем вопросе. Если вы хотите распечатать содержимое связанного списка, лучший способ сделать это - создать ссылку на первую ячейку связанного списка, а затем непрерывно перемещать ее вперед до тех пор, пока вы не достигнете конца списка. Завернуть ли вы это в java.util.Iterator объект - решать вам. Вероятно, проще всего создать реальный тип Iterator, чтобы выполнить итерацию, поскольку он позволяет вам взаимодействовать с циклами foreach и другими API, управляющими коллекциями.

Надеюсь, это поможет!

Answer 2

Хотите узнать, как использовать java.util.LinkedList или как создать свой собственный LinkedList? Вам не нужно использовать java.util.LinkedList, чтобы создать (реализовать) свой собственный класс LinkedList.

Я использую Iterator, когда имею дело со стандартным java.util.LinkedList, а не когда я реализую свой собственный класс LinkedList.

Ниже приведена простая реализация класса LinkedList с методом append и print. Мой метод печати выполняет обход через LinkedList для отображения каждого элемента.

public class Solution {
    public static void main(String[] args) {
         LinkedList list = new LinkedList();
         list.append(1);
         list.append(2);
         list.append(3);
         list.append(5);
         list.append(4);
         list.append(8);

         list.print(list.head);
    }
}
class Node {
    Node next;
    int data;
    public Node(int d) {
       data = d;
    }
}
class LinkedList {
    Node head;

    public void append(int val) {
       if (head == null) {
          head = new Node(val);
          return;
       }
       Node current = head;
       while (current.next != null) {
          current = current.next;
       }
       current.next = new Node(val);
    }

    public void print(Node head) {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
    }
}

Ниже приведен пример использования java.util.LinkedList и Iterator.

import java.util.LinkedList;
import java.util.Iterator;

public class Solution {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.add(1);
        list.add(2);
        list.add(4);
        list.add(7);
    }

    public static void print(LinkedList<Integer> list) {
         Iterator it = list.iterator();
         while(it.hasNext()) {
             System.out.print((int)(it.next()) + " ");
         }
    }
}

При использовании java.util.LinkedList вы можете даже просто напечатать LinkedList через System.out.println ()

import java.util.LinkedList;
import java.util.Iterator;

public class Solution {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<Integer>();
        list.add(1);
        list.add(2);
        list.add(4);
        list.add(7);

        System.out.println(list);
    }
}

Answer 3

Для создания связанного списка в Java вам понадобятся два базовых класса: -

1. Класс узла
2. SinglyLinkedList (или DoublyLinkedList) Класс

Вы можете получить базовую реализацию кода Java Linked List этих классов и класса функции main () здесь .