Java实现线性表的链式存储
本文实例为大家分享了Java实现线性表的链式存储,供大家参考,具体内容如下
链表:一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
packagealgorithm.datastructure.linklist; importjava.util.NoSuchElementException; /* *链表 *物理存储上非连续的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现 * **/ publicclassLinkedList{ privateNodehead;//头节点 privateintsize;//链表长度 staticprivateclassNode{ privateintdata; privateNodenext; publicNode(){ } privateNode(intdata,Nodenext){ this.data=data; this.next=next; } } //初始化空链表 publicLinkedList(){ //head=null; } //添加元素 publicBooleanadd(intelement){ linkLast(element); returntrue; } //在某个位置之前添加元素 publicBooleanadd(intindex,Integerelement){ checkPositionIndex(index); if(index==size){ linkLast(element); }else{ linkBefore(element,node(index)); } returntrue; } //根据下标获取元素 publicintget(intindex){ checkElementIndex(index); returnnode(index).data; } //获取第一个元素 publicIntegergetFirst(){ Nodef=head; if(f==null){ thrownewNoSuchElementException(); }else{ returnf.data; } } //获取最后一个元素 publicIntegergetLast(){ if(size==0){ thrownewNoSuchElementException(); } intindex=size-1; returnnode(index).data; } //删除第一个元素 publicIntegerremoveFirst(){ Nodef=head; if(f==null){ thrownewNoSuchElementException(); }else{ returnunlink(head); } } //删除最后一个元素 publicIntegerremoveLast(){ if(size==0){ thrownewNoSuchElementException(); } intindex=size-1; returnunlink(node(index)); } //根据索引删除元素 publicIntegerremove(intindex){ checkElementIndex(index); returnunlink(node(index)); } //销毁链表 publicvoiddestroyList(){ clearList(); } //将链表置为空表 publicvoidclearList(){ for(Nodep=head;p!=null;){ Nodenext=p.next;//记录下一个结点 p=null;//删除当前结点 p=next;//指向下一个结点 } size=0; head=null; } //遍历链表 publicvoidtraverseList(){ for(Nodep=head;p!=null;){ System.out.println(p.data); p=p.next; } } //返回链表元素个数 publicintsize(){ returnsize; } //尾部添加结点 privatevoidlinkLast(intelement){ Nodecur=null,p; if(size==0){//没有结点时 head=newNode(element,null); size++; return; } for(p=head;p!=null;){//有结点时候 cur=p; p=cur.next; } cur.next=newNode(element,null);//尾部添加元素 size++; } //在某结点之前插入结点 privatevoidlinkBefore(intelement,Nodenode){ if(node==null){ linkLast(element); }else{ Nodep=head,q=p.next; if(node.data==p.data){//node为结点时候 head=newNode(element,p);//在头部插入元素 size++; }else{ while(p!=null){ if(q.data==node.data){ p.next=newNode(element,q);//在q之前(p之后)插入一个元素 size++; break; } p=p.next; q=p.next; } } } } //删除结点 privateIntegerunlink(Nodenode){ IntegerdeleteNodeData=null; Nodep=null; deleteNodeData=node.data; if(node.data==head.data){//该节点为头结点 p=head; head=p.next; p=null; size--; }else{ Nodeq=head; for(p=q.next;p!=null;){//使用两个指针,p,q if(p.data==node.data){ break; } q=q.next;//p始终为q的next结点 p=q.next; } q.next=p.next; p=null;//删除p size--; } returndeleteNodeData; } //数组下标是否越界 privateBooleanisElementIndex(intindex){ returnindex>=0&&index=0&&index<=size; } //检验下标是否越界,抛出异常 privatevoidcheckElementIndex(intindex){ if(!isElementIndex(index)){ try{ thrownewIndexOutOfBoundsException("下标越界"); }catch(Exceptione){ e.printStackTrace(); } } } //检验插入下标是否越界,抛出异常 privatevoidcheckPositionIndex(intindex){ if(!isPositionIndex(index)){ try{ thrownewIndexOutOfBoundsException("下标越界"); }catch(Exceptione){ e.printStackTrace(); } } } //返回指定位置的元素 privateNodenode(intindex){ intnowIndex=0; if(size>0){ for(Nodep=head;p!=null;){ if(nowIndex==index){ returnp; } p=p.next; nowIndex++; } } returnnull; } publicstaticvoidmain(String[]args){ java.util.LinkedListlinkedList0=newjava.util.LinkedList(); linkedList0.add(6); linkedList0.remove(0); linkedList0.size(); linkedList0.peek(); //linkedList0.getFirst(); linkedList0.clear(); //测试 LinkedListlinkedList=newLinkedList(); linkedList.add(2); linkedList.add(6); linkedList.add(0); linkedList.add(3); linkedList.add(8); linkedList.add(10); System.out.println(linkedList.get(0)); System.out.println(linkedList.getFirst()); System.out.println(linkedList.getLast()); System.out.println(linkedList.get(5)); System.out.println(linkedList.remove(5)); System.out.println(linkedList.remove(4)); linkedList.remove(2); linkedList.remove(0); linkedList.remove(0); linkedList.remove(0); linkedList.add(2); linkedList.add(6); linkedList.add(0); linkedList.add(3); linkedList.add(8); linkedList.add(10); linkedList.removeFirst(); linkedList.removeFirst(); linkedList.removeLast(); System.out.println(linkedList.size()); System.out.println("遍历链表"); linkedList.traverseList(); linkedList.add(0,4); linkedList.add(0,5); linkedList.add(2,5); linkedList.add(4,5); linkedList.add(6,9); linkedList.add(8,11); linkedList.add(9,222); //linkedList.linkBefore(3,newNode(3,null)); //linkedList.linkBefore(3,newNode(2,null)); //linkedList.linkBefore(3,newNode(2,null)); //linkedList.linkBefore(7,newNode(2,null)); //linkedList.linkBefore(9,newNode(7,null)); //linkedList.linkBefore(9,newNode(8,null)); System.out.println("遍历链表"); linkedList.traverseList(); linkedList.clearList(); } }
以上就是Java简单实现线性表的链式存储,更多功能可参考Java集合中的LinkedList实现。