Реализации на интерфейса List

„Ако си мислите, че сме приключor с интерфейса List, тогава грешите. Ние едва започваме. Нека ви разкажа за колекциите LinkedList и ArrayList . “

„Ще започна с колекцията ArrayList.“

„Ето How изглежда диаграмата на наследяване на тази колекция:“

„Интерфейсите са зелени.“

„Абстрактните класове са лилави.“

"Обикновените класове са червени."

„Плътните линии представляват наследяване, а пунктираните линии представляват реализации на интерфейса.“

"Това е най-простата колекция. Вътре в ArrayList елементите се съхраняват в прост масив."

„Основното предимство на тази колекция пред масива е нейната способност да се разширява, т.е. способността й да увеличава дължината си според нуждите.“

„Ако пространството в масива свърши, тогава се създава втори по-голям масив и всички елементи от първия масив се копират в него. Тогава вторият масив заема мястото на първия, а първият се изхвърля (той ще бъде унищожен от боклукчия)."

„Колко по-голям става масивът?“

„Дължината на новия масив се изчислява като (3*n)/2+1, където n е дължината на стария масив. С други думи, ако старият масив е бил дълъг 100 елемента, тогава новият ще бъде 300/2+1 = 151."

„Когато добавяте елемент в средата на ArrayList, всички елементи вдясно от мястото, където ще бъде вмъкнат новият елемент, се копират 1 позиция вдясно и след това новият елемент се добавя към празната клетка.“

„Когато премахвате елемент от средата, всички елементи вдясно от този елемент се копират 1 позиция вляво.“

„Искате да кажете, че ArrayList се удължава, когато добавяте елементи към него, и че се скъсява, когато премахвате елементи?“

„Не, масивът вътре в ArrayList никога не се прави сам по-къс; можете обаче да принудите ArrayList да свие вътрешния си масив до възможно най-малкия размер, като извикате метода trimToSize () . “

„И, разбира се, ще ви разкажа за LinkedList.“

„Ето How изглежда неговата диаграма на наследяване:“

„Интерфейсите са зелени.“

„Абстрактните класове са лилави.“

"Обикновените класове са червени."

„Плътните линии представляват наследяване, а пунктираните линии представляват реализации на интерфейса.“

„Както вече знаете, LinkedList съхранява елементи като свързан списък.“

„Чувам това през цялото време, но бихте ли ми казали Howво е?“

"Разбира се. "Просто е."

„Свързаният списък се състои от елементи , които а) съхраняват данни и б) съхраняват препратки към следващия и предишния елемент.“

"Ето How би изглеждал класът за такъв елемент , ако съхранява низове:"

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

„И ако използваме декларация за общ тип, тогава ще изглежда нещо подобно:“

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

"Има смисъл."

„За да го разберем по-добре, нека напишем code, където добавяме 10 елемента към двойно свързан списък:“

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

„Представете си, че имаме 10 елемента в списъка. Ето How да вмъкнете елемент в средата:“

„Връзките, които са променени, са подчертани в ярко червено . Сега те сочат към новия елемент.“

"Новите връзки са подчертани в ярко лилаво . Те са връзките на новия елемент към неговите съседи."

„А сега като code:“

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

„Благодаря ти, Ели. Определено научих много нови неща за списъците.“