单向链表

链表本身也是线性表，只不过物理存储上不连续

//线性表接口
public interface List {
    //获得线性表长度
    public int size();

    //判断线性表是否为空
    public boolean isEmpty();

    //插入元素
    public void insert(int index, Object obj) throws Exception;

    //删除元素
    public void delete(int index) throws Exception;

    //获取指定位置的元素
    public Object get(int index) throws Exception;
}

Node.java:结点类

//结点类
public class Node {

    Object element; //数据域
    Node next;  //指针域

    //头结点的构造方法
    public Node(Node nextval) {
        this.next = nextval;
    }

    //非头结点的构造方法
    public Node(Object obj, Node nextval) {
        this.element = obj;
        this.next = nextval;
    }

    //获得当前结点的指针域
    public Node getNext() {
        return this.next;
    }

    //获得当前结点数据域的值
    public Object getElement() {
        return this.element;
    }
    //设置当前结点的指针域
    public void setNext(Node nextval) {
        this.next = nextval;
    }

    //设置当前结点数据域的值
    public void setElement(Object obj) {
        this.element = obj;
    }

    public String toString() {
        return this.element.toString();
    }
}

LinkList.java:单向链表类(核心代码)

//单向链表类
public class LinkList implements List {

    Node head; //头指针
    Node current;//当前结点对象
    int size;//结点个数
    
    //初始化一个空链表
    public LinkList()
    {
        //初始化头结点，让头指针指向头结点。并且让当前结点对象等于头结点。
        this.head = current = new Node(null);
        this.size =0;//单向链表，初始长度为零。
    }
    
    //定位函数，实现当前操作对象的前一个结点，也就是让当前结点对象定位到要操作结点的前一个结点。
    //比如我们要在a2这个节点之前进行插入操作，那就先要把当前节点对象定位到a1这个节点，然后修改a1节点的指针域
    public void index(int index) throws Exception
    {
        if(index <-1 || index > size -1)
        {
          throw new Exception("参数错误！");    
        }
        //说明在头结点之后操作。
        if(index==-1)    //因为第一个数据元素结点的下标是0，那么头结点的下标自然就是-1了。
            return;
        current = head.next;
        int j=0;//循环变量
        while(current != null&&j<index)
        {
            current = current.next;
            j++;
        }
        
    }    
    
    @Override
    public void delete(int index) throws Exception {
        // TODO Auto-generated method stub
        //判断链表是否为空
        if(isEmpty())
        {
            throw new Exception("链表为空，无法删除！");
        }
        if(index <0 ||index >size)
        {
            throw new Exception("参数错误！");
        }
        index(index-1);//定位到要操作结点的前一个结点对象。
        current.setNext(current.next.next);
        size--;
    }

    @Override
    public Object get(int index) throws Exception {
        // TODO Auto-generated method stub
        if(index <-1 || index >size-1)
        {
            throw new Exception("参数非法！");
        }
        index(index);
        
        return current.getElement();
    }

    @Override
    public void insert(int index, Object obj) throws Exception {
        // TODO Auto-generated method stub
        if(index <0 ||index >size)
        {
            throw new Exception("参数错误！");
        }
        index(index-1);//定位到要操作结点的前一个结点对象。
        current.setNext(new Node(obj,current.next));
        size++;
    }

    @Override
    public boolean isEmpty() {
        // TODO Auto-generated method stub
        return size==0;
    }

    @Override
    public int size() {
        // TODO Auto-generated method stub
        return this.size;
    } 
    
}

测试代码

public class LinkListTest {
    public static void main(String[] args) throws Exception {
        LinkList list = new LinkList();
        for (int i = 0; i < 10; i++) {
            int temp = ((int) (Math.random() * 100)) % 100;
            list.insert(i, temp);
            System.out.print(temp + " ");
        }

        list.delete(4);
        System.out.println("\n------删除第五个元素之后-------");
        for (int i = 0; i < list.size; i++) {
            System.out.print(list.get(i) + " ");
        }
    }
}

测试代码输出

31 98 25 18 10 34 1 20 57 81 
------删除第五个元素之后-------
31 98 25 18 34 1 20 57 81 

另外一种实现，将节点类Node改为内部类

/**
 * 单向链表另外一种实现，将节点类Node改为内部类
 * 
 * @author adminjack
 *
 */
public class LinkList2 {

    private int size;
    private Node root; // 定义一个根节点

    private int foot = 0; // 操作返回数组的脚标
    private String[] retData; // 返回数组
    private boolean changeFlag = true;
    // changeFlag == true：数据被更改了，则需要重新遍历
    // changeFlag == false：数据没有更改，不需要重新遍历

