データ構造--ArayListの実現原理ソース
1)テーマ:ArayListの実現原理ソース
2)考え方:順序表ArayListは、配列で表し、一連の連続アドレス空間.その実施方法は、
リニアテーブルArayListを初期化する 、線形テーブルの末尾に要素add(E e) を追加する.は、udateを更新し、第index各データをudate(E e,int index) に置換する.指定された位置の要素removeToIndexを削除する .スケーリングに従って要素値get(int index) を返す.は、テーブル容量が所定の大きさを超えているかどうかを判断し、自動拡張容量ensureCapacity() を超えると、自動的に拡張される.は、順序表の実際の表長sizeに戻る() は、テーブル容量length() に戻る. 判断表が空isEmptyかどうか() 指定サイズのランダムシーケンステーブルinitRamdomListを初期化する 指定サイズの非降順順順順テーブルinitNotDecsを初期化する 指定サイズの昇順順テーブルinitacsを初期化する 指定サイズの降順順順テーブルinitDecsを初期化する は、シーケンステーブルのエルゴードデータtoStering() を返す.
3)コード実現:
2)考え方:順序表ArayListは、配列で表し、一連の連続アドレス空間.その実施方法は、
3)コード実現:
package com.sam.datastruct.arrayList;
import java.util.Arrays;
import java.util.Date;
import java.util.Random;
/**
* ArrayList, 。
* @author LH-PC
* @param
*/
public class ArrayList {
private Object[] data = null; //data
private int length; //
private int current; //
/**
* 10
*/
public ArrayList(){
this(10);
}
/**
* ，
* @param initialSize
*/
public ArrayList(int initialSize){
if(initialSize >= 0){
this.length = initialSize; //
this.data = new Object[initialSize]; //
this.current = 0; // 0
}else {
throw new RuntimeException(" 0:" + initialSize); //
}
}
/**
* ,
* @param e
* @return
*/
public boolean add(E e){
//
ensureCapacity();
//
this.data[current++] = e;
// ++current; // ++
return true;
}
/**
* ,
* @param e
* @param index
* @return
*/
public boolean add(E e, int index){
if (index < 0 || index > current) { // ， false
System.err.print(new Date() + ": ");
return false;
}
//
ensureCapacity();
// index
for (int i = ++current; i > index; --i) {
this.data[i] = data[i - 1];
}
data[index] = e;
return true;
}
// index
public boolean update(E e, int index){
if (index < 0 || index >= current) {
System.err.print(new Date() + ": ");
}
data[index] = e;
return true;
}
public boolean remove(){
data[--current] = null;
return true;
}
/**
*
* @param index
* @return
*/
public boolean removeToIndex(int index){
// ： 。
// ， 。
//a b c
//0 1 2
//data[index] = data[index + 1]; //
//data //
// ，
if(index < 0 || index >= current){ // index ， false
System.err.print(new Date() + ": ");
return false;
}
for (int i = index; i < current - 1; i++) {
data[i] = data[i+1]; //
}
data[--current] = null; // null
// --current; // -1
return true;
}
/**
*
* @param index
* @return
*/
public E get(int index){
if(index >= 0){
return (E) data[index];
}else {
throw new RuntimeException(" 0:" + index);
}
}
/**
* ，
*
*/
public void ensureCapacity(){
//
if(current >= length){
length *= 2; // *2
data = Arrays.copyOf(data, length); //
}
}
/**
*
* @return
*/
public int size(){
return this.current;
}
/**
*
* @return
*/
public int length(){
return this.length;
}
/**
*
*
* @param args
*/
public boolean isEmpty(){
//return (current == 0) ? true : false;
return current == 0; // current == 0， ，
}
/**
*
* @param size
*/
public void initRamdomList(int size){
Random random = new Random();
StringBuffer sb = new StringBuffer();
for(current = 0; current < size; ++current){
ensureCapacity();
data[current] = random.nextInt(200);
sb.append("," + data[current]);
}
System.out.println(sb.length() > 0 ? sb.substring(1) : "");
}
/**
*
* @param size
*/
public void initNotDecs(int size){
ensureCapacity();
StringBuffer sb = new StringBuffer();
Random random = new Random();
data[0] = 1;
System.out.print(data[0]);
for(current = 1; current < size; ++current){
ensureCapacity();
data[current] = (Integer)data[(current - 1)] + random.nextInt(5);
sb.append("," + data[current]);
}
System.out.println(sb.length() > 0 ? sb.toString() : "");
}
/**
*
* @param size
*/
public void initacs(int size){
ensureCapacity();
StringBuffer sb = new StringBuffer();
Random random = new Random();
data[0] = 1;
System.out.print(data[0]);
for(current = 1; current < size; ++current){
ensureCapacity();
data[current] = (Integer)data[(current - 1)] + 1 + random.nextInt(5);
sb.append("," + data[current]);
}
System.out.println(sb.length() > 0 ? sb.toString() : "");
}
/**
*
* @param size
*/
public void initDecs(int size){
StringBuffer sb = new StringBuffer();
for(current = 0; current < size; ++current){
ensureCapacity();
data[current] = size - current;
sb.append("," + data[current]);
}
System.out.println(sb.length() > 0 ? sb.substring(1) : "");
}
/**
*
* @return string a[0],a[1],...,a[n]
*/
public String toString(){
StringBuffer sb = new StringBuffer();
for(int i = 0; i < this.current; ++i){
sb.append("," + this.data[i]);
}
if (sb.length() > 0) {
return sb.substring(1);
}
return "";
}
//
public static void main(String[] args) {
ArrayList list = new ArrayList(); // arrayList
// for (int i = 1; i <= 22; i++) {
// list.add(i);
// }
// list.removeToIndex(0);
// list.add(2, 1);
// list.removeToIndex(list.size());
// list
// for (int i = 0; i < list.size(); i++) {
// System.out.println(list.get(i));
// }
// list.initRamdomList(20);
// list.initacs(10);
list.initDecs(20);
list.remove();
System.out.println(list.toString());
}
}