配列リニアテーブルArayListの内部実装
リニアテーブルは、データを順番に記憶するのが一般的なデータ構造です.ほとんどの線形表の典型的な動作は、
1,リニアテーブルを初期化する
2,判断表が空かどうか
3,線形表の長さを求めます.
4,リニアテーブルのi番目の要素を読みだします.
5、条件を満たすデータ要素を検索します.
6,リニアテーブルのi番目の位置に新しいデータ要素を挿入します.
7,リニアテーブルのi番目のデータ要素を削除します.
8,テーブルを空にする
9,i番目の要素の前駆または後続を検索する.
10,1つ以上のデータ項目で増分または減少してデータ要素を並べ替える
配列線形表は、シーケンス記憶構造であり、最も簡単で、最も一般的なデータ構造である.メモリ内に連続的なメモリ空間を開き、連続的なメモリユニットでデータ要素を一度に保存する.順序記憶の特徴は、論理的に隣接するデータ要素であり、それらの物理的位置も接続されている.
利点は、直感的で直感的で、ランダムアクセス要素が非常に実現しやすく、テーブル内の各要素の保存場所が定位式化によって容易に見つけられますので、i番目の結点を指定するのに便利です.
欠点は、結点の挿入と削除が難しく、アルゴリズムの効率が高くないことです.結点は順番に保存されていますので、結点を挿入または削除する場合は、その結点以降のすべての要素を順に後ろに移動したり、順番に前に移動したりしなければなりません.
JDK 1.5以降、ArayListは汎型の導入を開始した.
インターフェースMyList＜E＞は、線形表を操作する基本的な方法があり、MyAbstractList＜E＞抽象類はMyList＜E＞インターフェースを実現しましたが、この抽象類はインターフェースの一部の方法を実現しただけで、MyAbstractList＜E＞は拡張抽象類のMyAbstractList＜E＞抽象類を継承します.
インターフェースMyList
1,リニアテーブルを初期化する
2,判断表が空かどうか
3,線形表の長さを求めます.
4,リニアテーブルのi番目の要素を読みだします.
5、条件を満たすデータ要素を検索します.
6,リニアテーブルのi番目の位置に新しいデータ要素を挿入します.
7,リニアテーブルのi番目のデータ要素を削除します.
8,テーブルを空にする
9,i番目の要素の前駆または後続を検索する.
10,1つ以上のデータ項目で増分または減少してデータ要素を並べ替える
配列線形表は、シーケンス記憶構造であり、最も簡単で、最も一般的なデータ構造である.メモリ内に連続的なメモリ空間を開き、連続的なメモリユニットでデータ要素を一度に保存する.順序記憶の特徴は、論理的に隣接するデータ要素であり、それらの物理的位置も接続されている.
利点は、直感的で直感的で、ランダムアクセス要素が非常に実現しやすく、テーブル内の各要素の保存場所が定位式化によって容易に見つけられますので、i番目の結点を指定するのに便利です.
欠点は、結点の挿入と削除が難しく、アルゴリズムの効率が高くないことです.結点は順番に保存されていますので、結点を挿入または削除する場合は、その結点以降のすべての要素を順に後ろに移動したり、順番に前に移動したりしなければなりません.
JDK 1.5以降、ArayListは汎型の導入を開始した.
インターフェースMyList＜E＞は、線形表を操作する基本的な方法があり、MyAbstractList＜E＞抽象類はMyList＜E＞インターフェースを実現しましたが、この抽象類はインターフェースの一部の方法を実現しただけで、MyAbstractList＜E＞は拡張抽象類のMyAbstractList＜E＞抽象類を継承します.
インターフェースMyList
public interface MyList<E> {
//
public void add(E e);
// index
public void add(int index,E e);
// list
public void clear();
//
public boolean remove(E e);
// index
public E remove(int index);
//index e
public Object set(int index,E e);
// e
public boolean contains(E e);
// index
public E get(int index);
// e index
public int indexOf(E e);
// e index
public int lastIndeOf(E e);
//
public boolean isEmpty();
//
public int size();
}
public abstract class MyAbstractList<E> implements MyList<E> {// MyList
protected int size=0;
protected MyAbstractList(){
}
protected MyAbstractList(E[] objects){
for(int i=1;i<objects.length;i++)
add(objects[i]);
}
@Override
public void add(E e){
add(size,e);
}
@Override
public void add(int index,E e){
}
@Override
public boolean isEmpty(){
return size==0;
}
@Override
public int size(){
return size;
}
@Override
public boolean remove(E e){
if(indexOf(e)>=0){
remove(indexOf(e));
return true;
}
else return false;
}
@Override
public E remove(int index){
return null;
}
@Override
public void clear() {
// TODO Auto-generated method stub
}
@Override
public Object set(int index, E e) {
// TODO Auto-generated method stub
return null;
}
@Override
public boolean contains(E e) {
// TODO Auto-generated method stub
return false;
}
@Override
public E get(int index) {
// TODO Auto-generated method stub
return null;
}
@Override
public int indexOf(E e) {
// TODO Auto-generated method stub
return 0;
}
@Override
public int lastIndeOf(E e) {
// TODO Auto-generated method stub
return 0;
}
}
public class MyArrayList<E> extends MyAbstractList<E> {
public static final int INITIAL_CAPACITY=16;
private E[] data=(E[])new Object[INITIAL_CAPACITY];
public MyArrayList(){
}
public MyArrayList(E[] objects){
for(int i=0;i<objects.length;i++)
add(objects[i]);
}
public void add(int index,E e){
ensureCapacity();
for(int i=size-1;i>=index;i--)
data[i+1]=data[i];
data[index]=e;
size++;
}
private void ensureCapacity() {
if(size>=data.length){
E[] newData=(E[])(new Object[size*2+1]);
System.arraycopy(data, 0, newData, 0, size);
data=newData;
}
}
public void clear(){
data=(E[])new Object[INITIAL_CAPACITY];
size=0;
}
public boolean contains(E e){
for(int i=0;i<size;i++){
if(e.equals(data[i])) return true;
}
return false;
}
public E get(int index){
return data[index];
}
public int indexOf(E e){
for(int i=0;i<size;i++)
if(e.equals(data[i])) return i;
return -1;
}
public int lastIndexOf(E e){
for(int i=size-1;i>=0;i--)
if(e.equals(data[i])) return i;
return -1;
}
public E remove(int index){
E e=data[index];
for(int j=index;j<size-1;j++)
data[j]=data[j+1];
data[size-1]=null;
size--;
return e;
}
public E set(int index,E e){
E old=data[index];
data[index]=e;
return old;
}
public String toString(){
StringBuilder result=new StringBuilder("[");
for(int i=0;i<size;i++){
result.append(data[i]);
if(i<size-1) result.append(",");
}
return result.toString()+"]";
}
public void trimToSize(){
if(size!=data.length){
E[] newData=(E[])new Object[size];
System.arraycopy(data, 0, newData, 0, size);
data=newData;
}
}
}