testlink.java

数据结构 链表的java实现 简单易懂

class testLink { 
public static link union(link l1,link l2) { //将两个排序链表和在一起 
link l3=new link(); 
node tmpL1=l1.head; 
node tmpL2=l2.head; 
while(tmpL1!=null && tmpL2!=null) { 
if(tmpL1.data>tmpL2.data) { 
l3.append(tmpL2.data); 
tmpL2=tmpL2.next; 
} else { 
l3.append(tmpL1.data); 
tmpL1=tmpL1.next; 
} 
} 

while(tmpL1!=null) { 
l3.append(tmpL1.data); 
tmpL1=tmpL1.next; 
} 
while(tmpL2!=null) { 
l3.append(tmpL2.data); 
tmpL2=tmpL2.next; 
} 
return l3; 
} 

public static void main(String args[]) { 
link l1=new link(); 
l1.insertBefor(null,0); 
l1.append(23); //添加 
node n2=l1.append(49); 
node n1=l1.append(77); 
l1.append(120); 
l1.echo(); 

l1.insert(n1,100); //插入 
l1.echo(); 

l1.insertBefor(n2,555); //前插 
l1.insertBefor(n2,1234); 
l1.echo(); 
node n3=new node(111); 
l1.insertBefor(n3,999); 
l1.echo(); 

int arr[]={45,78,89,65,21,111,45,7,0,-56,999,455,33}; //数组变链表 
link l2=new link(arr); 
l2.echo(); 

l2.reverse(); //反转 
l2.echo(); 
l1.reverse(); 
l1.echo(); 

l1.order(); //排序 
l1.echo(); 
l2.order(); 
l2.echo(); 

link l3=union(l1,l2); //连接 
l3.echo(); 
} 
} 

class link { 
public node head; 

public link() { 
head=null; 
} 

public link(int [] arr){//从数组构造链表 
node tmp; 
if(arr.length==0) { 
head=null; 
} else { 
head=new node(arr[0]); 
tmp=head; 
for(int i=1;i<arr.length;i++) { 
tmp.next=new node(arr[i]); 
tmp=tmp.next; 
} 
} 
} 

public node append(int val) { //在link的后面添加节点 
node tmp; 
node jd=new node(val); 
if(head==null) { //原来为空 
jd.next=null; 
head=jd; 
return jd; 
} else { 
jd.next=null; 
tmp=head; 
while(tmp.next!=null) tmp=tmp.next; 
tmp.next=jd; 
return jd; 
} 
} 

public node insert(node jd,int val) { //在jd的后面插一个节点 
node tmp=jd.next; 
node jd1=new node(val); 
jd.next=jd1; 
jd1.next=tmp; 
return jd1; 
} 

public void del(node jd) { //删除某一个节点的直接后继节点 
if(jd.next==null) return; 
node tmp=jd.next; 
jd.next=tmp.next; 
return; 
} 

public node insertBefor(node jd,int val) {//在jd前插一个节点 
node tmp=head; 
node befor=head; 
node n1=new node(val); 

if(head==jd) { //jd是头节点 
n1.next=head; 
head=n1; 
return n1; 
} 
while(tmp!=null) { 
if(tmp==jd) { 
n1.next=jd; 
befor.next=n1; 
return n1; 
} 
befor=tmp; 
tmp=tmp.next; 
} 
befor.next=n1; 
return n1; 
} 

public void reverse() {//逆表 
link tmpLink=new link(); 
node tmpNode; 
node befor=null; 
tmpNode=head; 
while(tmpNode!=null){ 
befor=tmpLink.insertBefor(befor,tmpNode.data); 
tmpNode=tmpNode.next; 
} 
head=tmpLink.head; 
return; 
} 

public void order() { //链表排序 
link tmpLink=new link(); 
node tmpNode; 
node minNode; //最小节点 
node minBeforNode; //直接前驱 
node beforNode; 
while(head!=null) { 
tmpNode=head; 
minBeforNode=null; 
beforNode=head; 
minNode=head; 
while(tmpNode!=null) { 
if(tmpNode.data<minNode.data) { 
minBeforNode=beforNode; 
minNode=tmpNode; 
} 
beforNode=tmpNode; 
tmpNode=tmpNode.next; 
} 
tmpLink.append(minNode.data); 
if(minNode==head) {//如果最小的是头节点，删除最小节点 
head=head.next; 
} else del(minBeforNode); 
} 
head=tmpLink.head; 
} 

public void echo() { //输出链表 
node tmp=head; 
System.out.print("Begin-->"); 
while(tmp!=null) { 
System.out.print(tmp.data + "-->"); 
tmp=tmp.next; 
} 
System.out.println("End"); 
} 
} 

class node{//节点 
public int data; 
public node next; 

public node(int val) { 
data=val; 
next=null; 
} 
}