本文档主要讲解类Java表中常见的三种表的实现，每种类中详细的介绍了每种类中要实现的方法和方式。常见的基本方法为clear（）、add（）、get（）、set（）、remove（）、contains （），在这里重点提出来contains这个方法，大家重点看，在笔试和面试中经常会考到。

在表的学习中，把握以下两点：1）针对数组表，构建ArrayList时，类中首先包含两个私有属性（theSize和item[]），接下来编写构造方法和基本方法。2）针对链表，类中首先要有节点类，这里节点类我们设计为静态内部类（节点基本要素），接下来编写构造方法和基本方法。

下面是三种表的具体实现类，类的后面是测试类，可以进行已定义的各种操作。测试类后面附上测试结果图，以做参考。

希望大家在编写的过程中能够领会到表的内涵！

肖龙-上海师范大学

2013-7-30

第一类表——ArrayList（类后面附上测试类）

表类

public class MyArrayList {

private int theSize;

private Object[] elementData;

public MyArrayList(){

clear();

}

public void clear(){

theSize=0;

enSureCapacity(10);

}

public int size(){

return theSize;

}

public void enSureCapacity(int newCapacity){

if(newCapacityreturn;

Object[] old=elementData;

elementData=(Object[]) new Object[newCapacity];

for(int i = 0;ielementData[i]=old[i];

theSize=newCapacity;

}

public boolean add(Object e){

add(size(),e);return true;

}

public void add(int index,Object e){

if (index >size() || index < 0)

throw new IndexOutOfBoundsException("Index: "+index+

else if(index ==size()){

enSureCapacity(size()+1);}

else{

enSureCapacity(size()+1);

System.arraycopy(elementData, index, elementData, index + 1, size()-index-1);}

elementData[index]=e;

}

public void addAll(int index,Object[] e){

if (index > size() || index < 0)

throw new IndexOutOfBoundsException("Index: "+index+

if(elementData.length==size())

enSureCapacity(size()+e.length);

System.arraycopy(elementData, index, elementData, index +

e.length, e.length);

for(int i=index;ielementData[i]=e[i-index];

}

public Object set(int index,Object e){

if (index > size() || index < 0)

throw new IndexOutOfBoundsException("Index: "+index+

Object[] oldE=elementData;

elementData[index]=e;

return oldE;

}

public Object get(int index){

if (index > size() || index < 0)

throw new IndexOutOfBoundsException("Index: "+index+

return elementData[index];

}

public Object remove(int index){

if (index > size() || index < 0)

throw new IndexOutOfBoundsException("Index: "+index+

elementData[i]=elementData[i+1];

theSize--;

return oldE;

}

public boolean contains(Object e){

if(indexOf(e)>=0)

System.out.println("true");

else

System.out.println("false");

return indexOf(e)>=0;

}

public int indexOf(Object e){

if(e==null){

for(int i=0;i{if(elementData[i]==e)

return i;}

}else{

for(int i=0;i{if(elementData[i]==e)

return i;}

}

return -1;

}

public void showList(){

System.out.print("List= ");

for(int i=0;iif(iSystem.out.print(elementData[i]+"-");

else

System.out.print(elementData[i]);

System.out.println();

}

public void showList(Object[] e){

System.out.print("List= ");

for(int i=0;iif(iSystem.out.print(e[i]+"-");

else

System.out.print(e[i]);

System.out.println();

}

public void overTurn(){elementData=(Object[]) new Object[size()];

showList();

showList(oldList);

for(int i=0;ielementData[i]=oldList[size()-1-i];}

showList();

System.out.print("overturn List= ");

for(int i=0;iif(iSystem.out.print(elementData[i]+"-");

else

System.out.print(elementData[i]);

System.out.println();

}

public boolean isEmpty(){

if(size()==0)

System.out.println("The list is empty");

else

System.out.println("The list is not empty");

return size()==0;

}

public void listNext(int index){

Object a=null;

if (index > size() || index < 0){

throw new IndexOutOfBoundsException("Index: "+index+

}else if(index < size()-1){

a=elementData[index+1];

System.out.println("The "+elementData[index]+"'s next one is"+a);

}else{

System.out.println("The "+elementData[index]+"don't has a next element");}

}

public boolean listhasNext(int index){

if (index > size() || index < 0){

throw new IndexOutOfBoundsException("Index: "+index+

}else if(index < size()-1){

System.out.println("true");

}else{

System.out.println("false");

}

}

}

测试类

public class ListMain {

static Object[] intE={1,2,3,4};

public static void main(String[] args) {

MyArrayList element=new MyArrayList();

element.enSureCapacity(10);

System.out.println(((MyArrayList) element).size());

element.add(0,intE[0]);

System.out.println(((MyArrayList) element).size());

System.out.println(((MyArrayList) element).get(0));

element.addAll(0, intE);

System.out.println(((MyArrayList) element).size());

System.out.println(((MyArrayList) element).get(3));

System.out.println(((MyArrayList) element).get(4));

System.out.println(((MyArrayList) element).set(4,5));

System.out.println(((MyArrayList) element).get(4));

element.remove(4);

System.out.println(((MyArrayList) element).size());

System.out.println(((MyArrayList) element).get(3));

System.out.println(((MyArrayList) element).get(4));

element.remove(3);

System.out.println(((MyArrayList) element).size());

System.out.println(((MyArrayList) element).get(2));

System.out.println(((MyArrayList) element).get(3));

System.out.println("-_-");

element.set(2, 10);

System.out.println(((MyArrayList) element).get(2));

element.contains(10);

System.out.println("0_0");

element.showList();

element.add(7);

element.showList();

System.out.println(((MyArrayList) element).size());

element.add(12,8);

System.out.println(((MyArrayList) element).size());

element.showList();

element.add(8);

System.out.println(((MyArrayList) element).size());

element.showList();

element.set(14, 'a');element.showList();

element.contains('a');

element.contains('b');

element.overTurn();

element.isEmpty();

element.listNext(14);

element.listNext(15);

element.listhasNext(14);

}

}

第二类表——SingleLinkedList（类后面附上测试类）

表类

public class MyLinkedListS {

public static class NodeD{

public NodeD(Object d,NodeD n){ data=d; nextP=n;

}

public Object data;

public NodeD nextP;

}

private int theSize;

private int modCount=0;

private NodeD beginMaker;

private NodeD endMaker;

public MyLinkedListS(){

clear();

}

public void clear(){

beginMaker=new NodeD(null,null);

endMaker=new NodeD(null,null);

beginMaker.nextP=endMaker;

theSize=0;

modCount++;

}

public int size(){

return theSize;

}

public boolean isEmpty(){

return size()==0;

}

public boolean add(Object e){

add(size()+1,e);

return true;

}

public void add(int index,Object e){

if(size()==0){

if(index==1)

endMaker=new NodeD(null,null);

NodeD newNode1=new NodeD(e,endMaker);

beginMaker=new NodeD(null,newNode1);} if(size()!=0){

if(index==1){

NodeD Node1=getNode(1);

NodeD newNode1=new NodeD(e,Node1);

beginMaker=new NodeD(null,newNode1);

}

else if(index==size()+1){

NodeD priN=getNode(index-1);

endMaker=new NodeD(null,null);

NodeD newNodeE=new NodeD(e,endMaker);

priN.nextP=newNodeE;

}

else{

NodeD priN=getNode(index-1);

NodeD nexN=getNode(index);

NodeD newNode=new NodeD(e,nexN);

priN.nextP=newNode;

newNode.nextP=nexN;

}

}

/*

NodeD priN=getNode(index-1);

NodeD nexN=getNode(index+1);

NodeD newNode=new NodeD(e,nexN);

priN.nextP=newNode;

newNode.nextP=nexN;

theSize++;theSize++;

modCount++;

}

public NodeD getNode(int index){

NodeD p;

if (index >size() || index <= 0)

throw new IndexOutOfBoundsException("Index: "+index+

else

p=beginMaker;

for(int i=1;i<=index;i++)

p=p.nextP;

return p;

}

public Object get(int index){

return getNode(index).data;

}

public Object set(int index,Object newValue){

Object oldVal=get(index);

NodeD p=getNode(index);

p.data=newValue;

return oldVal;

}

public void removeN(int index){

if(size()==1){

NodeD Node2=getNode(index).nextP;

beginMaker=new NodeD(null,Node2);

}

else{

if(index==1){

NodeD Node2=getNode(index).nextP;

beginMaker=new NodeD(null,Node2);

}else if(index==size()){

NodeD Node2=getNode(index-1);

endMaker=new NodeD(null,null);

Node2.nextP=endMaker;

}else{

NodeD priN=getNode(index-1);

NodeD nexN=getNode(index+1);

priN.nextP=nexN;

}

}

theSize--;}

public boolean containS(Object e){ if(indexOfE(e)>0)

System.out.println("true");

else

System.out.println("false");

return indexOfE(e)>0;

}

public int indexOfE(Object e){

NodeD p;

p=beginMaker;

if(e==null){

for(int i=1;i<=size();i++){

p=p.nextP;

if(p.data==e)

return i;

}

}else{

for(int i=1;i<=size();i++){

p=p.nextP;

if(p.data==e)

return i;

}

}

return -1;

}

public void showLinkedList(){

NodeD p;

p=beginMaker;

System.out.print("List= ");

for(int i=1;i<=size();i++){

p=p.nextP;

if(iSystem.out.print(p.data+"-");

else

System.out.print(p.data);

}

System.out.println();

}

public void LinkedListNext(int index){Object a=null,b=null;

/* NodeD Node1=getNode(index);

NodeD Node2=Node1.nextP;

a=Node2.data;

b=Node1.data;*/

if (index >size() || index <= 0){

throw new IndexOutOfBoundsException("Index: "+index+

}else if(indexa=get(index+1);

b=get(index);

System.out.println("The "+b+"'s next one is"+a);

}else{

b=get(index);

System.out.println("The "+b+"don't has a next element");} }

}

测试类

public class LinkedListMain{

static Object[] intE={1,2,3,4};

public static void main(String[] args) {

MyLinkedListS elementL=new MyLinkedListS();

System.out.println(elementL.size());

elementL.add(intE[0]);

elementL.removeN(1);

elementL.add(intE[0]);

System.out.println(elementL.size());

System.out.println(elementL.get(1));

elementL.add(intE[1]);

elementL.removeN(2);

elementL.add(intE[1]);

System.out.println(elementL.size());

System.out.println(elementL.get(2));

elementL.add(intE[2]);

elementL.add(intE[3]);

System.out.println(elementL.size());

System.out.println(elementL.get(3));

elementL.add(5);

elementL.add(6);

elementL.add(7);elementL.add(8);

elementL.add(9);

elementL.add(10);

System.out.println(elementL.size());

System.out.println(elementL.get(10));

elementL.showLinkedList();

elementL.removeN(2);

System.out.println(elementL.size());

System.out.println(elementL.get(2));

elementL.showLinkedList();

elementL.removeN(1);

System.out.println(elementL.size());

System.out.println(elementL.get(1));

elementL.containS(10);

elementL.showLinkedList();

elementL.LinkedListNext(1);

}

}

第三类表——DoubleLinkedList（类后面附上测试类）

表类

public class MyLinkedListD {

public static class NodeD{

public NodeD(Object d,NodeD p,NodeD n){ data=d; prevP=p; nextP=n;

}

public Object data;

public NodeD prevP;

public NodeD nextP;

}

private int theSize;

private int modCount=0;

private NodeD beginMaker;

private NodeD endMaker;public MyLinkedListD(){

clear();

}

public void clear(){

beginMaker=new NodeD(null,null,null);

endMaker=new NodeD(null,null,null);

beginMaker.nextP=endMaker;

endMaker.prevP=beginMaker;

theSize=0;

modCount++;

}

public int sizeD(){

return theSize;

}

public boolean isEmptyD(){

return sizeD()==0;

}

public boolean add(Object e){

add(sizeD()+1,e);

return true;

}

public void add(int index,Object e){

if(sizeD()==0){

NodeD newNode=new

NodeD(e,beginMaker,endMaker);

beginMaker.nextP=newNode;

endMaker.prevP=newNode;}

else

if(index==1){

NodeD ng1=getNodeD(index);

NodeD newNode=new

NodeD(e,beginMaker,ng1);

beginMaker.nextP=newNode;

ng1.prevP=newNode;

}else if(index==sizeD()+1){

NodeD ng2=getNodeD(index-1);

NodeD newNode=new

NodeD(e,ng2,endMaker);

ng2.nextP=newNode;

endMaker.prevP=newNode;

}else{

NodeD ng3=getNodeD(index-1);

NodeD ng4=getNodeD(index);

NodeD newNode=new NodeD(e,ng3,ng4);

ng3.nextP=newNode;

ng4.prevP=newNode;

}

theSize++;

modCount++;

}

public NodeD getNodeD(int index){

NodeD p;

if (index >sizeD() || index <= 0)

throw new IndexOutOfBoundsException("Index: "+index+

else if(index<=sizeD()/2){

p=beginMaker;

for(int i=1;i<=index;i++)

p=p.nextP;

}else{

p=endMaker;

for(int i=sizeD();i>=index;i--)

p=p.prevP;

}

return p;

}

public Object getData(int index){

return getNodeD(index).data;

}

public Object set(int index, Object newVal){

if (index >sizeD() || index <= 0)

throw new IndexOutOfBoundsException("Index: "+index+

Object oldVal=getData(index);

NodeD p=getNodeD(index);

p.data=newVal;

return oldVal;

}

public void removeDN(int index){

if (index >sizeD() || index <= 0){

throw new IndexOutOfBoundsException("Index: "+index+

beginMaker.nextP=getNodeD(index).nextP;

getNodeD(index).prevP=beginMaker;

}else if(index==sizeD()){

getNodeD(index).prevP.nextP=endMaker;

endMaker.prevP=getNodeD(index).prevP; //注意顺序}else{

getNodeD(index).prevP.nextP=getNodeD(index).nextP;

getNodeD(index).nextP.prevP=getNodeD(index).prevP;

}

theSize--;

modCount++;

}

public boolean containsD(Object e){

if(indexOfD(e)>0)

System.out.println("true");

else

System.out.println("false");

return indexOfD(e)>0;

}

public int indexOfD(Object e){

NodeD p;

p=beginMaker;

if(e==null){

for(int i=0;ip=p.nextP;

if(p.data==e)

return i;}

}else{

for(int i=0;ip=p.nextP;

if(p.data==e)

return i;}

}

return -1;

}

public void showLinkedListD(){

NodeD p;

p=beginMaker;

System.out.print("List= ");

for(int i=1;i<=sizeD();i++){

p=p.nextP;if(iSystem.out.print(p.data+"-");

else

System.out.print(p.data);

}

System.out.println();

}

public void LinkedListNextD(int index){

Object a=null,b=null;

/* NodeD Node1=getNode(index);

NodeD Node2=Node1.nextP;

a=Node2.data;

b=Node1.data;*/

if (index >sizeD() || index <= 0){

throw new IndexOutOfBoundsException("Index: "+index+

}else if(indexa=getData(index+1);

b=getData(index);

System.out.println("The "+b+"'s next one is"+a);

}else{

b=getData(index);

System.out.println("The "+b+"don't has a next element");} }

}

测试类

public class DlinkedListMain {

static Object[] intE={1,2,3,4};

public static void main(String[] args) {

MyLinkedListD elementD=new MyLinkedListD();

System.out.println(elementD.sizeD());

elementD.add(intE[0]);

System.out.println(elementD.sizeD());

System.out.println(elementD.getData(1));

elementD.add(intE[1]);

elementD.add(intE[2]);

elementD.add(intE[3]);

System.out.println(elementD.sizeD());System.out.println(elementD.getData(3));

System.out.println(elementD.getData(4));

elementD.set(1, 0);

System.out.println(elementD.sizeD());

System.out.println(elementD.getData(1));

elementD.removeDN(1);

System.out.println(elementD.sizeD());

System.out.println(elementD.getData(1));

elementD.showLinkedListD();

elementD.removeDN(3);

elementD.removeDN(2);

System.out.println(elementD.sizeD());

elementD.showLinkedListD();

elementD.removeDN(1);

//elementD.LinkedListNextD(2);

System.out.println(elementD.sizeD());

elementD.showLinkedListD();

elementD.removeDN(1);

}

}下载本文