Implementasi antarmuka List

"Yen sampeyan mikir yen kita kabeh wis rampung karo antarmuka List, sampeyan salah. Kita lagi miwiti. Ayo kula pitutur marang kowe bab koleksi LinkedList lan ArrayList . "

"Aku bakal miwiti karo koleksi ArrayList."

"Mangkene carane diagram warisan koleksi iki katon:"

"Antarmuka sing ijo."

"Kelas abstrak warna ungu."

"Kelas biasa iku abang."

"Garis padat makili warisan, lan garis putus-putus makili implementasi antarmuka."

"Iki koleksi paling prasaja. Nang ArrayList , unsur disimpen ing array prasaja."

"Kauntungan utami koleksi iki saka array yaiku kemampuan kanggo nggedhekake, yaiku kemampuan kanggo nambah dawa yen perlu."

"Yen array kehabisan spasi, banjur array luwih gedhe kaloro digawe lan kabeh unsur saka array pisanan disalin menyang. Banjur array kapindho njupuk Panggonan pisanan, lan pisanan dibuwang (bakal dirusak dening tukang sampah).

"Pinten luwih gedhe array entuk?"

"Dawa array anyar diitung minangka (3 * n) / 2 + 1, ing ngendi n yaiku dawa array lawas. Ing tembung liya, yen array lawas dawane 100 unsur, banjur sing anyar bakal dadi 300/2+1 = 151."

"Nalika nambahake unsur ing tengah ArrayList, kabeh unsur ing sisih tengen ngendi unsur anyar bakal dilebokake disalin 1 posisi ing sisih tengen, banjur unsur anyar ditambahake menyang sel kosong."

"Nalika ngilangi unsur saka tengah, kabeh unsur ing sisih tengen unsur kasebut disalin 1 posisi ing sisih kiwa."

"Apa sampeyan ngomong yen ArrayList nggawe luwih suwe nalika sampeyan nambahake unsur, lan nggawe luwih cendhek nalika mbusak unsur?"

"Ora, array ing jero ArrayList ora bakal nggawe dhewe luwih cendhek, nanging sampeyan bisa meksa ArrayList kanggo nyilikake array internal menyang ukuran paling cilik kanthi nelpon metode trimToSize ( ) .

"Lan, mesthi, aku bakal ngandhani sampeyan babagan LinkedList."

"Iki kaya diagram warisane:"

"Antarmuka sing ijo."

"Kelas abstrak warna ungu."

"Kelas biasa iku abang."

"Garis padat makili warisan, lan garis putus-putus makili implementasi antarmuka."

"Minangka sampeyan wis ngerti, LinkedList nyimpen unsur minangka dhaptar sing disambung."

"Aku krungu kabeh, nanging bisa ngomong apa iku?"

"Inggih. "Iku prasaja."

"Dhaptar sing disambung kalebu unsur sing a) nyimpen data lan b) nyimpen referensi menyang unsur sabanjure lan sadurunge."

"Iki carane kelas kanggo unsur kasebut bakal katon yen disimpen Strings:"

class LinkedListElement
{
String data;
LinkedListElement next;
LinkedListElement previous;
}

"Lan yen kita nggunakake deklarasi jinis umum, mula bakal katon kaya iki:"

class LinkedListElement<T>
{
 T data;
 LinkedListElement<T> next;
 LinkedListElement<T> previous;
}

"Make akal."

"Kanggo luwih ngerti, ayo nulis kode ing ngendi kita nambahake 10 unsur menyang dhaptar sing digandhengake kaping pindho:"

public static void main(String[] args)
{
 LinkedListElement<Integer> tail; // The tail (very last element) of the list

 for(int i = 0; i < 10; i++)
 {
  LinkedListElement<Integer> element = new LinkedListElement<Integer>();
  element.data = i;

  if (tail == null) // If the tail doesn't exist, then make our element the last element
  {
   tail = element;
  }
  else // if there is a tail, add the element
  {
   tail.next = element; // Set the next field on the tail element
   element.previous = tail; // Add a reference to the tail to the new element
   tail = element; // Make the new element the tail
  }
 }
}

"Mbayangno yen kita duwe 10 unsur ing dhaptar. Mangkene carane nglebokake unsur ing tengah: "

"Tautan sing wis diganti disorot abang padhang . Saiki nuding unsur anyar."

"Link anyar disorot ungu padhang . Iku pranala unsur anyar kanggo tetanggan."

"Lan saiki minangka kode:"

// This field stores the element that is the head of the list
LinkedListElement<Integer> head = …

// Get the 4th element (counting from zero)
LinkedListElement<Integer> element4 = head.next.next.next.next;
// Get the 5th element
LinkedListElement<Integer> element5 = element4.next;

// Create the new element that we will insert
LinkedListElement<Integer> newElement = new LinkedListElement<Integer>();
newElement.data = -18;

// Replace the references in the element on the left
newElement.previous = element4;
element4.next = newElement;

// Replace the references in the element on the right
newElement.next = element5;
element5.previous = newElement;

"Matur nuwun, Ellie. Aku mesthi sinau akeh perkara anyar babagan dhaptar."