Java集合：关于LinkedList类

亦凉 2024-03-17 15:07 115阅读 0赞

#### 文章目录 ####

*  一、LinkedList概念
 *  二、体系结构
 *  三、LinkedList的使用
 *   *  3.1构造函数
     *  3.2添加节点
     *  3.3删除节点
     *  3.4获取节点位置
     *  3.5更新节点的值
     *  3.6遍历链表
 *  四、源码分析

## 一、LinkedList概念 ##

**接口实现：** LinkedList类同时实现了List接口和Deque接口，说明它既可以用作List，又可以用作队列（Deque），同时还可以用于栈（Stack）。（Java官方声明不建议使用栈了）。

关于栈或队列，现在首选是ArrayDeque，它有着比LinkedList（当作栈或队列使用时）更好的性能。

**底层数据结构：** 双向链表（内部每个节点内部类Node表示，LinkedList通过first和last引用分别指向链表的第一个和最后一个元素。在这里没有所谓的哑元，当链表为空的时候first和last都指向null。）

**效率：** 随机访问效率比ArrayList要低，顺序访问的效率要比较的高。

**线程安全：** 为追求效率，LinkedList没有实现同步（synchronized），如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装。

**常用：** List集合、双端队列、栈

## 二、体系结构 ##

**源码：**

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

**继承关系：**

java.lang.Object  //顶层，所有类都继承Object类
        java.util.AbstractCollection<E> //Collection接口的骨架实现类，最小化实现了Collection接口所需要实现的工作量
            java.util.AbstractList<E>  //List接口的骨架实现类，最小化实现了List接口所需要实现的工作量
                java.util.AbstractSequentialList<E>  
                    java.util.LinkedList<E>

**实现接口：**

Serializable, //实现了该接口标示了类可以被序列化和反序列化
    Cloneable, //实现了该接口的类可以显示的调用Object.clone()方法，合法的对该类实例进行字段复制
    Iterable<E>, //迭代器
    Collection<E>, //Collection接口是所有集合类的根节点，Collection表示一种规则
    Deque<E>, //Deque定义了一个线性Collection，支持在两端插入和删除元素
    List<E>, //List是Collection的子接口，它是一个元素有序(按照插入的顺序维护元素顺序)、可重复、可以为null的集合
    Queue<E>

## 三、LinkedList的使用 ##

### 3.1构造函数 ###

LinkedList()  
    LinkedList(Collection<? extends E> c)

LinkedList没有长度的概念，所以不存在容量不足的问题，因此不需要提供初始化大小的构造方法，因此值提供了两个方法，一个是无参构造方法，初始一个LinkedList对象，和将指定的集合元素转化为LinkedList构造方法。

### 3.2添加节点 ###

addLast(E e)和add(E e)采用的是尾插法，addFirst(E e)采用的头插法。

add(int index, E element)：将指定的元素插入此列表中的指定位置（会检查指定位置是否合法）

addAll(Collection<? extends E> c)：将指定集合中的所有元素追加到此列表的末尾，此方法还有一个 addAll(int index, Collection<? extends E> c)，将集合 c 中所有元素插入到指定索引的位置。

下面是add(E e)举例分析：

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; //last指向新节点
         if (l == null) 
             first = newNode; //如果尾节点为空表示链表没有元素，新节点就是首节点
         else 
              l.next = newNode; //否则就把下一节点指向新节点（尾插法）
         size++; //节数+1
         modCount++; //和ArrayList中一样，iterator和listIterator方法返回的迭代器和列表迭代器实现使用。
    }

### 3.3删除节点 ###

remove(Object o):默认从链表的头部开始删除数据

remove(int index):删除指定位置的元素

