自定义线性表的简单例子

/*
* 创建日期 2005-2-5
*
* TODO 要更改此生成的文件的模板，请转至
* 窗口 － 首选项 － Java － 代码样式 － 代码模板
*/

/**
* @author bitan
*
* TODO 要更改此生成的类型注释的模板，请转至
* 窗口 － 首选项 － Java － 代码样式 － 代码模板
*/
public class Test4 {
class Digital {
private final int initSize;
private final int increase;
private Object[] arrays;
private int items;
private int capacity;
public void removeAll(int offset, int length) {
if (offset < 0 || length < 0 || (offset + length) > items)
throw new IllegalArgumentException("Arguments may be illegal.");
items -= length;
capacity -= ((capacity -items) / increase) * increase;
Object[] temps = new Object[capacity];
for (int i = 0; i < offset; i++) {
temps[i] = arrays[i];
}
for (int i = offset; i < items; i++) {
temps[i] = arrays[i + length];
}
arrays = temps;
}
public void addAll(Object[] os) {
addAll(items, os);
}
public void addAll(Digital d) {
addAll(items, d);
}
public void addAll(int index, Object[] os) {
if (index < 0) throw new IllegalArgumentException("Arguments may be illegal.");
if (os == null || os.length == 0) {
return;
}
items += os.length;
if (items > capacity) {
capacity += (((items - capacity)) / increase + 1) * increase;
}

Object[] temps = new Object[capacity];
for (int i = 0; i < index; i++) {
temps[i] = arrays[i];
}
for (int i = index, j = 0; j < os.length; i++, j++) {
temps[i] = os[j];
}
for (int i = (index + os.length), j = index; i < items; i++, j++) {
temps[i] = arrays[j];
}
arrays = temps;
}
public void addAll(int index, Digital d) {
addAll(index, d.toArrays());
}
public Object[] toArrays() {
Object[] temps = new Object[items];
for (int i = 0; i < items; i++) {
temps[i] = arrays[i];
}
return temps;
}
public void removeAll() {
init();
}
private void init() {
arrays = new Object[initSize];
items = 0;
capacity = initSize;
}
public int getCapacity() {
return capacity;
}
public int size() {
return items;
}
public Digital() {
initSize = 4;
increase = 2;
init();
}
public Digital(int initSize, int increase) {
if (initSize < 0 || increase <= 0)
throw new IllegalArgumentException("arguments may be illegal.");
this.increase = increase;
this.initSize = initSize;
init();
}
public Object elementAt(int index) {
if (index < 0 || index > this.items) {
throw new IllegalArgumentException("arguments may be illegal.");
}
return this.arrays[index];
}
public Object getFirstElement() {
return arrays[0];
}
public Object getLastElement() {
return arrays[items-1];
}
public void removeLastElement() {
removeElement(items - 1);
}
public void removeFirstElement() {
removeElement(0);
}
public void removeElement(int index) {
if (index < 0 || index > this.items) {
throw new IllegalArgumentException("arguments may be illegal.");
}
while(index < items -1) {
arrays[index] = arrays[index + 1];
index++;
}
arrays[index] = null;
items--;
if (items % increase == 0) {
this.capacity -= increase;
Object[] temps = new Object[capacity];
for (int i = 0; i < items; i++) {
temps[i] = arrays[i];
}
arrays = temps;
}
}

public void insertElement(int index, Object o) {
if (o == null || index < 0 || index > items)
throw new IllegalArgumentException("Argument may be illegal.");
items++;
if (items > capacity)
capacity += increase;
Object[] temps = new Object[capacity];
for (int i = 0; i < index; i++ ) {
temps[i] = arrays[i];
}
temps[index] = o;
for (int i = (index + 1); i < items; i++) {
temps[i] = arrays[i - 1];
}
arrays = temps;
}
public void addElement(Object o) {
insertElement(items, o);
}

public String toString() {
StringBuffer sb = new StringBuffer();
sb.append(this.getClass().getName() + " : (size=" + items + ", capacity=" + capacity + ") [");
for (int i = 0; i < this.items; i++) {
sb.append(arrays[i]);
if (i != items -1) {
sb.append(", ");
}
}
sb.append("]");
return sb.toString();
}
}

public static void main(String[] args) {
Test4 t4 = new Test4();
Digital d = t4.new Digital(3,2);
Digital d2 = t4.new Digital(6, 3);
String[] sArr = new String[8];
for (int i = 0; i < sArr.length; i++) {
sArr[i] = "aaaa" + i;
}
for (int i = 0; i < 4; i++) {
d.addElement("bbbb" + i);
}
d2.addAll(sArr);
System.out.println(d + "\n" + d2);
d2.addAll(2, d);
System.out.println(d2);
d2.removeAll(5, 4);
System.out.println(d2);
System.out.println("first=" + d2.getFirstElement() + ", last=" + d2.getLastElement() + ", index[5]=" + d2.elementAt(5));

d2.insertElement(7, "cccc0");
System.out.println(d2);
}
}

结果：

Test4$Digital : (size=4, capacity=5) [bbbb0, bbbb1, bbbb2, bbbb3]
Test4$Digital : (size=8, capacity=9) [aaaa0, aaaa1, aaaa2, aaaa3, aaaa4, aaaa5, aaaa6, aaaa7]
Test4$Digital : (size=12, capacity=15) [aaaa0, aaaa1, bbbb0, bbbb1, bbbb2, bbbb3, aaaa2, aaaa3, aaaa4, aaaa5, aaaa6, aaaa7]
Test4$Digital : (size=8, capacity=9) [aaaa0, aaaa1, bbbb0, bbbb1, bbbb2, aaaa5, aaaa6, aaaa7]
first=aaaa0, last=aaaa7, index[5]=aaaa5

Test4$Digital : (size=9, capacity=9) [aaaa0, aaaa1, bbbb0, bbbb1, bbbb2, aaaa5, aaaa6, cccc0, aaaa7]

结论：

一、设计线性表时，最复杂的是按索引增加和删除方法，最简单的是查找方法。

二、当实现几个功能类似的方法时，应该优先实现有索引参数的方法。然后，无索引参数的方法可以简单调用有索引参数的方法。