Pelaksanaan antara muka Senarai

"Jika anda fikir kami sudah selesai dengan antara muka Senarai, maka anda silap. Kami baru bermula. Biar saya beritahu anda tentang koleksi LinkedList dan ArrayList . "

"Saya akan mulakan dengan koleksi ArrayList."

"Berikut ialah rupa rajah warisan koleksi ini:"

"Antara muka berwarna hijau."

"Kelas abstrak berwarna ungu."

"Kelas biasa merah."

"Garis pepejal mewakili warisan, dan garis putus-putus mewakili pelaksanaan antara muka."

"Ini ialah koleksi paling ringkas. Di dalam ArrayList , elemen disimpan dalam tatasusunan ringkas."

"Kelebihan utama koleksi ini berbanding tatasusunan ialah keupayaannya untuk berkembang, iaitu keupayaannya untuk menambah panjangnya mengikut keperluan."

"Jika tatasusunan kehabisan ruang, maka tatasusunan kedua yang lebih besar dicipta dan semua elemen daripada tatasusunan pertama disalin kepadanya. Kemudian tatasusunan kedua mengambil tempat yang pertama, dan yang pertama dibuang (ia akan dimusnahkan oleh pemungut sampah).

"Berapa besarkah array dapat?"

"Panjang tatasusunan baharu dikira sebagai (3*n)/2+1, dengan n ialah panjang tatasusunan lama. Dengan kata lain, jika tatasusunan lama ialah 100 elemen panjang, maka tatasusunan baharu ialah 300/2+1 = 151."

"Apabila menambahkan elemen ke tengah ArrayList, semua elemen di sebelah kanan tempat elemen baharu akan disisipkan akan disalin 1 kedudukan ke kanan, dan kemudian elemen baharu ditambahkan pada sel kosong."

"Apabila mengalih keluar elemen dari tengah, semua elemen di sebelah kanan elemen itu disalin 1 kedudukan ke kiri."

"Adakah anda mengatakan bahawa ArrayList menjadikannya lebih panjang apabila anda menambah elemen padanya dan ia menjadikannya lebih pendek apabila anda mengalih keluar elemen?"

"Tidak, tatasusunan di dalam ArrayList tidak pernah menjadikannya lebih pendek dengan sendirinya; namun, anda boleh memaksa ArrayList untuk mengecilkan tatasusunan dalamannya kepada saiz terkecil yang mungkin dengan memanggil kaedah trimToSize () . "

"Dan, sudah tentu, saya akan memberitahu anda tentang LinkedList."

"Berikut ialah rupa rajah warisannya:"

"Antara muka berwarna hijau."

"Kelas abstrak berwarna ungu."

"Kelas biasa merah."

"Garis pepejal mewakili warisan, dan garis putus-putus mewakili pelaksanaan antara muka."

"Seperti yang anda sedia maklum, LinkedList menyimpan elemen sebagai senarai terpaut."

"Saya mendengarnya sepanjang masa, tetapi bolehkah anda memberitahu saya apa itu?"

"Sudah tentu. "Ia mudah."

"Senarai terpaut terdiri daripada elemen yang a) menyimpan data dan b) menyimpan rujukan kepada elemen seterusnya dan sebelumnya."

"Beginilah rupa kelas untuk elemen sedemikian jika ia menyimpan Strings:"

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

"Dan jika kita menggunakan pengisytiharan jenis generik, maka ia akan kelihatan seperti ini:"

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

"Masuk akal."

"Untuk memahaminya dengan lebih baik, mari tulis kod di mana kita menambah 10 elemen pada senarai berganda:"

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
  }
 }
}

"Bayangkan kita mempunyai 10 elemen dalam senarai. Begini cara untuk memasukkan elemen ke tengah:"

"Pautan yang telah berubah diserlahkan dengan warna merah terang . Ia kini menghala ke elemen baharu."

"Pautan baharu diserlahkan dengan warna ungu terang . Ia adalah pautan elemen baharu kepada jirannya."

"Dan sekarang sebagai kod:"

// 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;

"Terima kasih, Ellie. Saya pasti belajar banyak perkara baru tentang senarai."