Реалізація інтерфейсу List

— Якщо ти думаєш, що на інтерфейсі List все закінчилося, то помиляєшся, все тільки починається. Давай я тобі розповім про колекції LinkedList і ArrayList.

Почну з колекції ArrayList.

Ось як ця колекція виглядає на схемі успадкування:

Зеленим відзначені інтерфейси.

Фіолетовим – абстрактні класи.

Червоним – звичайні класи.

Суцільна лінія – успадкування, пунктирна – реалізація інтерфейсу.

Це найпростіша колекція. Всередині ArrayList зберігає елементи в простому масиві.

Основна перевага такої колекції над масивом – це розширюваність – збільшення довжини за потреби.

Якщо в цьому масиві закінчується місце, створюється другий масив побільше, куди копіюються всі елементи з першого. Потім другий масив займає місце першого, а перший викидається (буде знищений збирачем сміття).

— А наскільки збільшується масив?

— Довжина нового масиву розраховується так (3*n)/2+1 де n – це довжина старого масиву. Тобто. якщо старий масив був довжиною 100 елементів, новий буде 300/2+1 = 151.

При додаванні елемента в середину ArrayList, всі елементи праворуч від нього копіюються на 1 позицію вправо, а потім в порожню комірку додається новий елемент.

При видаленні елемента з середини всі елементи праворуч від нього копіюються на 1 позицію вліво.

— Ти кажеш, що ArrayList сам подовжується при додаванні елементів до нього. А при видаленні він сам коротшає?

— Ні, сам внутрішній масив у ArrayList ніколи не коротшає, але можна змусити ArrayList зменшити свій внутрішній масив до мінімального рівня, якщо викликати методtrimToSize().

Ну, і звичайно, розповім про LinkedList.

Ось як виглядає його схема успадкування:

Зеленим відзначені інтерфейси.

Фіолетовим – абстрактні класи.

Червоним – звичайні класи.

Суцільна лінія – успадкування, пунктирна – реалізація інтерфейсу.

Як ти вже знаєш, LinkedList зберігає елементи у вигляді зв'язкового списку.

— Я постійно чую про це, але не могла б ти розповісти, що це таке?

— Звичайно. Все просто.

Зв'язковий список складається з однакових елементів, які а)зберігають дані,б)зберігають посилання на наступний і попередній елементи.

От так виглядав би клас такого елемента для зберігання рядків:

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

А якщо використовувати generics для типу даних, то буде щось такого типу:

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

— Ясно.

— Давай, для кращого розуміння, напишемо код, де додамо до двозв'язкового списку 10 елементів:

public static void main(String[] args)
{
 LinkedListElement<Integer> tail; // хвіст (останній елемент) списку

 for(int i=0;i<10;i++)
 {
 LinkedListElement<Integer> element = новий LinkedListElement<Integer>< /span>();
  element.data = i;

  if (tail == null) //якщо в хвості немає елементів, зробити наш елемент останнім
  {
   tail = element;
  }
  else //якщо хвіст є, додати елемент
  {
   tail.next = element; //додаємо хвосту посилання на наступний елемент
 element.previous = tail; //додаємо новому елементу посилання на хвіст
   tail = element; //оголошуємо новий елемент хвостом.
  }
 }
}

Допустимо у нас у списку 10 елементів, ось як вставити елемент у середину:

Яскраво-червоним виділені посилання, які змінилися – вони тепер вказують на новий елемент.

Яскраво-фіолетовим Виділені нові посилання – посилання нового елемента на його сусідів.

А тепер – кодом:

//тут міститься елемент – голова списку
LinkedListElement<Integer> head = …

//отримуємо 4-й елемент (нумерація з нуля)
LinkedListElement<Integer> element4 = head.next.next.next.next;
//отримуємо 5-й елемент
LinkedListElement<Integer> element5 = element4. next;

//Створюємо новий елемент, який вставлятимемо
LinkedListElement<Integer> newElement = new LinkedListElement<Integer>< /span>();
newElement.data = -18;

//обмінюємося посиланнями з елементом зліва
newElement.previous = element4;
element4.next = newElement;

//обмінюємося посиланнями з елементом праворуч
newElement.next = element5;
element5.previous = newElement;

— Дякую, Еллі, справді дізнався про списки багато нового.