关于链表

链表是包含一些数据的独立数据结构（也成为节点）的集合，每个节点都是通过指针链接在一起的。通常节点是动态分配的。事实上，链表中的节点可以存在于内存中的各个地方。，所以在物理上是不是相邻并无影响。

链表在数据结构中占有很大的作用，它可以根据使用情况分配内存，避免内存的浪费。它的插入，删除，查找都是根据指针的访问来实现，删除或添加一个节点不会改变其他数据的位置和内容，和数组相比，链表具有很强的灵活性和可操作性，但是在使用和实现的时候稍微麻烦，而且比较抽象。

 

单链表

在单链表中，每个节点都包含指向下一个节点的指针，最后一个节点的指针为NULL，以标志最后一个节点。之所以叫单链表也是因为每个节点只存在一个节点指针而已，所以只能顺序访问下一个节点，俗话就是过了这个村就没这个店了。为了记住单链表的第一个位置，可以定义一个头指针head。

/**
   * 建立单链表中，函数是一个指针函数，指针类型是节点，它最终的返回值是头节点。函数里建立了三个节点指针，
   * 分别是头节点指针，当前节点指针和前一个节点指针。先建立头指针，数据为0，指针为NULL。通过传递给该函
   * 数的参数n来确定节点的个数。在n个循环内一直建立当前节点，当前节点的数据键盘输入，当前节点指针为空。
   * 前一节点的指针指向当前节点，最后把当前指针替换为前一个指针进行下一次循环。
   * @param n
   * @return
   */
  Node createChain(int n){
  
    Node head,current,previous;
    int i;
    previous = new Node();
    previous.setNodeValue(0);
    previous.setNextNode(null);
    head = previous;
   
    for(i=0;i<n;i++){
     current = new Node();
     current.setNextNode(null);
     previous.setNextNode(current);
     previous = current;
    }
    return head;
   
  }
  /**
   * 函数中，先遍历节点，直到找到需要添加节点的位置，如果遍历到最后一个节点，函数返回，如果跳出遍历循环，
   * 说明是插入位置，申请一个新的节点，数据为x，指针指向当前节点指向的后一个节点，当前节点（实际上已经是
   * 旧的节点）指向新节点
   * @param head
   * @param i
   * @param m
   * @return
   */
  int insert(Node head,int i,int m){
   Node current,newNode;
   int j;
   if(i < 1)
    return 0;
   
   current = head;
   j = 0;
   while((j<i-1)&&current != null ){
    current = current.getNextNode();
    j++;
   }
   if(current == null)
    return 0;
   newNode = new Node();
   newNode.setNodeValue(m);
   newNode.setNextNode(current.getNextNode());
   current.setNextNode(newNode);
   return 1;
  }
  
  /**
   * 函数中，先遍历节点，直到找到需要删除节点的位置，将需要删除的节点前一个节点的指针指向其后一个节点，释放内存。
   * @param head
   * @param i
   * @return
   */
  int delete(Node head,int i){
   Node current,previous;
   int j=1;
   if(i < 0)
    return 0;
   
   previous = head;
   while((j<i)&&previous.getNextNode() != null){
    previous = previous.getNextNode();
    j++;
   }
   if(previous.getNextNode() == null)
    return 0;
   
   current = previous.getNextNode();
   previous.setNextNode(current.getNextNode());
   current = null;
   return 1;
  }
  
  
  
 }
 class Node{

  public int getNodeValue() {
   return nodeValue;
  }

  public void setNodeValue(int nodeValue) {
   this.nodeValue = nodeValue;
  }

  public Node getNextNode() {
   return nextNode;
  }

  public void setNextNode(Node nextNode) {
   this.nextNode = nextNode;
  }

  private int nodeValue;
  private Node nextNode;
  
  
  public Node(){
   this(0,null);
  }
  
  public Node(int value,Node nextNode){
   this.nodeValue = value;
   this.nextNode = nextNode;
  }
  
  
  
 }