Java模拟有序链表数据结构的示例
有序链表:
按关键值排序。删除链头时,就删除最小(/最大)的值,插入时,搜索插入的位置。
插入时需要比较O(N),平均O(N/2),删除最小(/最大)的在链头的数据时效率为O(1),
如果一个应用需要频繁的存取(插入/查找/删除)最小(/最大)的数据项,那么有序链表是一个不错的选择
优先级队列可以使用有序链表来实现
有序链表的插入排序:
对一个无序数组,用有序链表来排序,比较的时间级还是O(N^2)
复制时间级为O(2*N),因为复制的次数较少,第一次放进链表数据移动N次,再从链表复制到数组,又是N次
每插入一个新的链结点,不需要复制移动数据,只需要改变一两个链结点的链域
importjava.util.Arrays; importjava.util.Random; /** *有序链表对数组进行插入排序 *@authorstone */ publicclassLinkedListInsertSort<TextendsComparable<T>>{ privateLink<T>first;//首结点 publicLinkedListInsertSort(){ } publicbooleanisEmpty(){ returnfirst==null; } publicvoidsortList(T[]ary){ if(ary==null){ return; } //将数组元素插入进链表,以有序链表进行排序 for(Tdata:ary){ insert(data); } // } publicvoidinsert(Tdata){//插入到链头,以从小到大排序 Link<T>newLink=newLink<T>(data); Link<T>current=first,previous=null; while(current!=null&&data.compareTo(current.data)>0){ previous=current; current=current.next; } if(previous==null){ first=newLink; }else{ previous.next=newLink; } newLink.next=current; } publicLink<T>deleteFirst(){//删除链头 Link<T>temp=first; first=first.next;//变更首结点,为下一结点 returntemp; } publicLink<T>find(Tt){ Link<T>find=first; while(find!=null){ if(!find.data.equals(t)){ find=find.next; }else{ break; } } returnfind; } publicLink<T>delete(Tt){ if(isEmpty()){ returnnull; }else{ if(first.data.equals(t)){ Link<T>temp=first; first=first.next;//变更首结点,为下一结点 returntemp; } } Link<T>p=first; Link<T>q=first; while(!p.data.equals(t)){ if(p.next==null){//表示到链尾还没找到 returnnull; }else{ q=p; p=p.next; } } q.next=p.next; returnp; } publicvoiddisplayList(){//遍历 System.out.println("List(first-->last):"); Link<T>current=first; while(current!=null){ current.displayLink(); current=current.next; } } publicvoiddisplayListReverse(){//反序遍历 Link<T>p=first,q=first.next,t; while(q!=null){//指针反向,遍历的数据顺序向后 t=q.next;//no3 if(p==first){//当为原来的头时,头的.next应该置空 p.next=null; } q.next=p;//no3->no1pointerreverse p=q;//startisreverse q=t;//no3start } //上面循环中的if里,把first.next置空了,而当q为null不执行循环时,p就为原来的最且一个数据项,反转后把p赋给first first=p; displayList(); } classLink<T>{//链结点 Tdata;//数据域 Link<T>next;//后继指针,结点链域 Link(Tdata){ this.data=data; } voiddisplayLink(){ System.out.println("thedatais"+data.toString()); } } publicstaticvoidmain(String[]args){ LinkedListInsertSort<Integer>list=newLinkedListInsertSort<Integer>(); Randomrandom=newRandom(); intlen=5; Integer[]ary=newInteger[len]; for(inti=0;i<len;i++){ ary[i]=random.nextInt(1000); } System.out.println("----排序前----"); System.out.println(Arrays.toString(ary)); System.out.println("----链表排序后----"); list.sortList(ary); list.displayList(); } }
打印
----排序前---- [595,725,310,702,444] ----链表排序后---- List(first-->last): thedatais310 thedatais444 thedatais595 thedatais702 thedatais725
单链表反序:
publicclassSingleLinkedListReverse{ publicstaticvoidmain(String[]args){ Nodehead=newNode(0); Nodetemp=null; Nodecur=null; for(inti=1;i<=10;i++){ temp=newNode(i); if(i==1){ head.setNext(temp); }else{ cur.setNext(temp); } cur=temp; }//10.next=null; Nodeh=head; while(h!=null){ System.out.print(h.getData()+"\t"); h=h.getNext(); } System.out.println(); //反转1 //h=Node.reverse1(head); //while(h!=null){ //System.out.print(h.getData()+"\t"); //h=h.getNext(); //} //反转2 h=Node.reverse1(head); while(h!=null){ System.out.print(h.getData()+"\t"); h=h.getNext(); } } } /* *单链表的每个节点都含有指向下一个节点属性 */ classNode{ Objectdata;//数据对象 Nodenext;//下一节点 Node(Objectd){ this.data=d; } Node(Objectd,Noden){ this.data=d; this.next=n; } publicObjectgetData(){ returndata; } publicvoidsetData(Objectdata){ this.data=data; } publicNodegetNext(){ returnnext; } publicvoidsetNext(Nodenext){ this.next=next; } //方法1head被重置 staticNodereverse1(Nodehead){ Nodep=null;//反转后新的头 Nodeq=head; //轮换结果:012,123,234,....10nullnull while(head.next!=null){ p=head.next;//第1个换成第2个这时p表示原始序列头中的next head.next=p.next;//第2个换成第3个 p.next=q;//已经跑到第1位置的原第2个的下一个就要变成原第1个 q=p;//新的第1个要变成当前第一个 } returnp; } //方法2head没重置 staticNodereverse2(Nodehead){ //将中间节点的指针指向前一个节点之后仍然可以继续向后遍历链表 Nodep1=head,p2=head.next,p3;//前中后 //轮换结果:012,123,234,345,456....910null while(p2!=null){ p3=p2.next; p2.next=p1;//指向后变指向前 p1=p2;//2、3向前挪 p2=p3; } head.next=null;//head没变,当输出到0时,再请求0.next为1 returnp1; } }