Senarai Pautan Java yang Berterusan dan Tidak Boleh Berubah

Dalam artikel ini kami akan melaksanakan variasi LinkedList yang berterusan dan tidak berubah dalam Java dengan
perkongsian struktur separa untuk keuntungan kecekapan masa dan ruang.

pengenalan

Apakah itu LinkedList

Senarai terpaut ialah struktur data yang terdiri daripada koleksi nod di mana setiap nod mengandungi nilai dan rujukan kepada nod seterusnya dalam jujukan. Operasi seperti menambah elemen ke kepala senarai atau mengalih keluar elemen daripada kepala ialah operasi O(1). Walau bagaimanapun, operasi seperti menambah elemen pada hujung senarai atau mengalih keluar elemen dari hujung ialah operasi O(n) dengan n ialah bilangan elemen dalam senarai.

Mengapa kita memerlukan LinkedList yang tidak boleh diubah

Dalam pengaturcaraan berfungsi, kebolehubahan ialah konsep utama. Ketidakbolehubah bermaksud apabila struktur data dibuat, ia
tidak boleh diubah suai. Sebaliknya, struktur data baharu dibuat dengan pengubahsuaian dan yang asal kekal tidak berubah.

Harta ini membolehkan kami beberapa faedah:

1. Keselamatan benang: Memandangkan struktur data tidak boleh diubah, ia boleh dikongsi merentas berbilang rangkaian tanpa memerlukan penyegerakan.
2. Kebolehramalan: Memandangkan struktur data tidak boleh diubah, kami boleh membuat alasan tentang keadaan struktur data pada bila-bila masa.
3. Buat asal: Memandangkan struktur data tidak boleh diubah, kami sentiasa boleh berbalik kepada keadaan sebelumnya dengan menggunakan versi struktur data sebelumnya.
4. Nyahpepijat: Ketidakbolehubahan menjadikan penyahpepijatan lebih mudah kerana struktur data tidak boleh diubah suai.

Walau bagaimanapun, koleksi dalam Java dan memandangkan fokus artikel ini adalah pada LinkedList, boleh diubah secara lalai. Sebabnya mungkin banyak
bermula daripada tidak difikirkan semula apabila koleksi direka bentuk kepada sebab prestasi yang wujud dalam
struktur data tidak berubah.

Perbezaan antara Koleksi JDK yang Tidak Boleh diubah suai dan LinkedList ini

JDK menyediakan koleksi yang tidak boleh diubah suai yang merupakan pembalut di sekeliling koleksi asal. Mereka menyokong kebolehubahan tetapi mereka tidak berterusan atau menyediakan cara selamat jenis sebenar. Ia adalah pembalut di sekeliling koleksi asal dan ia
buang pengecualian apabila operasi pengubahsuaian dipanggil. Ini tidak sama dengan kebolehubahan di mana struktur data tidak boleh diubah suai sama sekali sambil memastikan bahawa sukar untuk mendapatkan UnsupportedOperationException pada masa jalan.

Berterusan vs Tidak Berubah

Walaupun istilah berterusan dan tidak berubah sering digunakan secara bergantian, ia mempunyai makna yang berbeza. Walaupun kebolehubahan tidak membenarkan pengubahsuaian struktur data, kegigihan membenarkan perkongsian struktur data apabila ia diubah suai. Ini bermakna apabila struktur data diubah suai, aka versi baharu dicipta, bahagian struktur data lama boleh dikongsi dengan yang baharu untuk mencapai keuntungan kecekapan masa dan ruang. Teknik ini dipanggil perkongsian struktur.

Terdapat pelbagai cara untuk mencapai kegigihan dalam struktur data. Struktur data terdiri daripada mudah kepada kompleks seperti menggunakan pokok seimbang seperti pokok AVL atau Merah-Hitam, kepada yang lebih kompleks seperti pokok Jari dan Pokok Seimbang Berasaskan Radix.

