linklist.java

数据结构 包括数组(Array包) 和二叉树(Tree) 链表(Linelist包) 等等

package Link;


import java.util.*;
import MyLib.MyApp;

class LinkApp{
	 public static void main(String[] args ){
		 Random rn=new Random();
		 LinkList myLink=new LinkList();//建立一个链表对象
		 for(int i=25;i>0;i--){//在链表里插入25个节点
			 int randomNum=rn.nextInt(100);
			System.out.println(randomNum+" inserted");
			 //myLink.insertLast(i, "me");
			// myLink.insertFirst(i,"me");
			 //myLink.insertFirstRandom();
			 myLink.sortedInsert(randomNum, "me");
		 }
		  //myLink.last.displayLink();
		 //myLink.displayLink();//显示节点内容
		  //System.out.println("删除节点1-23");
		  //for(int i=0;i<25;i++)
			//  myLink.deleteLink(i);
		 
		  myLink.displayLink();
		  myLink.first.displayLink();
		//  myLink.last.displayLink();
		 
		  
	 }
}
//===================================================================
public class LinkList {//链表结构体
	  Link first;
	  Link last;
	  MyApp app;
	  public LinkList(){//把头指针置为空，这一步可做可不做
		  first=null;
		  app=new MyApp();
		  last=null;
	  } 
	  
	  public boolean LinkListIsEmpty(){//判断链表是否为空
		  return (first==null);
		  
	  }
	  
	  public void insertFirstRandom(){//头结点随机插入节点
		  Link newLink=new Link(app.nextInt(1,100),app.randomString(4,65,26));
		  newLink.next=first;
		  first=newLink;
		  
	  }
	  
	  public void insertFirst(int id,String name){//头节点按指定参数插入节点
		  Link newLink=new Link(id,name);
		  
		  if(first==null )
			 last=newLink;
		  
		  newLink.next=first;
		  first=newLink;
		  
		  
	  }
	  
	  public void sortedInsert(int key,String name){//顺序插入
		  Link newLink=new Link(key,name);
		  Link cur=first;
		  Link previous=null;
		  while(cur!=null && newLink.id>cur.id){
			   previous = cur;
			   cur=cur.next;//把节点向下一个节点推进
		  }
		  
		  
		  
		  if(previous==null){//链表为空
			  first=newLink;
		  }
		  else{
			 //插入节点
			  previous.next=newLink;
		  }
		  newLink.next=cur;
	  }
	  
	  
	  public void insertLast(int id,String name){//尾节点插入法
		    Link newLink=new Link(id,name);
		    if(LinkListIsEmpty()){
		    	first=newLink;
		        last=newLink;
		        }
		    else{
		    last.next=newLink;//在当前尾节点添加下个节点
		    last =newLink;//更新当前尾节点
		    }
	  }
	  
	  public Link deleteFirst(){//删除头节点
		  
		  Link temp=first;//把旧的first存起来
		  first=first.next;//把当前节点的next给first
		  if(first.next==null || first==null)
			  last=first;
		  return temp;//把旧的first返回
	  }
	  
	  
	  
	  public Link find(int key){//找寻指定内容的节点
		  Link cur=first;
		  Link result=null;
		  while(cur.next!=null){
			  if(cur.id==key){
				 result=cur;
				 break;
			  }
			  else
				  cur=cur.next;
			  
		  }
		  return result;
	  }
	  
	  public void deleteLink(int key){//删除指定key的节点
		  Link cur=first;
		  Link previous=first;
		  
		  while(cur.id!=key){
			   if(cur.next!=null){
				   previous=cur;//设定前一节点的指针
				   cur=cur.next;//把当前节点向后移动
			   }else
				   return;
			   }
		  if(cur==first){
			  first=first.next;
		  }else
			  previous.next=cur.next;//删除节点，
		         //把指向当前节点的指针等于指向下个节点的指针
	  }
	  
	  
	  public void displayLink(){//遍历链表和显示
		  System.out.println("display first to last ");
		  Link cur =first;
		  if(cur!=null)
		  while(cur!=null){//当当前节点的next(指向下个节点)不为空
			  cur.displayLink();//显示当前节点内容
			  cur=cur.next;//把当前节点移向next指向的下个节点
		  } 
		  else
			  System.out.println("nothing to display");
		  System.out.println("");
	  }
  
}


//==================================================================
class Link{//链表的节点类
	  Link next;
	  int id;
	  String name;
	  
	  Link(int inputId,String inputName){
		  id=inputId;
		  name=inputName;
		  
	  }
	  public void displayLink(){
		  System.out.println("id: "+id+" name: "+name);
	  }
	
	  
}