List インターフェースの実装

「List インターフェイスの使用がすべて完了したと思ったら、それは間違いです。まだ始まったばかりです。LinkedList コレクションと ArrayList コレクションについて説明しましょう。」

「ArrayList コレクションから始めます。」

「このコレクションの継承図は次のようになります。」

「インターフェースは緑色です。」

「抽象クラスは紫色です。」

「普通のクラスは赤です。」

「実線は継承を表し、破線はインターフェイスの実装を表します。」

「これは最も単純なコレクションです。ArrayList内では、要素は単純な配列に格納されます。」

「配列に対するこのコレクションの主な利点は、拡張機能、つまり、必要に応じて長さを増やすことができることです。」

「配列のスペースが不足すると、2 番目のより大きな配列が作成され、最初の配列のすべての要素がそこにコピーされます。その後、2 番目の配列が最初の配列の代わりになり、最初の配列は破棄されます (ガベージ コレクターによって破棄されます)。

「配列はどのくらい大きくなりますか?」

新しい配列の長さは (3*n)/2+1 として計算されます。ここで、n は古い配列の長さです。つまり、古い配列の長さが 100 要素である場合、新しい配列は 300/2+1 になります。 = 151。」

「ArrayList の中央に要素を追加する場合、新しい要素が挿入される場所の右側にあるすべての要素が 1 つ右にコピーされ、新しい要素が空のセルに追加されます。」

「要素を中央から削除すると、その要素の右側にあるすべての要素が 1 つ左の位置にコピーされます。」

「ArrayList に要素を追加すると ArrayList 自体が長くなり、要素を削除すると短くなると言いたいのですか?」

「いいえ、ArrayList 内の配列がそれ自体で短くなることはありません。ただし、 trimToSize () メソッドを呼び出すことで、ArrayList の内部配列を強制的に最小サイズに縮小することができます。」

「そしてもちろん、LinkedList についてもお話します。」

「その継承図は次のようになります。」

「インターフェースは緑色です。」

「抽象クラスは紫色です。」

「普通のクラスは赤です。」

「実線は継承を表し、破線はインターフェイスの実装を表します。」

「すでにご存知のとおり、LinkedList は要素をリンクされたリストとして保存します。」

「よく聞くんですが、どういうことなのか教えていただけますか？」

「そうですね。簡単です。」

「リンク リストは、 a) データを格納する要素、b) 次および前の要素への参照を格納する要素で構成されます。」

「文字列を格納した場合、そのような要素のクラスは次のようになります。」

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

「ジェネリック型宣言を使用すると、次のようになります。」

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

「理にかなっていますね。」

「よりよく理解するために、二重リンクリストに 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 個の要素があると想像してください。要素を中央に挿入する方法は次のとおりです。」

「変更されたリンクは明るい赤で強調表示されます。これらは新しい要素をポイントするようになりました。」

「新しいリンクは明るい紫色で強調表示されます。それらは新しい要素の隣接要素へのリンクです。」

「そして今度はコードとして:」

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

「ありがとう、エリー。リストについてたくさんの新しいことを学びました。」