Dalam artikel ini, kami akan melaksanakan versi yang lebih ringkas bagi LinkedList yang berterusan dan tidak berubah dengan perkongsian struktur separa. Sebabnya ialah LinkedList ialah struktur data yang mudah dan ia akan membantu kami memahami konsep kebolehubahan dan kegigihan dengan lebih baik dan lazimnya pelaksanaan struktur data yang lebih kompleks sememangnya merupakan tugas yang mencabar.

Perlaksanaan

Di bawah ini kami akan melaksanakan LinkedList tunggal yang berterusan dan tidak boleh diubah dalam Java menggunakan pendekatan langkah demi langkah.

Untuk pelaksanaan yang lengkap dan monad dan utiliti tambahan untuk membantu lawatan pengaturcaraan berfungsi anda ke Java, anda boleh menyemak perpustakaan kecil yang hebat ini FunctionalUtils.

Nama yang akan kami berikan kepada LinkedList kami ialah SeqList dan ia akan menjadi kelas generik.

Pada mulanya, kami perlu memikirkan operasi yang akan kami sokong dalam Senarai kami.

1. Tambahan pada kepala senarai yang akan menjadi operasi O(1).
2. Pengalihan keluar elemen daripada senarai yang akan menjadi operasi O(n) yang paling teruk jika elemen itu terletak di hujung.
3. Tambahan kepada kedudukan sewenang-wenang dalam senarai.
4. Operasi penapisan untuk menapis masuk / menapis elemen yang diberi predikat.
5. Operasi Peta dan FlatMap untuk menukar Senarai kami menjadi Monad untuk komposisi fungsi yang lebih mudah.

Kita boleh menganggap LinkedList sebagai struktur yang terdiri daripada nod di mana setiap nod mengandungi:

1. kepala memegang nilai.
2. ekor memegang selebihnya senarai yang seterusnya merupakan LinkedList yang terdiri daripada kepala dan ekor sehingga penghujung senarai.
3. Penghujung senarai diwakili oleh LinkedList kosong yang bermaksud kedua-dua kepala dan ekor adalah batal.

Pelaksanaan penuh boleh didapati di sini

Memandangkan elemen terakhir senarai ialah LinkedList kosong dan setiap elemen ialah nod dengan kepala dan ekor, kami boleh mewakili LinkedList kami sebagai struktur data rekursif yang terdiri daripada dua kelas:

public record Empty<T>() implements SeqList<T> {
}

public record Cons<T>(T head, SeqList<T> tail) implements SeqList<T> {
}

di mana Cons ialah istilah pengaturcaraan berfungsi bernama Construct bermula sejak bahasa pengaturcaraan Lisp.

Memandangkan perkara di atas, kami boleh melaksanakan antara muka SeqList seperti berikut:

public sealed interface SeqList<T> permits Empty, Cons {
  /**
   * Creates an empty list.
   *
   * @param <T> the type of the elements
   * @return an empty list
   */
  static <T> SeqList<T> empty() {
    return new Empty<>();
  }

  /**
   * Creates a new list with the given elements. The complexity of this method is O(n) where n is
   * the number of elements.
   *
   * @param elements the elements to add
   * @param <T>      the type of the elements
   * @return a new list with the elements added
   */
  @SafeVarargs
  static <T> SeqList<T> of(T... elements) {
    SeqList<T> list = empty();
    for (int i = elements.length - 1; i >= 0; i--) {
      list = list.add(elements[i]);
    }
    return list;
  }

  /**
   * Prepends the element to the list. The complexity of this method is O(1).
   *
   * @param element the element to add
   * @return a new list with the element prepended
   */
  default SeqList<T> add(T element) {
    return new Cons<>(element, this);
  }
}

Jom pecahkan apa yang kami tulis di atas:

1. Kami mencipta antara muka tertutup SeqList yang akan menjadi antara muka untuk LinkedList kami.
2. Kaedah empty() mencipta senarai kosong yang merupakan contoh kelas Empty.
3. Kaedah add() menambah elemen pada senarai. Kerumitan kaedah ini ialah O(1) kerana kami hanya mencipta nod baharu dengan elemen yang diberikan dan senarai semasa. Kaedah ini menggunakan Perkongsian Struktur kerana senarai baharu berkongsi ekor senarai semasa.
4. Kaedah() mencipta senarai baharu dengan elemen yang diberikan. Kerumitan kaedah ini ialah O(n) dengan n ialah bilangan unsur. Seperti yang jelas kita mulakan dari elemen terakhir dan menambahnya ke senarai. Ini kerana kami ingin mengekalkan susunan unsur.

