【无标题】

package com.myfunnel.dynamic.linked;


public class linkedList {
    
    Node first;
    
    private int size;

    public linkedList() {
        first = null;
        size = 0;
    }

    
    private static class Node {
        
        E element;
        
        Node next;

        public Node(E element, Node next) {
            this.element = element;
            this.next = next;
        }

        public Node(E element) {
            this(element, null);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "element=" + element +
                    ", next=" + next +
                    '}';
        }
    }

    
    public void addFirst(E element) {
        //创建新的节点存放数据
        Node node = new Node(element);
        //将已经存在的第一个节点指向当前节点的下个节点
        node.next = first;
        //同时将当前节点当作头节点
        first = node;
        //链表的长度增加
        size++;
    }

    
    public void addLast(E element) {
        add(element, size);
    }

    
    public void add(E element, int index) {
        if (index < 0 || index >= size) {
            System.out.println("索引不在链表范围内！");
        }
        //插入第一个位置
        if (index == 0) {
            addFirst(element);
            return;
        }
        //将头节点当作上一个节点
        Node prevNode = first;
        //找到指定位置的节点
        for (int i = 0; i < index - 1; i++) {
            prevNode = prevNode.next;
        }
        //创建当前节点
        Node node = new Node(element);
        //将新节点的next指向上个节点的next
        node.next = prevNode.next;
        //新节点指向上个节点的next
        prevNode.next = node;
        size++;
    }

    
    public boolean add(E element) {
        addLast(element);
        return true;
    }

    
    public boolean remove(Object element) {
        if (first == null) {
            System.out.println("没有元素可以移除！");
        }
        if (element != null) {
            for (Node x = first; x != null; x = x.next) {
                unlink(x);
            }
        }
        return true;
    }

    
    public E remove(int index) {
        if (index < 0 || index >= size) {
            System.out.println("索引不在链表范围内！");
        }
        Node node = node(index);
        return unlink(node);
    }

    
    public E set(int index, E element) {
        if (index < 0 || index >= size) {
            System.out.println("索引不在链表范围内！");
        }
        Node x = node(index);
        E oldItem = x.element;
        x.element = element;
        return oldItem;
    }

    
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

    private int indexOf(Object o) {
        int index = 0;
        for (Node x = first; x != null; x = x.next) {
            if (o.equals(x.element)) {
                return index;
            }
            index++;
        }

        return -1;
    }

    
    public E removeFirst() {
        Node x = first;
        if (x == null) {
            System.out.println("没有参数可以移除！");
        }
        final E element = x.element;
        final Node next = x.next;
        x.element = null;
        x.next = null;
        first = next;
        size--;
        return element;
    }

    
    public E removeLast() {
        Node x = first;
        if (x == null) {
            System.out.println("没有参数可以移除！");
        }

        Node node = node(size - 1);
        E element = node.element;
        node.element = null;
        return element;
    }

    
    public E get(int index) {
        Node x = first;
        if (x == null) {
            System.out.println("没有参数可以获取！");
        }
        Node node = node(index);
        return node.element;
    }

    
    public E getFirst() {
        Node x = first;
        if (x == null) {
            System.out.println("没有参数可以获取！");
        }
        return x.element;
    }

    
    public E getLast() {
        Node x = first;
        if (x == null) {
            System.out.println("没有参数可以获取！");
        }
        return node(size - 1).element;
    }


    
    public void clear() {
        for (Node x = first; x != null; ) {
            Node next = x.next;
            x.element = null;
            x.next = null;
            x = next;
        }
        first = null;
        size = 0;
    }

    
    private Node node(int index) {
        //如果index小于链表长度的一半,则从头找
        Node x = first;
        for (int i = 0; i < index; i++) {
            x = x.next;
        }
        return x;
    }

    
    public int size() {
        return size;
    }


    
    private E unlink(Node x) {
        final E element = x.element;
        if (x == first && element.equals(x.element)) {
            first = x.next;
            first.element = null;
            size--;
        } else {
            if (element.equals(x.element)) {
                x = x.next;
                x.element = null;
                size--;
            }
        }
        return element;
    }

    @Override
    public String toString() {
        return "linkedList{" +
                "first=" + first +
                ", size=" + size +
                '}';
    }
}

package com.myfunnel.dynamic;


import com.myfunnel.dynamic.linked.linkedList;


public class TestlinkedList {
    public static void main(String[] args){
        linkedList linkedList = new linkedList();
        linkedList.add("a");
        linkedList.add("b");
        linkedList.add("c");
        linkedList.add("d");
        System.out.println(linkedList);

        linkedList.addFirst("222");
        System.out.println(linkedList);

        linkedList.addLast("666");
        System.out.println(linkedList);

        linkedList.add("88888",3);
        System.out.println(linkedList);

        System.out.println(linkedList.size());

        System.out.println(linkedList.get(3));

        System.out.println(linkedList.getFirst());

//        System.out.println(linkedList.removeFirst());
//        System.out.println(linkedList.removeLast());
//        System.out.println(linkedList.remove(6));
        System.out.println(linkedList.getLast());
//        linkedList.clear();
//        System.out.println("--------------》"+linkedList);

        System.out.println(linkedList.contains("888i88"));

    }

}