链表

在开发中，数组是数据结构中的重要部分，一般表征线性表，它的优点是易访问，但是缺点是增加删除数据较慢，要解决这个缺陷，可以使用数据结构中的链表。

interface ILinkedList<E> {
    public void Add(E e);

    public int getLenth();

    public boolean isEmpty();

    public Object[] toArray();

    public E get(int index);

    public boolean set(int index, E data);

    public boolean contains(E data);

    public boolean delete(E data);

    public void clearAll();

    public void printAll();
}

class LinkImpl<E> implements ILinkedList<E> {
    private Node<E> linkStarterNode;
    private int count;
    private Object[] returnArrData;
    private int arrayIndex = 0;

    private class Node<E> {
        private E data;
        private Node<E> next;

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

        public void addNode(Node<E> newNode) {
            if (this.next == null) {
                this.next = newNode;
            } else {
                this.next.addNode(newNode);
            }
        }

        public void toArrayNode() {
            LinkImpl.this.returnArrData[LinkImpl.this.arrayIndex++] = this.data;
            if (this.next != null) {
                this.next.toArrayNode();
            }

        }

        public E getNode(int index) {
            if (LinkImpl.this.arrayIndex++ == index) {
                return this.data;
            } else {
                return this.next.getNode(index);
            }
        }

        public boolean setData(int index, E data) {
            if (LinkImpl.this.arrayIndex++ == index) {
                this.data = data;
                return true;
            } else {
                return this.next.setData(index, data);
            }
        }

        public boolean contains(E data) {
            if (this.data.equals(data))
                return true;
            if (this.next != null)
                return this.next.contains(data);
            return false;
        }

        public boolean delete(E data) {
            if (this.next != null)
                if (this.next.data.equals(data)) {
                    this.next = this.next.next;
                    LinkImpl.this.count--;
                    return true;
                } else {
                    return this.next.delete(data);
                }
            return false;

        }

        public void PrintNode() {
            System.out.println(this.data);
            if (this.next != null) {
                this.next.PrintNode();
            }
        }
    }

    @Override
    public void Add(E e) {
        this.count++;
        // TODO Auto-generated method stub
        if (e == null) {
            return;
        }

        Node<E> newNode = new Node<E>(e);
        if (this.linkStarterNode == null) {
            this.linkStarterNode = newNode;
        } else {
            this.linkStarterNode.addNode(newNode);
        }

    }

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

    }

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

    @Override
    public Object[] toArray() {
        // TODO Auto-generated method stub
        if (linkStarterNode == null) {
            return null;
        }

        arrayIndex = 0;
        returnArrData = new Object[this.count];
        this.linkStarterNode.toArrayNode();
        return returnArrData;

    }

    @Override
    public E get(int index) {
        // TODO Auto-generated method stub
        if (index >= this.count) {
            throw new ArrayIndexOutOfBoundsException("超出数据范围！");
        }
        this.arrayIndex = 0;
        return this.linkStarterNode.getNode(index);
    }

    @Override
    public boolean set(int index, E data) {
        if (index >= this.count) {
            throw new ArrayIndexOutOfBoundsException("超出数据范围！");
        }
        this.arrayIndex = 0;
        return this.linkStarterNode.setData(index, data);
    }

    @Override
    public boolean contains(E data) {
        if (this.linkStarterNode == null)
            return false;
        return this.linkStarterNode.contains(data);
    }

    @Override
    public boolean delete(E data) {
        // TODO Auto-generated method stub
        if (this.linkStarterNode == null)
            return false;
        if (this.linkStarterNode.data.equals(data)) {
            this.linkStarterNode = this.linkStarterNode.next;
            this.count--;
        }
        return this.linkStarterNode.delete(data);
    }

    @Override
    public void clearAll() {
        // TODO Auto-generated method stub
        this.count = 0;
        this.linkStarterNode = null;

    }

    @Override
    public void printAll() {
        // TODO Auto-generated method stub
        if (this.linkStarterNode == null)
            return;

        this.linkStarterNode.PrintNode();

    }
}

做下测试：

class PersonInfo {
    private String name;
    private int age;

    public PersonInfo(String n, int a) {
        this.name = n;
        this.age = a;
    }

    @Override
    public boolean equals(Object obj) {
        // TODO Auto-generated method stub
        PersonInfo target = (PersonInfo) obj;
        if (this.name == target.name && this.age == target.age) {
            return true;
        }
        return false;
    }

    @Override
    public String toString() {
        // TODO Auto-generated method stub
        return "name:" + this.name + ";age:" + age;
    }

}

public class Main {
    public static void main(String[] args) {
        LinkImpl<PersonInfo> lp = new LinkImpl<PersonInfo>();
        lp.Add(new PersonInfo("li", 22));
        lp.Add(new PersonInfo("wang", 22));
        lp.Add(new PersonInfo("zhang", 22));
        lp.Add(new PersonInfo("li", 23));
        System.out.println(lp.getLenth());
        lp.printAll();

        Object[] resultObjects = lp.toArray();
        for (Object p1 : resultObjects) {
            System.out.println("result:" + p1);
        }
        System.out.println("second element:" + lp.get(1));
        System.out.println("设置第2个元素：");
        lp.set(1, new PersonInfo("sun", 19));
        lp.printAll();

        System.out.println(lp.contains(new PersonInfo("zhang", 22)));
        System.out.println("删除元素，li 22:" + lp.delete(new PersonInfo("li", 23)));

        lp.printAll();
        System.out.println(lp.getLenth());
    }
}