linklist.java

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

package LinkList;


import MyLib.MyApp;

public class LinkList {//链表结构体
	  Link first;
	  Link last;
	  MyApp app;
	  
	  public LinkList(){//把头指针置为空，这一步可做可不做
		  first=null;
		  app=new MyApp();
		  last=null;
	  } 
	  
	  public boolean IsEmpty(){//判断链表是否为空
		  return (first==null);
		  
	  }
	  
	  public void insertFirstRandom(){//头结点随机插入节点
		  Link newLink=new Link(app.nextInt(1,100),app.randomString(4,65,26));
		  if(IsEmpty())
			  last=newLink;
		  else{
		  newLink.next=first;
		  first.previous=newLink;
		  }
		  first=newLink;
		  
	  }
	  
	  public void insertFirst(int id,String name){//头节点按指定参数插入节点
		  Link newLink=new Link(id,name);
		  
		  if(first==null )
			 last=newLink;
		  else{
		  newLink.next=first;
		  first.previous=newLink;
		  }
		  first=newLink;
		  
		  
	  }
	  
	  public void sortedInsert(int key,String name){
		  //顺序插入，插入同时比较节点数据项的大小，找寻应该插入的位置插入
		  Link newLink=new Link(key,name);
		  Link cur=first;
		  Link previous=null;//初始当前节点的前一个节点为null
		  
		  while(cur!=null && newLink.id>cur.id){
			  //这个循环寻找该插入的位置
			  //找到要插入的位置的条件是
			  //当前节点为空或者 当要插入的节点的数据比当前节点数据要小
			   previous = cur;
			   
			   
			   cur=cur.next;//把节点向下一个节点推进
			  
			    //cur.previous=previous;
		  }//当这个循环结束，cur值应为newlink的next属性
		    //previous表示了cur值之前的那个节点位置，
		  //也即是说，previous的next就应该是newLink要插入的位置
		    
		  if(first==null/*链表没有数据 */|| cur==null/*要插入的位置是最后*/)
		     last=newLink;//这里定义了sortedInsert方法last值的变化
		  
		  if(previous==null){//链表为空
			  if(first!=null){//或者要插入的节点在第一个节点之前
			   first.previous=newLink;
			  }
				  
			  first=newLink;
		  }
		  else{
			 //插入节点
			  previous.next=newLink;
			  newLink.previous=previous;
		  }
		  newLink.next=cur;//要插入节点的下一个节点是cur
	  }
	  
	  
	  public void insertLast(int id,String name){//尾节点插入法
		    Link newLink=new Link(id,name);
		    if(IsEmpty()){
		    	first=newLink;
		        }
		    else{
		    last.next=newLink;//在当前尾节点添加下个节点
		    newLink.previous=last;//把last赋值给新节点的previous
		    }
		    last =newLink;//尾节点总是新节点
	  }
	  
	  public Link deleteFirst(){//删除头节点
		  
		  Link temp=first;//把旧的first存起来
		  first.next.previous=null;
		  first=first.next;//把当前节点的next给first
		  if(first.next==null || first==null)
			  last=first;
		  return temp;//把旧的first返回
	  }
	  
    public Link deleteLast(){//删除尾节点
		  
		  Link temp=last;//把旧的last存起来
		  last.previous.next=null;
		  last=last.previous;//把当前节点的previous给last，删除last
		  if(last.previous==null || last==null)
			  first=last;
		  return temp;//把旧的last返回
	  }
	  
	  public Link findFirst(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 Link findLast(int key){//从尾节点开始找寻指定内容的节点
		  Link cur=last;
		  Link result=null;
		  while(cur.previous!=null){
			  if(cur.id==key){
				 result=cur;
				 break;
			  }
			  else
				  cur=cur.previous;
			  
		  }
		  return result;
	  }
	  
	  
	  public void deleteLinkNode(int key){//删除指定key的节点
		  Link cur=first;
		  Link previous=first;
		  if(first==null){
			  System.out.println("nothing can be deleted");
			  return;
		  }
		  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;//删除节点，
		       cur.next.previous=previous;  
		  }
	  }
	  
	  
	  public void displayLinkFirst(){//头遍历链表和显示
		  System.out.println("display first to last ");
		  Link cur =first;
		  if(cur!=null)
		  while(cur!=null){//当前节点的next(指向下个节点)不为空
			  System.out.println("=======================");
			  cur.displayLink();//显示当前节点内容
			  if(cur.previous!=null){
			  System.out.print("its previous is ");
			  cur.previous.display();
			
			  }
			  if(cur.next!=null){
				  System.out.print("its next is ");
				  cur.next.display();
				  System.out.println();
				  }
			  System.out.println("=======================");
			  cur=cur.next;//把当前节点移向next指向的下个节点
		  } 
		  else
			  System.out.println("nothing to display");
		  System.out.println("");
	  }
	  
	  public void displayLinkLast(){//头遍历链表和显示
		  System.out.println("display last to first ");
		  Link cur =last;
		  if(cur!=null)
		  while(cur!=null){//当当前节点的previous(指向下个节点)不为空
			  cur.displayLink();//显示当前节点内容
			  cur=cur.previous;//把当前节点移向next指向的下个节点
		  } 
		  else
			  System.out.println("nothing to display");
		  System.out.println("");
	  }
	  
	  public Iterator getIterator(){//和迭代器联系起来
		  return (new Iterator(this));
	  }
	  
	  public Link getFirst(){//得到头节点
		  return first;
	  }
	  
	  public Link getLast(){//得到尾节点
		  return last;
	  }
	  

}