LinkList列表#

LinkList：链接表，任何数据都有自己的地址。

@以下转载自http://blog.csdn.net/hantiannan/article/details/5447567

------------------------------------------------------------------------------------------------------

数据插入 :比如在i节点插入一个新数据

   ArrayList:循环到i节点,插入一个新数据,然后把i节点后面的所有的数据的index加1. ->操作多

   LinkedList:循环到i节点,把前一个节点的后续链接到新数据,然后把新数据链接到后一个数据就可以了.  ->操作少

   结论:平均效率LinkedList要好.

数据删除 :比如删除i节点数据

   ArrayList:循环到i节点,然后把i节点后面的所有的数据的index减1. ->操作多

   LinkedList:循环到i节点,把前一个节点的后续链接到i节点的后一个数据就可以了.  ->操作少

   结论:平均效率LinkedList要好.

数据查询 :比如查询i节点数据

   ArrayList:循环到i节点. ->操作少

   LinkedList:循环到i节点.  ->操作少,但由于每个数据的地址不一样,查询比如 ArrayList慢.

   结论:平均效率 ArrayList要好.

数据更新 :比如更新i节点数据

   ArrayList:循环到i节点,把数据更新. ->操作少

   LinkedList:循环到i节点,把前数据更新.  ->操作少,但由于查询速度没有 ArrayList好,所有效率没有 ArrayList好.

   结论:平均效率ArrayList要好.

------------------------------------------------------------------------------------------------------

 

增删查改API

    public void test1(){
        LinkedList<Integer> ll = new LinkedList<>();
        ll.add(1);ll.add(2);ll.add(3);
        
        System.out.println("原始列表:"+ll);
        System.out.println("------------------");
        //插入方法多(add方法插入返回void,offer方法返回boolean可以判断是否插入成功.)
        ll.addLast(0);
        System.out.println("1.头插入:"+ll);
        System.out.println("2.尾插入:"+ll.offer(null)+ll);
        ll.push(4);
        System.out.println("3.push插入:"+ll);//默认头插入
        ll.pop();
        System.out.println("4.pop弹出"+ll);//默认头弹出
        ll.remove();
        System.out.println("5.remove移除:"+ll);//默认头移除
        
        //API里面说getLast是null会报exception但是....
        System.out.println("6.尾查询:"+ll.getLast());
        System.out.println("7.尾查询"+ll.peekLast());
            
    }

结果:

3种迭代器比较

    public void test2(){
        LinkedList<Integer> ll = new LinkedList<>();
        ll.add(10);ll.add(2);ll.add(3);
        
        System.out.println("原始列表:"+ll);
        System.out.println("------------------");
        System.out.println("顺序输出:");
        for (Iterator<Integer> iterator = ll.iterator(); iterator.hasNext();) {
            Integer integer = (Integer) iterator.next();
            System.out.println(integer);
        }
        System.out.println("逆序输出descendingIterator()");
        for (Iterator<Integer> iterator = ll.descendingIterator(); iterator.hasNext();) {
            Integer integer = (Integer) iterator.next();
            System.out.println(integer);
        }
//        System.out.println("列表迭代器(按适当顺序)listIterator()");
//        for (ListIterator<Integer> iterator = ll.listIterator(); iterator.hasNext();) {
//            System.out.println("输出当前Index:"+(iterator.nextIndex()-1));
//            Integer integer = (Integer) iterator.next();//索引+1
//            System.out.println(".next()后的index值为:"+(iterator.nextIndex()-1)+"的时候,integer的值:"+integer);
//            System.out.println("原来的ll"+ll);
//            iterator.set(1);iterator.add(5);
//            System.out.println("后来的ll"+ll);
//            System.out.println("最后的index:"+(iterator.nextIndex()-1));
//            System.out.println();
//        }
    }

输出结果（正逆迭代器）

还有LinkList独有迭代器（基本可以了解到每一步index是怎么移动的，还有就是这个迭代器比普通Intertor高级的地方在于能增删数据，下面也验证了，慢慢看能看懂的）

    public void test2(){
        LinkedList<Integer> ll = new LinkedList<>();
        ll.add(10);ll.add(2);ll.add(3);
        
        System.out.println("原始列表:"+ll);
        System.out.println("------------------");
//        System.out.println("顺序输出:");
//        for (Iterator<Integer> iterator = ll.iterator(); iterator.hasNext();) {
//            Integer integer = (Integer) iterator.next();
//            System.out.println(integer);
//        }
//        System.out.println("逆序输出descendingIterator()");
//        for (Iterator<Integer> iterator = ll.descendingIterator(); iterator.hasNext();) {
//            Integer integer = (Integer) iterator.next();
//            System.out.println(integer);
//        }
        System.out.println("列表迭代器(按适当顺序)listIterator()");
        for (ListIterator<Integer> iterator = ll.listIterator(); iterator.hasNext();) {
            System.out.println("输出当前Index:"+(iterator.nextIndex()-1));
            Integer integer = (Integer) iterator.next();//索引+1
            System.out.println(".next()后的index值为:"+(iterator.nextIndex()-1)+"的时候,integer的值:"+integer);
            System.out.println("原来的ll"+ll);
            iterator.set(1);iterator.add(5);
            System.out.println("后来的ll"+ll);
            System.out.println("最后的index:"+(iterator.nextIndex()-1));
            System.out.println();
        }
    }

Ending... ...