java双向链表操作

在这里插入图片描述
有add(v)
add(i.v)
remove(i)
get(i)

public class TowWayLinkList <T> implements Iterable<T>{
    /**
     * 双向链表的节点
     */
    private class Node<U>{
        //当前节点的值
        private U item;
        //当前节点上一个值
        private Node<U> pre;
        //当前节点下一个值
        private Node<U> next;

        public Node(Node<U> pre,U item, Node<U> next){
            this.item = item;
            this.pre = pre;
            this.next = next;
        }
    }

    //第一个节点
    private Node<T> first;
    //最后一个节点
    private Node<T> last;
    //链表长度
    private int N;

    public TowWayLinkList(){
        //初始化节点
        N=0;
    }

    /**
     * 添加数据
     */
    public void add(T v){
        Node<T> l = last;
        //创建新的节点，把节点指向前一个节点
        Node<T> newNode = new Node<>(l, v, null);
        last = newNode;
        //判断最后一个节点是否为空
        if(l == null){
            first = newNode;
        }else{
            l.next = newNode;
        }
        N++;
    }

    /**
     * 添加操作
     * @param i
     * @param v
     */
    public void add(int i,T v){
        if(i <0|| i >N){
            throw new RuntimeException("索引超限");
        }
        //判断大小
        //如果放的位置
        if(i == N){
            //直接放在最后
            add(v);
        }else{
            //原节点
            Node<T> current = getNode(i);
            //原节点的上一个节点
            Node<T> pre = current.pre;

            Node<T> nowData = new Node<>(pre, v, current);
            if(pre == null){
                first = nowData;
            }else{
                current.pre = nowData;
                pre.next = nowData;
            }
        }
        N++;
    }

    public T get(int i){
        return getNode(i).item;
    }

    private Node<T> getNode(int i){
        if(i < 0||i >= N){
            throw new RuntimeException("索引超限");
        }
        //得到信息
        if(i < (N >> 1)){
            Node<T> x = first;
            for (int j = 0; j < i; j++) {
                x = x.next;
            }
            return x;
        }else{
            Node<T> x = last;
            for (int j = N-1; j > i; j--) {
                x = x.pre;
            }
            return x;
        }
    }

    /**
     * 移出数据
     */
    public void remove(int i){
        if(i < 0||i> N){
            throw new RuntimeException("索引超限");
        }
        if(i == N-1){
            //干掉最后一个
            Node<T> a = last;
            //前一个
            Node<T> pre = a.pre;
            pre.next = null;
            last = pre;
        }else if(i == 0){
            Node<T> a = first;
            Node<T> next = a.next;
            next.pre = null;
            first = next;
        }else{
            //中间
            Node<T> a = getNode(i);
            Node<T> pre = a.pre;
            Node<T> next = a.next;
            pre.next = next;
            next.pre = pre;
        }
        N--;
    }

    public static void main(String[] args) {
        LinkedList lis1 = new LinkedList();
        lis1.add(0, "2");
        lis1.get(0);
//        System.out.println(16 >> 1);
        TowWayLinkList<String> list = new TowWayLinkList<>();
        list.add("111");
        list.add("2222");
        list.add("222232");
        list.add("2222q111");
        list.add("212121");
//        list.add(4,"22222");  //索引超限
//        list.add(3, "333333333");
//        list.add(2,"22222222222");
//        list.add(0, "0000000"); //第一个位置
//        list.remove(5);//索引超限
//        list.remove(4);
//        list.remove(0);
//        list.remove(2);
//        list.remove(0);
//        System.out.println(list.get(0));
        System.out.println("-------------");

        Iterator it = list.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }
    }


    @Override
    public Iterator<T> iterator() {
        return new LIterator();
    }

    /**
     * 迭代器代码
     */
    private class LIterator implements Iterator<T>{
        private Node<T> next;
        private Node<T> lastReturned;
        private int nextInt;

        public LIterator(){
            nextInt = 0;
            this.next = first;
        }
        @Override
        public boolean hasNext() {
            return nextInt < N;
        }
        @Override
        public T next() {
            lastReturned = next;
            //并把下一个数据数据传给next
            next = next.next;
            nextInt++;
            //返回当前数据
            return (T) lastReturned.item;
        }
    }

}