链表

链表的本质是一个动态数组。

链表的基本定义

在实际开发中对象数组非常实用，但是传统的对象数组长度是固定的，正因为如此，传统的数组应用非常有限。如果要想进行灵活的数据保存，需要自己来实现结构。
传统的对象数组采用索引控制，如果要想实现内容的动态维护难度太高。对于随时可能变化的数据使用不合理。
所谓链表的实质性本质是利用引用的逻辑关系来实现类似数组的数据处理操作，实现与数组类似的功能。

链表全部代码

package com.Link;
interface Link<E>{
    void add(E e);
    void show();
    int getSize();
    boolean isEmpty();
    Object[] toArray();
    E get(int index);//获取指定索引数据
    void set(int index,E data);
    boolean contains(E data);
    void remove(E data);
    void clean();
}
class LinkImpl<E> implements Link<E>{
    private class Node{
        private E data;
        private Node next;
        public Node(E e) {
            this.data = e;
        }
        void addNode(Node newNode) {
            if(this.next == null) {
                this.next = newNode;
            }
            else {
                this.next.addNode(newNode);
            }
        }
        void showNode() {
            System.out.println(this.data);
        }
        public void toArrayNode() {
            LinkImpl.this.returnData[LinkImpl.this.foot++] = this.data;
            if(this.next!=null) {
                this.next.toArrayNode();
            }
        }
        E getNode(int index) {
            if(LinkImpl.this.foot ++ == index) {//索引相同
                return this.data;
            }
            else {
                return this.next.getNode(index);
            }
        }
        void setNode(int index,E data) {
            if(LinkImpl.this.foot ++ == index) {//索引相同
                this.data = data;
            }
            else {
                this.next.setNode(index,data);
            }
        }
        boolean containsNode(E data) {
            if(this.data.equals(data)) {
                return true;
            }else {
                if(this.next == null) {
                    return false;
                }
                else {
                    return this.next.containsNode(data);
                }
            }
        }
        void removeNode(Node previous,E data) {//previous是上一个节点
            if(this.data.equals(data)) {
                previous.next = this.next;
            }else {
                if(this.next != null) {
                    this.next.removeNode(this, data);
                }
            }
        }
    }
    private Node root = null;
    private int count = 0;
    private int foot = 0;
    private Object[] returnData;
    @Override
    public void add(E e) {
        // TODO Auto-generated method stub
        if(e == null) {
            return;
        }
        else {
            Node newNode = new Node(e);
            if(this.root == null) {
                this.root = newNode;
            }
            else {
                root.addNode(newNode);
            }
            this.count++;
        }
    }
    @Override
    public void show() {
        // TODO Auto-generated method stub
        Node tmp = root;
        while(tmp != null) {
            tmp.showNode();
            tmp = tmp.next;
        }
    }
    @Override
    public int getSize() {
        // TODO Auto-generated method stub
        return this.count;
    }
    @Override
    public boolean isEmpty() {
        // TODO Auto-generated method stub
        return this.count == 0;
        // return this.root == null;
    }
    @Override
    public Object[] toArray() {
        // TODO Auto-generated method stub
        if(this.isEmpty()) {
            return null;    
        }
        else {
            this.returnData = new Object[this.count];
            this.root.toArrayNode();
            return this.returnData;
        }
    }
    @Override
    public E get(int index) {
        // TODO Auto-generated method stub
        if(index >= count) {
            return null;
        }
        else {
            this.foot = 0;
            return this.root.getNode(index);
        }
    }
    @Override
    public void set(int index, E data) {
        // TODO Auto-generated method stub
        if(index >= count) {
            return;
        }
        else {
            this.foot = 0;
            this.root.setNode(index, data);
        }
    }
    @Override
    public boolean contains(E data) {
        // TODO Auto-generated method stub
        return this.root.containsNode(data);
    }
    @Override
    public void remove(E data) {
        // TODO Auto-generated method stub
        if(this.contains(data)) {
            if(this.root.data.equals(data)) {
                this.root = this.root.next;//根节点和根节点的下一个变为同一个对象。
            }
            else {
                this.root.next.removeNode(this.root, data);
            }
            count--;
        }
    }
    @Override
    public void clean() {
        // TODO Auto-generated method stub
        this.count = 0;
        this.root = null;
    }
}
public class Test {
    public static void main(String[] args) {
        LinkImpl<String> all = new LinkImpl<String>();
        System.out.println(all.isEmpty());
        all.add("111");
        all.add("222");
        all.add("333");
        all.show();
        System.out.println(all.getSize());
        System.out.println(all.isEmpty());
        Object res[] = all.toArray();
        for(Object obj:res) {
            System.out.println(obj.toString());
        }
        System.out.println(all.get(2));
        all.set(2, "444");
        System.out.println(all.get(2));
        System.out.println(all.contains("111"));
        System.out.println(all.contains("199"));
        all.remove("111");
        all.show();
        all.clean();
        all.show();
    }
}