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;
}
}