Kami perlu melaksanakan baki operasi kami. Mari mulakan dengan operasi alih keluar:

/**
   * Removes the first occurrence of the element from the list. If the element is not found, the
   * list is returned as is. The complexity of this method is O(n) where n is the number of
   * elements. It uses structural sharing up to the element to remove. If the element is not found
   * the structural sharing is not utilized.
   *
   * @param element the element to remove
   * @return a new list with the element removed
   * @throws StackOverflowError for infinite lists
   */
  default SeqList<T> remove(T element) {
    if (isEmpty()) {
      return this;
    }
    if (head().equals(element)) {
      return tail();
    }
    return new Cons<>(head(), tail().remove(element));
  }

Selain itu, laksanakan kaedah tail() dan beberapa kaedah lain yang berguna dalam subkelas kami:

public record Cons<T>(T head, SeqList<T> tail) implements SeqList<T> {

  @Override
  public boolean isEmpty() {
    return false;
  }

  @Override
  public Optional<T> headOption() {
    return Optional.ofNullable(head);
  }

  @Override
  public Optional<T> last() {
    if (tail.isEmpty()) {
      return Optional.ofNullable(head);
    }
    return tail.last();
  }
}

public record Empty<T>() implements SeqList<T> {

  @Override
  public boolean isEmpty() {
    return true;
  }

  @Override
  public T head() {
    throw new UnsupportedOperationException("head() called on empty list");
  }

  @Override
  public Optional<T> headOption() {
    return Optional.empty();
  }

  @Override
  public SeqList<T> tail() {
    throw new UnsupportedOperationException("tail() called on empty list");
  }

  @Override
  public Optional<T> last() {
    return Optional.empty();
  }
}

Seperti yang kita boleh periksa daripada pelaksanaan kaedah alih keluar, kami menggunakan panggilan rekursif untuk mengalih keluar elemen daripada
senarai itu. Ini adalah corak biasa dalam pengaturcaraan berfungsi di mana kami menggunakan rekursi untuk melintasi senarai dan
keluarkan elemen. Penjagaan harus diambil untuk mengelakkan limpahan tindanan sekiranya senarai tidak terhingga. Penambahbaikan masa depan mungkin menggunakan pengoptimuman rekursi ekor yang tidak disokong di Jawa tetapi boleh dicapai menggunakan trampolining.

Akhir sekali, mari kita laksanakan operasi peta dan peta rata untuk menukar Senarai kami menjadi Monad:

/**
   * Applies a map function to the elements of the list. The complexity of this method is O(n) where
   * n is the number of elements.
   * <b>It does not use structural sharing</b> as it requires advanced data structures to achieve
   * it.
   *
   * @param fn  the map function
   * @param <U> the type of the elements of the new list
   * @return a new list with the elements mapped
   * @throws StackOverflowError for infinite lists
   */
  default <U> SeqList<U> map(Function<? super T, ? extends U> fn) {
    if (isEmpty()) {
      return empty();
    }
    return new Cons<>(fn.apply(head()), tail().map(fn));
  }

  /**
   * Applies a flat map function to the elements of the list. The complexity of this method is O(n)
   * where n is the number of elements.
   * <b>It does not use structural sharing</b> as it requires advanced data structures to achieve
   * it.
   *
   * @param fn  the flat map function
   * @param <U> the type of the elements of the new list
   * @return a new list with the elements flat mapped
   * @throws StackOverflowError for infinite lists
   */
  default <U> SeqList<U> flatMap(Function<? super T, ? extends SeqList<U>> fn) {
    if (isEmpty()) {
      return empty();
    }
    SeqList<U> mappedHead = fn.apply(head());
    SeqList<U> newTail = tail().flatMap(fn);
    return concat(mappedHead, newTail);
  }

  /**
   * Concatenates two lists. The complexity of this method is O(n) where n is the number of
   * elements.
   *
   * @param list1 the first list
   * @param list2 the second list
   * @param <T>   the type of the elements
   * @return a new list with the elements of the two lists concatenated
   * @throws StackOverflowError for infinite lists
   */
  static <T> SeqList<T> concat(SeqList<T> list1, SeqList<T> list2) {
    if (list1.isEmpty()) {
      return list2;
    }
    return new Cons<>(list1.head(), concat(list1.tail(), list2));
  }

