Implementasi antarmuka Daftar

"Jika Anda berpikir bahwa kita sudah selesai dengan antarmuka List, maka Anda salah. Kita baru saja memulai. Izinkan saya memberi tahu Anda tentang koleksi LinkedList dan ArrayList . "

"Saya akan mulai dengan koleksi ArrayList."

"Beginilah tampilan diagram pewarisan koleksi ini:"

"Antarmuka berwarna hijau."

"Kelas abstrak berwarna ungu."

"Kelas biasa berwarna merah."

"Garis padat mewakili warisan, dan garis putus-putus mewakili implementasi antarmuka."

"Ini adalah koleksi paling sederhana. Di dalam ArrayList , elemen disimpan dalam larik sederhana."

"Keunggulan utama koleksi ini dibandingkan larik adalah kemampuannya untuk mengembang, yaitu kemampuannya untuk menambah panjangnya sesuai kebutuhan."

"Jika larik kehabisan ruang, maka larik kedua yang lebih besar dibuat dan semua elemen dari larik pertama disalin ke dalamnya. Kemudian larik kedua menggantikan yang pertama, dan yang pertama dibuang (itu akan menjadi dihancurkan oleh pemulung).

"Seberapa besar susunannya?"

"Panjang array baru dihitung sebagai (3*n)/2+1, di mana n adalah panjang array lama. Dengan kata lain, jika array lama panjangnya 100 elemen, maka yang baru akan menjadi 300/2+1 = 151."

"Saat menambahkan elemen ke tengah ArrayList, semua elemen di sebelah kanan tempat elemen baru akan dimasukkan disalin 1 posisi ke kanan, lalu elemen baru ditambahkan ke sel kosong."

"Saat menghapus elemen dari tengah, semua elemen di sebelah kanan elemen tersebut disalin 1 posisi ke kiri."

"Apakah Anda mengatakan bahwa ArrayList membuat dirinya lebih panjang ketika Anda menambahkan elemen ke dalamnya, dan itu membuat dirinya lebih pendek ketika Anda menghapus elemen?"

"Tidak, larik di dalam ArrayList tidak pernah membuat dirinya lebih pendek dengan sendirinya; namun, Anda dapat memaksa ArrayList untuk mengecilkan larik internalnya ke ukuran sekecil mungkin dengan memanggil metode trimToSize () . "

"Dan, tentu saja, saya akan memberi tahu Anda tentang LinkedList."

"Seperti inilah diagram warisannya:"

"Antarmuka berwarna hijau."

"Kelas abstrak berwarna ungu."

"Kelas biasa berwarna merah."

"Garis padat mewakili warisan, dan garis putus-putus mewakili implementasi antarmuka."

"Seperti yang sudah Anda ketahui, LinkedList menyimpan elemen sebagai daftar tertaut."

"Aku mendengarnya sepanjang waktu, tapi bisakah kau memberitahuku apa itu?"

"Tentu. Sederhana saja."

"Daftar tertaut terdiri dari elemen yang a) menyimpan data dan b) menyimpan referensi ke elemen berikutnya dan sebelumnya."

"Beginilah tampilan kelas untuk elemen seperti itu jika menyimpan Strings:"

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

"Dan jika kita menggunakan deklarasi tipe generik, maka akan terlihat seperti ini:"

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

"Masuk akal."

"Untuk memahaminya dengan lebih baik, mari kita menulis kode di mana kita menambahkan 10 elemen ke daftar yang tertaut ganda:"

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 memiliki 10 elemen dalam daftar. Berikut cara memasukkan elemen ke tengah:"

"Tautan yang telah berubah disorot dengan warna merah terang . Tautan tersebut sekarang mengarah ke elemen baru."

"Tautan baru disorot dengan warna ungu cerah . Itu adalah tautan elemen baru ke tetangganya."

"Dan sekarang sebagai 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;

"Terima kasih, Ellie. Aku benar-benar belajar banyak hal baru tentang daftar."