LinkedList源码解析及自定义LinkedList

blob.png

一、源码解析

    1、 LinkedList类定义。

public class LinkedList<E>  extends AbstractSequentialList<E>  implements List<E>, Deque<E>, Cloneable, 
java.io.Serializable

   LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。

   LinkedList 实现 List 接口,能对它进行队列操作。

   LinkedList 实现 Deque 接口,即能将LinkedList当作双端队列使用。

   LinkedList 实现了Cloneable接口,即覆盖了函数clone(),能克隆。(浅度复制)

   LinkedList 实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。

   LinkedList 是非同步的。

2、LinkedList数据结构原理

    LinkedList底层的数据结构是基于双向循环链表的,且头结点中不存放数据,如下:  

    既然是双向链表,那么必定存在一种数据结构——我们可以称之为节点,节点实例保存业务数据,前一个节点的位置信息和后一个节点位置信息,如下图所示:

 

 3、私有属性

 LinkedList中之定义了3个属性:

1.      transient int size = 0;   
2.    /** 
3.     * Pointer to first node. 
4.     * Invariant: (first == null && last == null) || 
5.     *            (first.prev == null && first.item != null) 
6.     */  
7.    transient Node<E> first;  
8.    /** 
9.     * Pointer to last node. 
10.     * Invariant: (first == null && last == null) || 
11.     *   (last.next == null && last.item != null) 
12.     */  
13.    transient Node<E> last;

额外补充:

    java 的transient关键字为我们提供了便利,你只需要实现Serilizable接口,将不需要序列化的属性前添加关键字transient,序列化对象的时候,这个属性就不会序列化到指定的目的地中。 详细分析查看

    transient关键字详细分析

    fist是双向链表的头节点,last是链表尾节点,它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量: previous, next, element。其中,previous是该节点的上一个节点,next是该节点的下一个节点,element是该节点所包含的值。size是双向链表中节点实例的个数。

   首先来了解节点类Node类的代码。

1.private static class Node<E> {  
2.        E item;  //当前对象信息
3.        Node<E> next;  //下一个节点
4.        Node<E> prev;  //上一个节点
5.        Node(Node<E> prev, E element, Node<E> next) {  
6.            this.item = element;  
7.            this.next = next;  
8.            this.prev = prev;  
9.        }  
10.    }

  4、构造方法

     LinkedList提供了两个构造方法。第一个构造方法不接受参数,将first实例的previous和next全部指向自身实例(注意,这个是一个双向循环链表,如果不是循环链表,空链表的情况应该是节点的前一节点和后一节点均为null),这样整个链表其实就只有一个节点,用于表示一个空的链表。执行完构造函数后,header实例自身形成一个闭环;

   第二个构造方法接收一个Collection参数c,调用第一个构造方法构造一个空的链表,之后通过addAll将c中的元素全部添加到链表中。

1.public boolean addAll(int index, Collection<? extends E> c) {  
2.        // 插入位置超过了链表的长度或小于0,报IndexOutOfBoundsException异常  
3.        checkPositionIndex(index);  
4.        Object[] a = c.toArray();  
5.        int numNew = a.length;  
6.         // 若需要插入的节点个数为0则返回false,表示没有插入元素  
7.        if (numNew == 0)  
8.            return false;  
9.       // 保存index处的节点。插入位置如果是size,则在头结点前面插入,否则在获取index处的节点插入  
10.        // 获取前一个节点,插入时需要修改这个节点的next引用  
11.        Node<E> pred, succ;  
12.        if (index == size) {  
13.            succ = null;  
14.            pred = last;  
15.        } else {  
16.            succ = node(index);  
17.            pred = succ.prev;  
18.        }  
19.       // 按顺序将a数组中的第一个元素插入到index处,将之后的元素插在这个元素后面  
20.        for (Object o : a) {  
21.            @SuppressWarnings("unchecked") E e = (E) o;  
22.            // 结合Node的构造方法,这条语句是插入操作,相当于C语言中链表中插入节点并修改指针  
23.            Node<E> newNode = new Node<>(pred, e, null);  
24.            if (pred == null)  
25.                first = newNode;  
26.            else  
27.                pred.next = newNode; // 插入节点后将前一节点的next指向当前节点,相当于修改前一节点的next指针  
28.            pred = newNode; // 相当于C语言中成功插入元素后将指针向后移动一个位置以实现循环的功能  
29.        }  
30.        if (succ == null) {  
31.            last = pred;  
32.        } else {  
33.            pred.next = succ;  
34.            succ.prev = pred;  
35.        }   
36.        size += numNew;   // 修改size  
37.        modCount++; //否则,插入对象,链表修改次数加1  
38.        return true;  
39.    }

