单向 链表.txt

JAVA教程

kid_in_the_sky上传的代码，非常感谢！


import java.util.*;

public class Node{  //这个Node类写的很好！
 private int value;
 public Node next;
 
 public Node(){
  value = 0;
  next = null;
 }
 public Node(int valule){
    this.value = value;
    next = null;
  }
   
 public void setValue(int value){
  this.value = value;  
 } 
 public int getValue(){
  return value;
 }
 
 public void setNext(Node next){
  this.next = next;
 }
 public Node getNext(){
  return next;
 }
 
 public boolean equals(Node anotherNode){
  if(this.value == anotherNode.getValue())
   return true;
  return false;
 }
}

//////////////////

import java.util.*;

public class LinkList{
 
 Node head ; //链表的头结点
  int list_len;  //链表的长度（即元素个数），这个属性可有可无，有了比较方便。

///////初始化各属性
  public LinkList(){
   head = new Node();   //初始化一个链表时，head节点最初应该指向null.  head=null;
   list_len = 0;
  }  
  
//////返回链表头节点 
  public Node getHead(){
   return head;
  }
  //返回链表长度
  public int length(){
   return list_len;
  } 
   //把元素加在链表最前面.
  public void insertFirst(int value){
   
    Node node = new Node();               //可以直接用Node node = new Node(value); 构建一个新Node
    node.setValue(value);
                                                        
    node.setNext(head.getNext());    //以下三句修改为 insertFirst(node);
    head.setNext(node);                   
    list_len++;   
  }
  
    //把节点加在链表最前面
  public void insertFirst(Node node){
    node.setNext(head.getNext());    //修改为 node.setNext(head);    
    head.setNext(node);    //修改为  head = node;
    list_len++;
  }
  
  //把元素加在链表中第index个位置
  //可以考虑用value构造进一个Node后，直接调用addElement(Node node, int index)方法。
  public void addElement(int value, int index){  //先要判断head是否为空
   Node node = new Node();   
   node.setValue(value);
   
   Node p = head;
   Node q = head;   
   int i;
   
   //下面的逻辑大体是对的，但是可以进一步改进
   // 1. 让for循环结束时，p指向第index-1个节点，q=p;不要放在循环中做，甚至可以不用q
   // 2. 此时node.setNext(p.getNext());  p.setNext(node); list_len++; 即可
   for(i=0;i<list_len&&i<index;i++){  
   q = p;    
   p = p.getNext();
   }    
   if(i==index){
    q.setNext(node);
    node.setNext(p);
    list_len++;
   }
   else{  //此处的处理很好，考虑很周全。
    p.setNext(node);
    list_len++;
   }
  } 
 
  //把节点加在链表中第index个位置
  public void addElement(Node node, int index){   //逻辑与addElement(int value, int index)相同
   Node p = head;
   Node q = head;   
   int i;
   
   for(i=0;i<list_len&&i<index;i++){
   q = p;
   p = p.getNext();
   }    
   if(i==index){
    q.setNext(node);
    node.setNext(p);
    list_len++;
   }
   else{
    p.setNext(node);
    list_len++;
   }
 }
  //从链表中删除节点node
  public void removeElement(Node node){  //可能我前面的提示有些问题，删除节点一般要把该节点返回
   int i=0;
   if(list_len==0){
    System.out.println("the LinkList is empoty");   
   }else{
    Node p = head;
    Node q = new Node();
    
    for( i=0;i<list_len;i++){
     q = p;    //留下前一节点q以备后用，很好！
     if(p.equals(node))break;
     p = p.getNext();
    }   
    q.setNext(p.getNext());
    list_len--;
   }
   if(i==list_len)
    System.out.println("Fals");
  } 
  //从链表中删除第index位置处的节点
  public void removeElement(int index){
   int i=0;
   if(list_len==0){
    System.out.println("the LinkList is empoty");
   }else{
    
    Node p = head;
    Node q = new Node();
    for(i=0;i<list_len&&i<index;i++){
     q = p;
    p = head.getNext();
    }  
    q.setNext(p.getNext());
    list_len--;
   }
   if(i==list_len)
    System.out.println("Fals");
  } 
  public String toString(){
   return "There are "+list_len+" crunodes in this LinkList";
  }
 
}