//方法1.删除指定索引上的节点 
    public E remove(int index) {
         
        //检查索引是否正确 
        checkElementIndex(index); 
        //这里分为两步，第一通过索引定位到节点，第二删除节点 
        return unlink(node(index)); 
    } 
    //方法2.删除指定值的节点 
    public boolean remove(Object o) {
         
        //判断删除的元素是否为null 
        if (o == null) {
         
            //若是null遍历删除 
            for (Node<E> x = first; x != null; x = x.next) {
         
                if (x.item == null) {
         
                    unlink(x); 
                    return true; 
                } 
            } 
        } else {
         
            //若不是遍历删除  
            for (Node<E> x = first; x != null; x = x.next) {
         
                if (o.equals(x.item)) {
         
                    unlink(x); 
                    return true; 
                } 
            } 
        } 
        return false; 
    } 
    
    // 作用是删除x节点,返回对应的值
    E unlink(Node<E> x) {
        
            // assert x != null;
            final E element = x.item;
            final Node<E> next = x.next;
            final Node<E> prev = x.prev;
           //头节点为空设置当前元素为第一个元素
            if (prev == null) {
        
                first = next;
            } else {
        
                prev.next = next;
                x.prev = null;
            }
          //尾节点为空设置当前元素为最后一个元素
            if (next == null) {
        
                last = prev;
            } else {
        
                next.prev = prev;
                x.next = null;
            }
     
            x.item = null;    // x节点的数据域、next、prev都设置为null，方便垃圾回收
            size--;
            modCount++;
            return element;
    }

### 3.4获取节点位置 ###

public E get(int index) {
        
        checkElementIndex(index);
        return node(index).item;
    }
    
    /**
    * 相当于查找某个位置的节点（元素）
    */
    Node<E> node(int index) {
        
        // 算是一种小优化，看需要插入的位置是处于链表的前半部分还是后半部分
        // 如果是前半部分则从头部开始顺序查找插入位置的节点
        if (index < (size >> 1)) {
        //如果插入的索引在前半部分
            Node<E> x = first;//设x为头节点
            for (int i = 0; i < index; i++)//从开始节点到插入节点索引之间的所有节点向后移动一位
                x = x.next;
            return x;
        } else {
        //如果插入节点位置在后半部分
            Node<E> x = last;//将x设为最后一个节点
            for (int i = size - 1; i > index; i--)//从最后节点到插入节点的索引位置之间的所有节点向前移动一位
                x = x.prev;
            return x;
        }
        }

### 3.5更新节点的值 ###

set(int index, E element)：用来更新index节点的值，返回旧值，由于存在需要顺序遍历到第index位置，因此时间复杂度为n/2也即为n，源码如下：

public E set(int index, E element) {
        
         checkElementIndex(index);    // 检查index 位置的合法性
         Node<E> x = node(index);    // 遍历获取index位置的节点
         E oldVal = x.item;
         x.item = element;
         return oldVal;
    }

### 3.6遍历链表 ###

listIterator(int index):返回一个LinkedList的迭代器，通常我们不会直接调用此函数，一般是直接调用List的iterator()，它最终就是调用listIterator(int index)，只不过index为0而已，通过迭代器对链表进行遍历，相当于C语言里面的指针一样，指向某个元素顺序遍历，因此复杂度为n。

*  for循环方式遍历

int size = list.size()
    for(int i=0; i<size;i++){
                        
        System.out.println(list.get(i)+"  ");         
    }

*  迭代器方式遍历

Iterator iter = list.iterator();          
    while(iter.hasNext()) {
                               
        String value = (String)iter.next();       
        System.out.print(value + "  ");           
    }

## 四、源码分析 ##