下面说明双向链表添加元素的原理:

  添加数据:add()

1.public void add(int index, E element) {  
2.        checkPositionIndex(index);  // 插入位置超过了链表的长度或小于0,报IndexOutOfBoundsException异常  
3.        if (index == size)  
4.            linkLast(element);   // 如果相等,则从最后的节点插入  
5.        else  
6.            linkBefore(element, node(index));    // 按顺序将a数组中的第一个元素插入到index处,将之后的元素插在这个元素后面  
7.    }  
8.      /** 
9.     * e :元素数据;succ:查找到目标的顺序元素 
10.     */  
11.     void linkBefore(E e, Node<E> succ) {  
12.        // assert succ != null;  
13.        final Node<E> pred = succ.prev;  //目标元素的父节点  
14.        final Node<E> newNode = new Node<>(pred, e, succ);  //创建新的节点newNode  
15.        succ.prev = newNode; //目标元素的父节点设置成新节点  
16.        if (pred == null)  
17.            first = newNode;  //第一个节点  
18.        else  
19.            pred.next = newNode; //目标元素的父节点的下一个节点设置成新节点  
20.        size++;  
21.        modCount++;  
22.    }

6、删除数据remove(index)

1.public E remove(int index) {  
2.        checkElementIndex(index);  
3.        return unlink(node(index));  
4.    }  
5. /** 
6.     * Unlinks non-null node x. 
7.     */  
8.    E unlink(Node<E> x) {  
9.        // assert x != null;  
10.        final E element = x.item; // 保留将被移除的节点e的内容  
11.        final Node<E> next = x.next;  
12.        final Node<E> prev = x.prev;  
13.  
14.        if (prev == null) {  //判断上一个节点是否为null
15.            first = next;  //说明移除的是第一个节点需要设置first 
16.        } else {  
17.            prev.next = next;   // 将前一节点的next引用赋值为e的下一节点  
18.            x.prev = null; // 解除了e节点对前后节点的引用  
19.        }  
20.  
21.        if (next == null) {  //如果e节点的下一个节点是null
22.            last = prev;  //说明prev是最后一个节点
23.        } else {  
24.            next.prev = prev;  // 将e的下一节点的previous赋值为e的上一节点   
25.            x.next = null; // 解除了e节点对前后节点的引用  
26.        }  
27.        x.item = null;  // 将被移除的节点的内容设为null  
28.        size--;  
29.        modCount++;  
30.        return element;  
31.    }

7、删除数据remove() 这个方法默认是移除first节点 先进先出的队列形式;

    public E removeFirst() {
1.        final Node<E> f = first;  // 记录要移除的第一个节点
2.        if (f == null)   
3.            throw new NoSuchElementException();
4.        return unlinkFirst(f); 
5.    }   
6.    private E unlinkFirst(Node<E> f) {  // 
7.        // assert f == first && f != null; // 记录要移除的第一个节点
8.        final E element = f.item; // 保留将被移除的节点e的内容 
9.        final Node<E> next = f.next; 
10.        f.item = null; // 把要移除的节点的内容置空
11.        f.next = null; // help GC // 解除了f节点对前后节点的引用
12.        first = next; // 将f节点的下一个设置第一个节点
13.        if (next == null) 
14.            last = null; 
15.        else 
16.            next.prev = null; // 第一个节点的prev引用解除
17.        size--; 
18.        modCount++; 
19.        return element; 
20.    }

7、数据获取get()

   Get(int)方法的实现在remove(int)中已经涉及过了。首先判断位置信息是否合法(大于等于0,小于当前LinkedList实例的Size),然后遍历到具体位置,获得节点的业务数据(element)并返回。

注意:为了提高效率,需要根据获取的位置判断是从头还是从尾开始遍历。

1./** 
2.     * // 获取双向链表中指定位置的节点   
3.     */  
4.    Node<E> node(int index) {  
5.        // assert isElementIndex(index);  
6.       // 获取index处的节点。      
7.        // 若index < 双向链表长度的1/2,则从前先后查找;      
8.        // 否则,从后向前查找。     
9.        if (index < (size >> 1)) {  
10.            Node<E> x = first;  
11.            for (int i = 0; i < index; i++)  
12.                x = x.next;  
13.            return x;  
14.        } else {  
15.            Node<E> x = last;  
16.            for (int i = size - 1; i > index; i--)  
17.                x = x.prev;  
18.            return x;  
19.        }  
20.    }