Seperti yang dapat kita lihat daripada pelaksanaan kaedah peta dan peta rata, kami menggunakan panggilan rekursif untuk melintasi senarai dan menggunakan fungsi pada setiap elemen. Kaedah flatMap adalah sedikit lebih kompleks kerana ia memerlukan fungsi untuk mengembalikan senarai baharu yang perlu kita gabungkan dengan senarai yang lain. Kedua-dua kaedah tidak menggunakan perkongsian struktur kerana kesukaran yang terkenal dan kepentingan menggunakan struktur data lanjutan. Penambahbaikan pada masa hadapan akan dikaji dalam artikel akan datang.

Contoh penggunaan

Mari lihat beberapa contoh penggunaan SeqList kami.

• Bayangkan kita mempunyai senarai integer dan kita mahu menapis nombor genap dan kemudian mendarabnya dalam kuasa dua tetapi dengan kebolehubahan dan kegigihan.

SeqList<Integer> list = SeqList.of(1, 2, 3, 4, 5, 6);
SeqList<Double> updatedList = list
   .filterOut(number -> number % 2 == 0)
   .map(number -> Math.pow(number, 2));

• Bayangkan kami mempunyai senarai rentetan dan kami ingin menggabungkannya dengan awalan dan akhiran.

SeqList<String> list = SeqList.of("a", "b", "c", "d", "e");
SeqList<String> updatedList = list
   .map(letter -> "prefix" + letter + "suffix");

• Bayangkan kami mempunyai senarai senarai dan kami ingin meratakannya.

SeqList<SeqList<Integer>> list = SeqList.of(SeqList.of(1, 2), SeqList.of(3, 4), SeqList.of(5, 6));
SeqList<Integer> updatedList = list
   .flatMap(seqList -> seqList);

• Contoh lain ialah padanan corak menggunakan ungkapan suis JDK 21 dan mengambil kesempatan daripada semakan pengkompil.

SeqList<Integer> list = SeqList.of(1, 2, 3, 4, 5, 6);
switch (list) {
  case Empty() -> {
    // do something
  }
  case Cons<Integer> cons -> {
    //do something else
  }
}

Keburukan

1. Prestasi: Jika senarai digunakan terutamanya untuk menambah elemen untuk mendapatkan elemen daripada ketua senarai maka prestasinya adalah baik. Dalam semua kes lain, O(n) diperlukan sekurang-kurangnya dengan pelaksanaan ini.
2. Kerumitan: Pelaksanaan LinkedList yang berterusan dan tidak berubah adalah lebih kompleks daripada rakan sejawatnya yang boleh berubah.
3. Memori: Pelaksanaan LinkedList yang berterusan dan tidak berubah memerlukan lebih banyak memori daripada rakan sejawatannya yang boleh berubah disebabkan oleh penciptaan senarai baharu untuk setiap operasi. Dengan perkongsian struktur ini dapat dikurangkan tetapi tidak dihapuskan.

Kesimpulan

Dalam artikel ini, kami melaksanakan LinkedList yang berterusan dan tidak berubah dalam Java dengan perkongsian struktur separa. Kami menunjukkan faedah kebolehubahan dan kegigihan dan cara kami boleh mencapainya di Jawa. Kami juga menunjukkan cara kami boleh menukar LinkedList kami menjadi Monad untuk komposisi fungsi yang lebih mudah. Kami membincangkan kebaikan dan keburukan struktur data yang berterusan dan tidak berubah serta cara ia boleh digunakan dalam amalan.

Atas ialah kandungan terperinci Senarai Pautan Java yang Berterusan dan Tidak Boleh Berubah. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!