链表的有关操作

《链表的有关操作》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、publicclassSingleLinkedList>{privatestaticclassNode{publicAnyTypedata;publicNodenextNode;publicNode(AnyTyped,Noden){data=d;nextNode=n;}publicNode(AnyTyped){data=d;nextNode=null;}publicNode(){data=null;nextNode=null;

2、}}privateinttheSize;//表的大小privateNodeheadNode;//单链表的头节点publicSingleLinkedList(){//构造空单链表headNode=null;theSize=0;}publicintsize(){//单链表的大小returntheSize;}publicAnyTypeget(intidx){returngetNode(idx).data;}publicAnyTypeset(intidx,AnyTypenewVal){Nodep=getNode(idx);AnyT

3、ypeoldVal=p.data;p.data=newVal;returnoldVal;}privateNodegetNode(intidx){Nodep;if(idx<0

4、

5、idx>size())thrownewIndexOutOfBoundsException("getNodeindex:"+idx+";size:"+size());p=headNode;for(inti=0;i

6、e(),x);returntrue;}publicvoidadd(intidx,AnyTypex){NodenewNode=newNode(x);if(this.headNode==null

7、

8、idx==0){//边界条件：空表插入或者在idx=0的节点之前插入Nodeq=newNode(x);newNode.nextNode=headNode;headNode=newNode;theSize++;}else{//单链表非空并且idx>0Nodep;p=getNode(

9、idx-1);newNode.nextNode=p.nextNode;p.nextNode=newNode;theSize++;}}publicbooleanremove(intidx){if(headNode==null)returnfalse;if(idx==0

10、

11、this.headNode.nextNode==null){//只有一个数据元素Nodep=this.headNode;headNode=null;theSize--;}else{Nodep=getNode(idx-1),q;q=p.nextNode;p.n

12、extNode=q.nextNode;theSize--;}returntrue;}publicintgetSize(SingleLinkedListLa){intcount=0;Nodep=La.headNode;if(La.headNode==null)return0;while(p!=null){++count;p=p.nextNode;}returncount;}publicintcontains(AnyTypex,SingleLinkedListLa){intidx=0;Nodep=La.hea

13、dNode;if(La.headNode==null)return-1;while(p.data!=x){idx++;p=p.nextNode;if(p==null)return-1;}returnidx;}publicvoidmergeSort(SingleLinkedListLa,SingleLinkedListLb,SingleLinkedListLc){Nodepa=La.headNode,pb=Lb.headNode,tmp;while(pa!=null&&pb!=null){//合并if(pa.data.compareTo(pb

14、.data)<0){tmp=pa;pa=pa.nex