上述只是简单的代码分析,要深入可以详细查看JDK源码;

下面自定义LinkedList,便于更好的理解LinkedList内部数据结构:

1.public class CustomLinkeList<E> {  
2.      
3.    private transient int size;  
4.      
5.    private  transient Node<E> firstNode;  
6.      
7.    private transient Node<E> last;  
8.      
9.    public CustomLinkeList() {  
10.        super();  
11.    }  
12.      
13.    public void add(E element){  
14.        Node<E> node=null;  
15.        if(firstNode==null){  //没有值  
16.            node=new Node<E>(element, null, null);  
17.            firstNode=node;  
18.            last=node;  
19.        }else{  
20.            node=new Node<E>(element, last, null);  
21.            last.next=node;  
22.            last=node;  
23.        }  
24.        size++;  
25.    }  
26.      
27.    public void add(int index,E element){  
28.        rangeCheck(index);  
29.        //查找到需要插入的Node位置  
30.        Node<E> temp=findNode(index);  
31.        if(temp!=null){  
32.            Node<E> up = temp.prev;  
33.            Node<E> newNode = new Node<E>(element,up, temp);  
34.            up.next=newNode;  
35.            temp.prev=newNode;  
36.            size++;  
37.        }  
38.    }  
39.      
40.    public void remove(int index){  
41.        rangeCheck(index);  
42.        //查找到需要插入的Node位置  
43.        Node<E> temp=findNode(index);  
44.        if(temp!=null){  
45.            Node<E> up = temp.prev;  
46.            Node<E> dowm = temp.next;  
47.            up.next=dowm;  
48.            dowm.prev=up;  
49.            size--;  
50.        }  
51.    }  
52.      
53.    private Node<E> findNode(int index) {  
54.        Node<E> temp=null;  
55.        if(firstNode!=null){  
56.            int _point=size>>1 ;//二分查找  
57.            if(index<_point){ //往前查找  
58.                temp = firstNode;  
59.                for (int i = 0; i < index; i++) {  
60.                    temp = temp.next;  
61.                }  
62.            }else{  
63.                temp=last;  
64.                for (int i = size-1; i > index; i--) {  
65.                    temp = temp.prev;  
66.                }  
67.            }  
68.        }  
69.        return temp;  
70.    }  
71.  
72.    private void rangeCheck(int index){  
73.        if(index<0 || index>=size){  
74.            try {  
75.                throw new Exception("越界");  
76.            } catch (Exception e) {  
77.                e.printStackTrace();  
78.            }  
79.        }  
80.    }  
81.      
82.      
83.    /** 
84.     * 查看元素 
85.     * @param index 
86.     * @return 
87.     */  
88.    public Object get(int index){  
89.        rangeCheck(index);  
90.        //查找到需要插入的Node位置  
91.        Node<E> temp=findNode(index);  
92.        if(temp!=null){  
93.            return temp.element;  
94.        }  
95.        return null;  
96.    }  
97.      
98.      
99.    public int size(){  
100.        return size;  
101.    }  
102.  
103.  
104.  
105.    class  Node<E>{  
106.          
107.        private E element;  
108.          
109.        private  Node<E> prev;  
110.          
111.        private Node<E> next;  
112.  
113.        public Node(E element, Node<E> prev, Node<E> next) {  
114.            super();  
115.            this.element = element;  
116.            this.prev = prev;  
117.            this.next = next;  
118.        }  
119.          
120.    }  
121.      
122.    public static void main(String[] args) {  
123.        CustomLinkeList<String> list=new CustomLinkeList<String>();  
124.        list.add("aaa");  
125.        list.add("bbb");  
126.        list.add(1,"BBBB");  
127.        list.add("ccc");  
128.        list.add("ddd");  
129.        list.add("eee");  
130.        //list.remove(1);  
131.        System.out.println(list.get(1));   
132.        System.out.println(list.size());  
133.          
134.    }  
135.      
136.}

  原文-个人CSDN

   在阅览的过程中如果遇到没有代码的样式,建议使用chrome浏览器,便于更好的阅读文章代码结构及内容

发表评论