一、LinkedList实现类的使用

重复的不再写

    增加 	 addFirst(E e) 列表首位添加元素
    		 addLast(E e) 列表尾部添加元素
        	 offer(E e) 列表尾部添加元素
      	     offerLast(E e)  列表末尾添加元素
       	     offerFirst(E e)   列表首尾添加元素
       	     
    删除      poll()   列表首部弹出元素
             pollFirst()  列表首部弹出元素
             pollLast()   列表尾部弹出元素
                                   ---》JDK1.6以后新出的方法，提高了代码的健壮性
             removeFirst()  列表首部弹出元素
             removeLast() 列表尾部弹出元素
             
    修改
    
    查看     element() 查看首部元素
             getFirst()  获取第一个元素
             getLast() 获取最后一个元素
             indexOf(Object o)  查看元素第一次出现的位置
             lastIndexOf(Object o)  查看元素最后一次出现的位置
             peek()        查看首部元素
             peekFirst()   查看首部元素
             peekLast()    查看尾部元素
    判断
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

为什么这么多相似方法呢？

1.1 removeFirst ( )

获取头结点，若为空，则报错 NoSuchElementException 没有这个元素异常

    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1.2 pollFirst ( )

（JDK1.6开始，提高了代码的健壮性）
获取头结点，若为null，则返回null，否则返回头结点

    public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
   private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;
        if (next == null)
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.3 集合的遍历

        //集合的遍历：
        System.out.println("---------------------");
        //普通for循环：
        for(int i = 0;i<list.size();i++){
            System.out.println(list.get(i));
        }
        System.out.println("---------------------");
        //增强for：
        for(String s:list){
            System.out.println(s);
        }
        System.out.println("---------------------");
        //迭代器：
        /*Iterator it = list.iterator();
        while(it.hasNext()){
            System.out.println(it.next());
        }*/
        //下面这种方式好，节省内存
        //内存节省在 it 的生命周期上，一个是for循环结束it结束，一个是整个方法结束，it结束
        for(Iterator<String> it = list.iterator();it.hasNext();){
            System.out.println(it.next());
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

二、LinkedList简要底层原理图

三、模拟LinkedList源码

public class Node{
	Object obj;
	Node pre;
	Node next;
  // get/set 省略
}

public class MyLinkedList {
    //链中一定有一个首节点：
    Node first;
    //链中一定有一个尾节点：
    Node last;
    //计数器：
    int count = 0;
    //提供一个构造器：
    public MyLinkedList(){
    }
    //添加元素方法：
    public void add(Object o){
        if(first == null){//证明你添加的元素是第一个节点：
            //将添加的元素封装为一个Node对象：
            Node n = new Node();
            n.setPre(null);
            n.setObj(o);
            n.setNext(null);
            //当前链中第一个节点变为n
            first = n;
            //当前链中最后一个节点变为n
            last = n;
        }else{//证明已经不是链中第一个节点了
            //将添加的元素封装为一个Node对象：
            Node n = new Node();
            n.setPre(last);//n的上一个节点一定是当前链中的最后一个节点last
            n.setObj(o);
            n.setNext(null);
            //当前链中的最后一个节点的下一个元素 要指向n
            last.setNext(n);
            //将最后一个节点变为n
            last = n;
        }
        //链中元素数量加1
        count++;
    }
    //得到集合中元素的数量：
    public int getSize(){
        return count;
    }
    //通过下标得到元素：
    public Object get(int index){
        //获取链表的头元素：
        Node n = first;
        //一路next得到想要的元素
        for(int i=0;i<index;i++){
            n = n.getNext();
        }
        return n.getObj();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

四、LinkedList源码解析（JDK1.7和JDK1.8是一样的）

底层是双向链表

    private static class Node<E> {
        E item; //当前元素
        Node<E> next; //下一个元素地址
        Node<E> prev; //上一个元素地址

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element; 
            this.next = next;
            this.prev = prev;
        }
    }
    
     transient int size = 0;  //链表有效元素个数
     transient Node<E> first; //链表头结点
     transient Node<E> last;  //链表尾结点
     public LinkedList() { }

	 public boolean add(E e) {
        linkLast(e);
        return true;
    }
    //尾部添加元素
    void linkLast(E e) {
    //获取尾结点
        final Node<E> l = last;
        //创建新的尾结点
        final Node<E> newNode = new Node<>(l, e, null);
        //尾结点后移
        last = newNode;
        //如果之前没有尾结点，则当前结点则为头结点
        if (l == null)
            first = newNode;
        else
        //如果之前有尾结点，则之前尾结点的下一个结点为当前尾结点
            l.next = newNode;
        //有效元素数量++
        size++;
        //操作数++
        modCount++;
    }
    
    public int size() {
        return size;
    }
    //细节对半找
    Node<E> node(int index) {
          if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58