Triển khai giao diện Danh sách

"Nếu bạn nghĩ rằng chúng ta đã hoàn thành tất cả với giao diện Danh sách, thì bạn đã nhầm. Chúng ta chỉ mới bắt đầu. Để tôi nói cho bạn biết về các bộ sưu tập LinkedList và ArrayList ."

"Tôi sẽ bắt đầu với bộ sưu tập ArrayList."

"Đây là sơ đồ kế thừa của bộ sưu tập này trông như thế nào:"

"Giao diện có màu xanh lá cây."

"Các lớp trừu tượng có màu tím."

"Các lớp bình thường có màu đỏ."

"Các đường liền nét biểu thị tính kế thừa và các đường đứt nét biểu thị các triển khai giao diện."

"Đây là bộ sưu tập đơn giản nhất. Bên trong ArrayList , các phần tử được lưu trữ trong một mảng đơn giản."

"Ưu điểm chính của bộ sưu tập này so với mảng là khả năng mở rộng, tức là khả năng tăng chiều dài khi cần."

"Nếu mảng hết dung lượng, thì mảng thứ hai lớn hơn sẽ được tạo và tất cả các phần tử từ mảng đầu tiên được sao chép vào mảng đó. Sau đó, mảng thứ hai sẽ thay thế mảng thứ nhất và mảng thứ nhất bị loại bỏ (nó sẽ bị hủy bởi bộ thu gom rác)."

"Mảng lớn hơn bao nhiêu?"

"Độ dài của mảng mới được tính là (3*n)/2+1, trong đó n là độ dài của mảng cũ. Nói cách khác, nếu mảng cũ dài 100 phần tử thì mảng mới sẽ là 300/2+1 = 151."

"Khi thêm một phần tử vào giữa ArrayList, tất cả các phần tử ở bên phải nơi phần tử mới sẽ được chèn sẽ được sao chép 1 vị trí sang bên phải, sau đó phần tử mới được thêm vào ô trống."

"Khi xóa một phần tử ra khỏi giữa thì tất cả các phần tử bên phải phần tử đó đều được sao chép 1 vị trí sang bên trái."

"Có phải bạn đang nói rằng ArrayList tự dài hơn khi bạn thêm các phần tử vào nó và nó sẽ tự ngắn hơn khi bạn xóa các phần tử?"

"Không, mảng bên trong ArrayList không bao giờ tự nó ngắn lại; tuy nhiên, bạn có thể buộc ArrayList thu nhỏ mảng bên trong của nó về kích thước nhỏ nhất có thể bằng cách gọi phương thức trimToSize() . "

"Và, tất nhiên, tôi sẽ nói với bạn về LinkedList."

"Đây là sơ đồ kế thừa của nó trông như thế nào:"

"Giao diện có màu xanh lá cây."

"Các lớp trừu tượng có màu tím."

"Các lớp bình thường có màu đỏ."

"Các đường liền nét biểu thị tính kế thừa và các đường đứt nét biểu thị các triển khai giao diện."

"Như bạn đã biết, LinkedList lưu trữ các phần tử dưới dạng danh sách được liên kết."

"Tôi nghe điều đó mọi lúc, nhưng bạn có thể cho tôi biết nó là gì không?"

"Chắc chắn. "Nó đơn giản."

"Danh sách được liên kết bao gồm các phần tử a) lưu trữ dữ liệu và b) lưu trữ các tham chiếu đến các phần tử tiếp theo và trước đó."

"Đây là cách lớp cho một phần tử như vậy sẽ trông như thế nào nếu nó được lưu trữ Chuỗi:"

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

"Và nếu chúng ta sử dụng một khai báo kiểu chung, thì nó sẽ giống như thế này:"

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

"Có ý nghĩa."

"Để hiểu rõ hơn, hãy viết mã trong đó chúng tôi thêm 10 phần tử vào danh sách liên kết kép:"

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

"Hãy tưởng tượng rằng chúng ta có 10 phần tử trong danh sách. Đây là cách chèn một phần tử vào giữa:"

"Các liên kết đã thay đổi được đánh dấu màu đỏ tươi . Bây giờ chúng trỏ đến phần tử mới."

"Các liên kết mới được đánh dấu bằng màu tím sáng . Chúng là các liên kết của phần tử mới với các liên kết lân cận của nó."

"Và bây giờ là mã:"

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

"Cảm ơn, Ellie. Tôi chắc chắn đã học được rất nhiều điều mới về danh sách."