    // 添加数据
    public boolean add(String data) {

        if (data == null) { // 如果添加的是一个空数据，那增加失败
            return false;
        }

        // 将数据封装为节点，目的：节点有next可以处理关系
        Node newNode = new Node(data);
        // 链表的关键就在于根节点
        if (root == null) { // 如果根节点是空的，那么新添加的节点就是根节点。(第一次调用add方法时，根节点当然是空的了)
            root = newNode;
        } else {
            root.addNode(newNode);
        }

        this.size++;
        return true;

    }

    // 方法：增加一组数据
    public boolean addAll(String data[]) { // 一组数据
        for (int x = 0; x < data.length; x++) {
            if (!this.add(data[x])) { // 只要有一次添加不成功，那就是添加失败
                return false;
            }
        }
        return true;
    }

    // 方法：删除数据
    public boolean remove(String data) { // 要删除的节点，假设每个节点的data都不一样

        if (!this.contains(data)) { // 要删除的数据不存在
            return false;
        }

        if (root != null) {
            if (root.data.equals(data)) { // 说明根节点就是需要删除的节点
                root = root.next; // 让根节点的下一个节点成为根节点，自然就把根节点顶掉了嘛（不像数组那样，要将后面的数据在内存中整体挪一位）
            } else { // 否则
                root.removeNode(data);
            }
        }
        size--;
        return true;

    }

    // 输出所有节点
    public void print() {
        if (root != null) {
            System.out.print(root.data);
            root.printNode();
            System.out.println();
        }
    }

    // 方法：获取全部数据
    public String[] toArray() {
        if (this.size == 0) {
            return null; // 没有数据
        }
        this.foot = 0; // 清零
        this.retData = new String[this.size]; // 开辟数组大小
        this.root.toArrayNode();
        return this.retData;
    }

    // 获取数据的长度
    public int size() {
        return this.size;
    }

    // 判断是否为空链表
    public boolean isEmpty() {
        return this.size == 0;
    }

    // 清空链表
    public void clear() {
        this.root = null;
        this.size = 0;
    }

    // 查询数据是否存在
    public boolean contains(String data) { // 查找数据
        // 根节点没有数据，查找的也没有数据
        if (this.root == null || data == null) {
            return false; // 不需要进行查找了
        }
        return this.root.containsNode(data); // 交给Node类处理
    }

    // 方法：根据索引取得数据
    public String get(int index) {
        if (index > this.size) { // 超过个数
            return null; // 返回null
        }
        this.foot = 0; // 操作foot来定义脚标
        return this.root.getNode(index);
    }

    // 定义一个节点内部类（假设要保存的数据类型是字符串）
    // 比较好的做法是，将Node定义为内部类，在这里面去完成增删、等功能，然后由LinkList去调用增、删的功能
    class Node {
        private String data;
        private Node next; // next表示：下一个节点对象（单链表中）

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

        // 添加节点
        public void addNode(Node newNode) {

            // 下面这段用到了递归，需要反复理解
            if (this.next == null) { // 递归的出口：如果当前节点之后没有节点，说明我可以在这个节点后面添加新节点
                this.next = newNode; // 添加新节点
            } else {
                this.next.addNode(newNode); // 向下继续判断，直到当前节点之后没有节点为止
            }
        }

        // 判断节点是否存在
        public boolean containsNode(String data) { // 查找数据
            if (data.equals(this.data)) { // 与当前节点数据吻合
                return true;
            } else { // 与当前节点数据不吻合
                if (this.next != null) { // 还有下一个节点
                    return this.next.containsNode(data);
                } else { // 没有后续节点
                    return false; // 查找不到
                }
            }
        }

        // 删除节点
        public void removeNode(String data) {
            if (this.next != null) {
                if (this.next.data.equals(data)) {
                    this.next = this.next.next;
                } else {
                    this.next.removeNode(data);
                }
            }
        }

        // 输出所有节点
        public void printNode() {
            if (this.next != null) {
                System.out.print("-->" + this.next.data);
                this.next.printNode();
            }
        }

        // 获取全部数据
        public void toArrayNode() {
            LinkList2.this.retData[LinkList2.this.foot++] = this.data;
            if (this.next != null) {
                this.next.toArrayNode();
            }
        }

        // 根据索引位置获取数据
        public String getNode(int index) {
            if (LinkList2.this.foot++ == index) { // 当前索引为查找数值
                return this.data;
            } else {
                return this.next.getNode(index);
            }
        }

    }
}