public class LinkedList<E>
        extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable
    {
        
        // 存放元素的个数
        transient int size = 0;
        // 指向头节点
        transient Node<E> first;
        // 指向尾节点
        transient Node<E> last;
        
       //构造方法，创建一个空的列表 
        public LinkedList() {
         
        } 
        //将一个指定的集合添加到LinkedList中，先完成初始化，在调用添加操作 
        public LinkedList(Collection<? extends E> c) {
         
            this(); 
            addAll(c); 
        } 
        //插入头节点 
        private void linkFirst(E e) {
         
            final Node<E> f = first;  //将头节点赋值给f节点 
            //new 一个新的节点，此节点的data = e , pre = null , next - > f  
            final Node<E> newNode = new Node<>(null, e, f); 
            first = newNode; //将新创建的节点地址复制给first 
            if (f == null)  //f == null，表示此时LinkedList为空 
                last = newNode;  //将新创建的节点赋值给last 
            else 
                f.prev = newNode;  //否则f.前驱指向newNode 
            size++; 
            modCount++; 
        } 
        //插入尾节点 
        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++; 
        } 
        //在succ节点前插入e节点，并修改各个节点之间的前驱后继 
        void linkBefore(E e, Node<E> succ) {
         
            // assert succ != null; 
            final Node<E> pred = succ.prev; 
            final Node<E> newNode = new Node<>(pred, e, succ); 
            succ.prev = newNode; 
            if (pred == null) 
                first = newNode; 
            else 
                pred.next = newNode; 
            size++; 
            modCount++; 
        } 
        //删除头节点 
        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; 
        } 
        //删除尾节点 
        private E unlinkLast(Node<E> l) {
         
            // assert l == last && l != null; 
            final E element = l.item; 
            final Node<E> prev = l.prev; 
            l.item = null; 
            l.prev = null; // help GC 
            last = prev; 
            if (prev == null) 
                first = null; 
            else 
                prev.next = null; 
            size--; 
            modCount++; 
            return element; 
        } 
        //删除指定节点 
        E unlink(Node<E> x) {
         
            // assert x != null; 
            final E element = x.item; 
            final Node<E> next = x.next;  //获取指定节点的前驱 
            final Node<E> prev = x.prev;  //获取指定节点的后继 
            if (prev == null) {
         
                first = next;   //如果前驱为null, 说明此节点为头节点 
            } else {
         
                prev.next = next;  //前驱结点的后继节点指向当前节点的后继节点 
                x.prev = null;     //当前节点的前驱置空 
            } 
            if (next == null) {
            //如果当前节点的后继节点为null ,说明此节点为尾节点 
                last = prev; 
            } else {
         
                next.prev = prev;  //当前节点的后继节点的前驱指向当前节点的前驱节点 
                x.next = null;     //当前节点的后继置空 
            } 
            x.item = null;     //当前节点的元素设置为null ,等待垃圾回收 
            size--; 
            modCount++; 
            return element; 
        } 
        //获取LinkedList中的第一个节点信息 
        public E getFirst() {
         
            final Node<E> f = first; 
            if (f == null) 
                throw new NoSuchElementException(); 
            return f.item; 
        } 
        //获取LinkedList中的最后一个节点信息 
        public E getLast() {
         
            final Node<E> l = last; 
            if (l == null) 
                throw new NoSuchElementException(); 
            return l.item; 
        } 
        //删除头节点 
        public E removeFirst() {
         
            final Node<E> f = first; 
            if (f == null) 
                throw new NoSuchElementException(); 
            return unlinkFirst(f); 
        } 
        //删除尾节点 
        public E removeLast() {
         
            final Node<E> l = last; 
            if (l == null) 
                throw new NoSuchElementException(); 
            return unlinkLast(l); 
        } 
        //将添加的元素设置为LinkedList的头节点 
        public void addFirst(E e) {
         
            linkFirst(e); 
        } 
        //将添加的元素设置为LinkedList的尾节点 
        public void addLast(E e) {
         
            linkLast(e); 
        } 
        //判断LinkedList是否包含指定的元素 
        public boolean contains(Object o) {
         
            return indexOf(o) != -1; 
        } 
        //返回List中元素的数量 
        public int size() {
         
            return size; 
        } 
        //在LinkedList的尾部添加元素 
        public boolean add(E e) {
         
            linkLast(e); 
            return true; 
        } 
        //删除指定的元素 
        public boolean remove(Object o) {
         
            if (o == null) {
         
                for (Node<E> x = first; x != null; x = x.next) {
         
                    if (x.item == null) {
         
                        unlink(x); 
                        return true; 
                    } 
                } 
            } else {
         
                for (Node<E> x = first; x != null; x = x.next) {
         
                    if (o.equals(x.item)) {
         
                        unlink(x); 
                        return true; 
                    } 
                } 
            } 
            return false; 
        } 
        //将集合中的元素添加到List中 
        public boolean addAll(Collection<? extends E> c) {
         
            return addAll(size, c); 
        } 
        //将集合中的元素全部插入到List中，并从指定的位置开始 
        public boolean addAll(int index, Collection<? extends E> c) {
         
            checkPositionIndex(index); 
            Object[] a = c.toArray();  //将集合转化为数组 
            int numNew = a.length;  //获取集合中元素的数量 
            if (numNew == 0)   //集合中没有元素，返回false 
                return false; 
            Node<E> pred, succ; 
            if (index == size) {
         
                succ = null; 
                pred = last; 
            } else {
         
                succ = node(index); //获取位置为index的结点元素，并赋值给succ 
                pred = succ.prev; 
            } 
            for (Object o : a) {
          //遍历数组进行插入操作。修改节点的前驱后继 
                @SuppressWarnings("unchecked") E e = (E) o; 
                Node<E> newNode = new Node<>(pred, e, null); 
                if (pred == null) 
                    first = newNode; 
                else 
                    pred.next = newNode; 
                pred = newNode; 
            } 
            if (succ == null) {
         
                last = pred; 
            } else {
         
                pred.next = succ; 
                succ.prev = pred; 
            } 
            size += numNew; 
            modCount++; 
            return true; 
        } 
        //删除List中所有的元素 
        public void clear() {
         
            // Clearing all of the links between nodes is "unnecessary", but: 
            // - helps a generational GC if the discarded nodes inhabit 
            //   more than one generation 
            // - is sure to free memory even if there is a reachable Iterator 
            for (Node<E> x = first; x != null; ) {
         
                Node<E> next = x.next; 
                x.item = null; 
                x.next = null; 
                x.prev = null; 
                x = next; 
            } 
            first = last = null; 
            size = 0; 
            modCount++; 
        } 
        //获取指定位置的元素 
        public E get(int index) {
         
            checkElementIndex(index); 
            return node(index).item; 
        } 
        //将节点防止在指定的位置 
        public E set(int index, E element) {
         
            checkElementIndex(index); 
            Node<E> x = node(index); 
            E oldVal = x.item; 
            x.item = element; 
            return oldVal; 
        } 
        //将节点放置在指定的位置 
        public void add(int index, E element) {
         
            checkPositionIndex(index); 
            if (index == size) 
                linkLast(element); 
            else 
                linkBefore(element, node(index)); 
        } 
        //删除指定位置的元素 
        public E remove(int index) {
         
            checkElementIndex(index); 
            return unlink(node(index)); 
        } 
        //判断索引是否合法 
        private boolean isElementIndex(int index) {
         
            return index >= 0 && index < size; 
        } 
        //判断位置是否合法 
        private boolean isPositionIndex(int index) {
         
            return index >= 0 && index <= size; 
        } 
        //索引溢出信息 
        private String outOfBoundsMsg(int index) {
         
            return "Index: "+index+", Size: "+size; 
        } 
        //检查节点是否合法 
        private void checkElementIndex(int index) {
         
            if (!isElementIndex(index)) 
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 
        } 
        //检查位置是否合法 
        private void checkPositionIndex(int index) {
         
            if (!isPositionIndex(index)) 
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 
        } 
        //返回指定位置的节点信息 
        //LinkedList无法随机访问，只能通过遍历的方式找到相应的节点 
        //为了提高效率，当前位置首先和元素数量的中间位置开始判断，小于中间位置， 
        //从头节点开始遍历，大于中间位置从尾节点开始遍历 
        Node<E> node(int index) {
         
            // assert isElementIndex(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; 
            } 
        } 
        //返回第一次出现指定元素的位置 
        public int indexOf(Object o) {
         
            int index = 0; 
            if (o == null) {
         
                for (Node<E> x = first; x != null; x = x.next) {
         
                    if (x.item == null) 
                        return index; 
                    index++; 
                } 
            } else {
         
                for (Node<E> x = first; x != null; x = x.next) {
         
                    if (o.equals(x.item)) 
                        return index; 
                    index++; 
                } 
            } 
            return -1; 
        } 
        //返回最后一次出现元素的位置 
        public int lastIndexOf(Object o) {
         
            int index = size; 
            if (o == null) {
         
                for (Node<E> x = last; x != null; x = x.prev) {
         
                    index--; 
                    if (x.item == null) 
                        return index; 
                } 
            } else {
         
                for (Node<E> x = last; x != null; x = x.prev) {
         
                    index--; 
                    if (o.equals(x.item)) 
                        return index; 
                } 
            } 
            return -1; 
        } 
        //弹出第一个元素的值 
        public E peek() {
         
            final Node<E> f = first; 
            return (f == null) ? null : f.item; 
        } 
        //获取第一个元素 
        public E element() {
         
            return getFirst(); 
        } 
        //弹出第一元素，并删除 
        public E poll() {
         
            final Node<E> f = first; 
            return (f == null) ? null : unlinkFirst(f); 
        } 
        //删除第一个元素 
        public E remove() {
         
            return removeFirst(); 
        } 
        //添加到尾部 
        public boolean offer(E e) {
         
            return add(e); 
        } 
        //添加到头部 
        public boolean offerFirst(E e) {
         
            addFirst(e); 
            return true; 
        } 
        //插入到最后一个元素 
        public boolean offerLast(E e) {
         
            addLast(e); 
            return true; 
        } 
        //队列操作 
        //尝试弹出第一个元素，但是不删除元素 
        public E peekFirst() {
         
            final Node<E> f = first; 
            return (f == null) ? null : f.item; 
         } 
        //队列操作 
        //尝试弹出最后一个元素，不删除 
        public E peekLast() {
         
            final Node<E> l = last; 
            return (l == null) ? null : l.item; 
        } 
        //弹出第一个元素，并删除 
        public E pollFirst() {
         
            final Node<E> f = first; 
            return (f == null) ? null : unlinkFirst(f); 
        } 
        //弹出最后一个元素，并删除 
        public E pollLast() {
         
            final Node<E> l = last; 
            return (l == null) ? null : unlinkLast(l); 
        } 
        //如队列，添加到头部 
        public void push(E e) {
         
            addFirst(e); 
        } 
        //出队列删除第一个节点 
        public E pop() {
         
            return removeFirst(); 
        } 
       //删除指定元素第一次出现的位置 
        public boolean removeFirstOccurrence(Object o) {
         
            return remove(o); 
        } 
        //删除指定元素最后一次出现的位置 
        public boolean removeLastOccurrence(Object o) {
         
            if (o == null) {
         
                for (Node<E> x = last; x != null; x = x.prev) {
         
                    if (x.item == null) {
         
                        unlink(x); 
                        return true; 
                    } 
                } 
            } else {
         
                for (Node<E> x = last; x != null; x = x.prev) {
         
                    if (o.equals(x.item)) {
         
                        unlink(x); 
                        return true; 
                    } 
                } 
            } 
            return false; 
        } 
        //遍历方法 
        public ListIterator<E> listIterator(int index) {
         
            checkPositionIndex(index); 
            return new ListItr(index); 
        } 
        //内部类，实现ListIterator接口 
        private class ListItr implements ListIterator<E> {
         
            private Node<E> lastReturned = null; 
            private Node<E> next; 
            private int nextIndex; 
            private int expectedModCount = modCount; 
            ListItr(int index) {
         
                // assert isPositionIndex(index); 
                next = (index == size) ? null : node(index); 
                nextIndex = index; 
            } 
            public boolean hasNext() {
         
                return nextIndex < size; 
            } 
            public E next() {
         
                checkForComodification(); 
                if (!hasNext()) 
                    throw new NoSuchElementException(); 
                lastReturned = next; 
                next = next.next; 
                nextIndex++; 
                return lastReturned.item; 
            } 
            public boolean hasPrevious() {
         
                return nextIndex > 0; 
            } 
            public E previous() {
         
                checkForComodification(); 
                if (!hasPrevious()) 
                    throw new NoSuchElementException(); 
                lastReturned = next = (next == null) ? last : next.prev; 
                nextIndex--; 
                return lastReturned.item; 
            } 
            public int nextIndex() {
         
                return nextIndex; 
            } 
            public int previousIndex() {
         
                return nextIndex - 1; 
            } 
            public void remove() {
         
                checkForComodification(); 
                if (lastReturned == null) 
                    throw new IllegalStateException(); 
                Node<E> lastNext = lastReturned.next; 
                unlink(lastReturned); 
                if (next == lastReturned) 
                    next = lastNext; 
                else 
                    nextIndex--; 
                lastReturned = null; 
                expectedModCount++; 
            } 
            public void set(E e) {
         
                if (lastReturned == null) 
                    throw new IllegalStateException(); 
                checkForComodification(); 
                lastReturned.item = e; 
            } 
            public void add(E e) {
         
                checkForComodification(); 
                lastReturned = null; 
                if (next == null) 
                    linkLast(e); 
                else 
                    linkBefore(e, next); 
                nextIndex++; 
                expectedModCount++; 
            } 
            final void checkForComodification() {
         
                if (modCount != expectedModCount) 
                    throw new ConcurrentModificationException(); 
            } 
        } 
        //静态内部类，创建节点 
        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; 
            } 
        } 
        /** 
         * @since 1.6 
         */ 
        public Iterator<E> descendingIterator() {
         
            return new DescendingIterator(); 
        } 
        /** 
         * Adapter to provide descending iterators via ListItr.previous 
         */ 
        private class DescendingIterator implements Iterator<E> {
         
            private final ListItr itr = new ListItr(size()); 
            public boolean hasNext() {
         
                return itr.hasPrevious(); 
            } 
            public E next() {
         
                return itr.previous(); 
            } 
            public void remove() {
         
                itr.remove(); 
            } 
        } 
        @SuppressWarnings("unchecked") 
        private LinkedList<E> superClone() {
         
            try {
         
                return (LinkedList<E>) super.clone(); 
            } catch (CloneNotSupportedException e) {
         
                throw new InternalError(); 
            } 
        } 
        /** 
         * Returns a shallow copy of this {@code LinkedList}. (The elements 
         * themselves are not cloned.) 
         * 
         * @return a shallow copy of this {@code LinkedList} instance 
         */ 
        public Object clone() {
         
            LinkedList<E> clone = superClone(); 
            // Put clone into "virgin" state 
            clone.first = clone.last = null; 
            clone.size = 0; 
            clone.modCount = 0; 
            // Initialize clone with our elements 
            for (Node<E> x = first; x != null; x = x.next) 
                clone.add(x.item); 
            return clone; 
        } 
        public Object[] toArray() {
         
            Object[] result = new Object[size]; 
            int i = 0; 
            for (Node<E> x = first; x != null; x = x.next) 
                result[i++] = x.item; 
            return result; 
        } 
        @SuppressWarnings("unchecked") 
        public <T> T[] toArray(T[] a) {
         
            if (a.length < size) 
                a = (T[])java.lang.reflect.Array.newInstance( 
                                    a.getClass().getComponentType(), size); 
            int i = 0; 
            Object[] result = a; 
            for (Node<E> x = first; x != null; x = x.next) 
                result[i++] = x.item; 
            if (a.length > size) 
                a[size] = null; 
            return a; 
        } 
        private static final long serialVersionUID = 876323262645176354L; 
        //将对象写入到输出流中 
        private void writeObject(java.io.ObjectOutputStream s) 
            throws java.io.IOException {
         
            // Write out any hidden serialization magic 
            s.defaultWriteObject(); 
            // Write out size 
            s.writeInt(size); 
            // Write out all elements in the proper order. 
            for (Node<E> x = first; x != null; x = x.next) 
                s.writeObject(x.item); 
        } 
        //从输入流中将对象读出 
        @SuppressWarnings("unchecked") 
        private void readObject(java.io.ObjectInputStream s) 
            throws java.io.IOException, ClassNotFoundException {
         
            // Read in any hidden serialization magic 
            s.defaultReadObject(); 
            // Read in size 
            int size = s.readInt(); 
            // Read in all elements in the proper order. 
            for (int i = 0; i < size; i++) 
                linkLast((E)s.readObject()); 
        } 
    }

LinkedList继承AbstractSequentialList是为什么?

AbstractSequentialList 提供了一套基于顺序访问的接口。通过继承此类，子类仅需实现部分代码即可拥有完整的一套访问某种序列表（比如链表）的接口。深入源码，AbstractSequentialList 提供的方法基本上都是通过 ListIterator 实现。

所以只要继承类实现了listIterator方法，它不需要再额外实现什么即可使用。对于随机访问集合类一般建议继承AbstractList而不是AbstractSequentialList。

LinkedList和其他父类一样，也是基于顺序访问。所以LinkedList继承了AbstractSequentialList，但LinkedList并没有直接使用父类的方法，而是重新实现了一套方法。

另外，LinkedList还实现了Deque（double ended queue）,Deque又继承自Queue接口。这样LinkedList就具备了队列的功能。