链表

链表是动态的进行存储分配的一种结构。

我们知道，用数组存放数据时，必须事先定义固定的长度（即元素个数）。如果事先难以确定元素个数，则必须把数组定义的足够大，以便存放，显然这样会浪费内存。
而链表可根据需要开辟内存单元，不会浪费内存。
链表有一个“头指针”变量，它存放一个地址，该地址指向一个元素，这个元素又指向下一个元素......直到最后一个元素，该元素不再指向其他元素，称为“表尾”，链表到此结束。

单向链表：

如果想要实现链表，肯定要设计一个链表的节点类，此类中必须有一个属性保存下一个节点的引用地址

示例：具有增删查功能

package com.matto.linkedList;

/**
 * Created by matto on 6/17/16.
 */
class Link {

    class Node {                            //节点类，因为操作对象是节点所以创建
        private String data;
        private Node next;

        public Node(String data) {
            this.data = data;
        }

        public void add(Node newNode) {     //定义添加函数
            if (this.next == null) {        //如果调用的实例的下一个节点为空
                this.next = newNode;        //那么就把新节点设置给它
            } else {                        //如果下一个节点不为空
                this.next.add(newNode);     //那么递归调用添加函数向后添加
            }
        }

        public void print() {               //定义打印函数
            System.out.println(this.data + "	");
            if (this.next != null) {        //如果调用的示例的下一个不为空
                this.next.print();          //那么递归调用打印函数继续打印
            }
        }

        public boolean search(String data){ //内部的查找方法
            if(this.data.equals(data)){     //根据data判断当前节点是否存在
                return true;
            }else {
                if(this.next != null){      //如果调用search函数的实例的下一个节点不为空
                    return this.next.search(data);  //递归调用此查询函数继续查询
                }else{                              //否则返回false，即没有查到
                    return false;
                }
            }
        }

        public void delete(Node previous ,String data){ //删除函数
            if(data.equals(this.data)){                 //判断当前节点和传进来的节点是否是一个
                previous.next = this.next;              //是的话，将当前节点的下一个节点的引用地址给当前节点的上一个节点
            }else{
                if(this.next != null){                  //判断是否还有下一个节点
                    this.next.delete(this,data);        //不是的话，递归调用函数直到当前节点和传进来的节点是一个为止
                }
            }
        }
    }

    private Node root;                      //链表类的根节点属性

    public void addNode(String data) {      //链表类的添加节点函数
        Node newNode = new Node(data);      //使用节点类创建一个新节点
        if (this.root != null) {            //如果根节点不为空
            this.root.add(newNode);         //递归调用添加节点函数向后添加节点
        } else {                            //如果根节点为空
            this.root = newNode;            //将新节点设置为根节点
        }
    }

    public void printNode() {               //链表类的打印函数
        if (this.root != null) {            //如果根节点不为空
            this.root.print();              //递归调用节点类的输出函数进行输出
        }
    }

    public boolean contains(String name){     //查找节点函数
        return this.root.search(name);        //调用内部类的查找函数
    }

    public void deleteNode(String data){      //链表类的删除函数
        if(this.contains(data)){              //判断要删的节点是否存在
            if(this.root.data.equals(data)){    //判断要删的是否是根节点
                this.root = this.root.next;     //将根节点的下一个节点设置为根节点
            }else{
                this.root.delete(root,data);    //执行节点类的delete函数，传入根节点和要删除的节点
            }
        }
    }
}

public class LinkDemo02 {

    public static void main(String[] args) {
        Link l = new Link();                //创建一个link实例
        l.addNode("A");                     //使用Link类的添加节点函数进行添加
        l.addNode("B");
        l.addNode("C");
        l.addNode("D");
        l.addNode("E");

        //l.printNode();                      //使用Link类的打印函数进行节点输出
        //System.out.println(l.contains("A"));//使用Link类的实例调用contains方法判断名字为f 的节点是否存在
        l.deleteNode("A");                      //删除节点A
        l.printNode();

    }
}