java集合框架入门解析-----linkedList

素颜马尾好姑娘i 2022-12-29 04:39 141阅读 0赞

### java集合框架入门解析-----linkedList ###

*  0.结构图
 *  1.linkedList是什么
 *  2.linkedList的特点
 *  3.LinkedList继承的类和实现的接口
 *   *  1）AbstractSequentialList结构及成员函数
     *  (1). 什么是 AbstractSequentialList
     *  (2). 获取迭代器
     *  (3). add(int, E)
     *  (4). addAll(int index, Collection<? extends E> c)
     *  (5). get(int index)
     *  (6). remove(int index)
     *  (7). set(int index, E element)
     *  2）LinkedList 的结构和方法
     *  (1). 关键的几个内部方法
     *  (3). 公共的删除方法
     *  (4). 清除元素
     *  (5). 设置数据
     *  (6). 查询方法
     *  (7). 迭代器方法
 *  4. Queue接口
 *  5.Deque接口
 *  6.ArrayList和LinkedList
 *   *  ArrayList
     *  LinkedList

# 0.结构图 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3podXlpbjY1NTM_size_16_color_FFFFFF_t_70_pic_center]

# 1.linkedList是什么 #

LinkedList使用了循环双向链表数据结构，并提供了一些队列，栈，双端队列操作的方法。

# 2.linkedList的特点 #

1）与ArrayList对比，LinkedList插入、删除更高效，随机访问速度慢。  
2）非同步，线程不安全，支持null，有序，元素可重复。  
3）可以作为栈，队列，双端队列使用。

# 3.LinkedList继承的类和实现的接口 #

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

## 1）AbstractSequentialList结构及成员函数 ##

public abstract class AbstractSequentialList<E> extends AbstractList<E>

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3podXlpbjY1NTM_size_16_color_FFFFFF_t_70]

## (1). 什么是 AbstractSequentialList ##

AbstractSequentialList 继承自 AbstractList，是 LinkedList 的父类，是 List 接口 的简化版实现。  
简化的地方在 AbstractSequentialList 只支持按次序访问，而不像 AbstractList 那样支持随机访问。

## (2). 获取迭代器 ##

public Iterator<E> iterator() { 
            return listIterator();
        }
        
    public abstract ListIterator<E> listIterator(int index);

## (3). add(int, E) ##

添加元素到指定位置，将当前处于该位置（如果有的话）和任何后续元素的元素移到右边（添加一个到它们的索引）：

public void add(int index, E element) { 
            try { 
            //注意：这里要调用了 ListIterator.add()，没有实现该方法的话会报异常
                listIterator(index).add(element);
            } catch (NoSuchElementException exc) { 
                throw new IndexOutOfBoundsException("Index: "+index);
            }
        }

## (4). addAll(int index, Collection<? extends E> c) ##

将指定集合中的所有元素插入到列表的指定位置(可选操作)。将当前位于该位置的元素(如果有的话)和任何后续元素向右移动(增加它们的索引)。新元素将按指定集合的迭代器返回的顺序出现在此列表中。如果在操作进行时修改了指定的集合，则此操作的行为未定义。(注意，如果指定的集合是这个列表，并且它不是空的，就会发生这种情况。)

之后请看在linkedList中的实现

## (5). get(int index) ##

获取指定位置的元素：

public E get(int index) { 
            try { 
                return listIterator(index).next();
            } catch (NoSuchElementException exc) { 
                throw new IndexOutOfBoundsException("Index: "+index);
            }
        }

AbstractSequentialList 只支持迭代器按顺序 访问，不支持 RandomAccess，所以遍历 AbstractSequentialList 的子类，使用 for 循环 get() 的效率要 <= 迭代器遍历：

for(int i=0, n=list.size(); i < n; i++)
          list.get(i);
    //使用迭代器获取元素效率更高些 
    for (Iterator i=list.iterator(); i.hasNext(); )
         i.next();

## (6). remove(int index) ##

删除指定位置的元素：

public E remove(int index) { 
            try { 
                ListIterator<E> e = listIterator(index);
                E outCast = e.next();
                e.remove();
                return outCast;
            } catch (NoSuchElementException exc) { 
                throw new IndexOutOfBoundsException("Index: "+index);
            }
        }

## (7). set(int index, E element) ##

用指定的元素替换列表中指定位置的元素(可选操作)。

public E set(int index, E element) { 
            try { 
                ListIterator<E> e = listIterator(index);
                E oldVal = e.next();
                e.set(element);
                return oldVal;
            } catch (NoSuchElementException exc) { 
                throw new IndexOutOfBoundsException("Index: "+index);
            }
        }

## 2）LinkedList 的结构和方法 ##

//指向第一个节点的指针。
    //只有两种情况: (first == null && last == null) || (first.prev == null && first.item != null) 
    transient Node<E> first;
    
    //指向最后一个节点的指针
    //(first == null && last == null) || (last.next == null && last.item != null)
    transient Node<E> last;
    
    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;
            }
        }

## (1). 关键的几个内部方法 ##

（头部添加删除，尾部添加删除，获取指定节点，指定节点的添加删除）

注意：要记住  
first是始终要指向第一个节点的，有插入头部的节点，或者删除第一个节点的，first要跟着变。  
last是始终指向最后一个节点的，有插入，或者删除最后一个节点的，last要跟着变。  
判断情况就是上面列举出来的那两种情况。  
记住这点，下面的代码就容易看懂了。

//链接e作为第一个元素
    private void linkFirst(E e) { 
    		//获取首节点元素的指针
            final Node<E> f = first;
            //新建一个节点，注意next节点指向了F
            final Node<E> newNode = new Node<>(null, e, f);
            //首结点指针指向新的节点
            first = newNode;
            //如果链表为空链表，未节点指针指向新节点
            if (f == null)
                last = newNode;
             //如果不为空，原来首结点的pre指针指向新节点
            else
                f.prev = newNode;
            size++;
            modCount++;
        }
    //链接e作为最后一个元素
    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++;
        }
    //删除链接非空的第一个节点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;
        }
    
    //删除链接非空的最后一个节点l
        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;
        }
    //删除链接非空节点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;
            size--;
            modCount++;
            return element;
        }
    //返回指定元素索引处的（非空）节点
    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;
            }
        }

(2). 公共的添加方法

//将指定的元素追加到此列表的末尾
        public boolean add(E e) { 
            linkLast(e);//调用了上面的方法
            return true;
        }
    //在列表的指定位置插入指定的元素。
    //将当前位于该位置的元素(如果有的话)和任何后续的元素向右移动(给它们的索引加1)。
        public void add(int index, E element) { 
            checkPositionIndex(index);
    
            if (index == size)
                linkLast(element);
            else
                linkBefore(element, node(index));  //node()方法，上面也有，用来找到执行位置的节点
        }
    //将指定集合中的所有元素按集合迭代器返回的顺序追加到列表的末尾。如果在操作进行时修改了指定的集合，则此操作的行为未定义。
    //(注意，如果指定的集合是这个列表，并且它不是空的，就会发生这种情况。)
        public boolean addAll(Collection<? extends E> c) { 
            return addAll(size, c);
        }
    //从指定位置开始，将指定集合中的所有元素插入到列表中。将当前位于该位置的元素(如果有的话)和任何后续元素向右移动(增加它们的索引)。
    //新元素将按照指定集合的迭代器返回的顺序出现在列表中。
        public boolean addAll(int index, Collection<? extends E> c) { 
            checkPositionIndex(index);
    		//要添加的集合转数组 
            Object[] a = c.toArray();
            int numNew = a.length;
            if (numNew == 0)
                return false;
    		//声明两个节点，分别指向要插入位置的前面节点和要插入位置的节点
            Node<E> pred, succ;
            if (index == size) { 
                succ = null;
                pred = last;
            } else { 
                succ = node(index);//node()返回指定元素索引处的（非空）节点
                pred = succ.prev;//pred拿到指定位置的前一个节点指针
            }
    		//遍历要添加的数组 
            for (Object o : a) {   
                @SuppressWarnings("unchecked") E e = (E) o;
                //注意pred的是指向succ前一个节点的
                Node<E> newNode = new Node<>(pred, e, null);
                //判断插入的节点是不是首节点
                if (pred == null)
                    first = newNode;
                else
                    pred.next = newNode;
                //这里pred 指向了新插入的节点 
                pred = newNode;
            }
    		
            if (succ == null) { 
                last = pred;
            } else {  /此时的pred 指向的是集合最后一个元素，要把这个元素和succ连起来，才能构成一个完整的链
                pred.next = succ;
                succ.prev = pred;
            }
    
            size += numNew;
            modCount++;
            return true;
        }
    //添加到头部，时间复杂度为 O(1)
    public void addFirst(E e) { 
        linkFirst(e);
    }
    
    //添加到尾部，时间复杂度为 O(1)
    public void addLast(E e) { 
        linkLast(e);
    }

## (3). 公共的删除方法 ##

//删除头部节点
    public E remove() { 
        return removeFirst();
    }
    
    //删除指定位置节点
    public E remove(int index) { 
        checkElementIndex(index);
        return unlink(node(index));
    }
    
    //删除包含指定元素的节点，这就得遍历了
    public boolean remove(Object o) { 
        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;
    }
    
    //删除头部元素
    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);
    }
    
    //删除首次出现的指定元素，从头遍历
    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;
    }

## (4). 清除元素 ##

清除元素的话只需要把首尾都置为 null, 这个链表就已经是空的，因为无法访问元素。  
但是为了避免浪费空间，需要把中间节点都置为 null：

public void clear() { 
        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++;
    }

## (5). 设置数据 ##

//set 很简单，找到这个节点，替换数据就好了
    public E set(int index, E element) { 
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

## (6). 查询方法 ##

//挨个遍历，获取第一次出现位置
    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 boolean contains(Object o) { 
        return indexOf(o) != -1;
    }
    
    //获取指定位置的元素，需要遍历
    public E get(int index) { 
        checkElementIndex(index);
        return node(index).item;
    }
    
    //获取第一个元素，很快
    public E getFirst() { 
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }
    
    //获取第一个，同时删除它
    public E poll() { 
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
    
    //也是获取第一个，和 poll 不同的是不删除
    public E peek() { 
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }
    
    //长得一样嘛
    public E peekFirst() { 
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }
    
    //最后一个元素，也很快
    public E getLast() { 
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }
    
    public E peekLast() { 
        final Node<E> l = last;
        return (l == null) ? null : l.item;
    }

## (7). 迭代器方法 ##

public ListIterator<E> listIterator(int index) { 
            checkPositionIndex(index);
            return new ListItr(index);
        }
    
        private class ListItr implements ListIterator<E> { 
            private Node<E> lastReturned;
            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++;
            }
    
            public void forEachRemaining(Consumer<? super E> action) { 
                Objects.requireNonNull(action);
                while (modCount == expectedModCount && nextIndex < size) { 
                    action.accept(next.item);
                    lastReturned = next;
                    next = next.next;
                    nextIndex++;
                }
                checkForComodification();
            }
    
            final void checkForComodification() { 
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
            }
        }

# 4. Queue接口 #

队列接口，定义了一些队列的基本操作，

注意使用时优先选择以下蓝色字体方法（offer、poll、peek），队列通常不允许null元素，因为我们通常调用poll方法是否返回null来判断队列是否为空，但是LinkedList是允许null元素的，所以，在使用LinkedList最为队列的实现时，不应该将null元素插入队列；

boolean add(E e);
    
    将对象e插入队列尾部，成功返回true，失败（没有空间）抛出异常IllegalStateException；
    
    boolean offer(E e);
    
    将对象e插入队列尾部，成功返回true，失败（没有空间）返回false；
    
    E remove();
    
    获取并移除队列头部元素，如果队列为空，抛出NoSuchElementException异常；
    
    E poll();
    
    获取并移除队列头部元素，如果队列为空，返回null；
    
    E element();
    
    获取但不移除队列头部元素，如果队列为空，抛出NoSuchElementException异常；
    
    E peek();
    
    获取但不移除队列头部元素，如果队列为空，返回null；

# 5.Deque接口 #

双端队列接口，继承队列接口，支持在队列两端进行入队和出队操作；

除了Collection接口Queue接口中定义的方法外，Deque还包括以下方法

void addFirst(E e);
    
    将对象e插入到双端队列头部，容间不足时，抛出IllegalStateException异常；
    
    void addLast(E e);
    
    将对象e插入到双端队列尾部，容间不足时，抛出IllegalStateException异常；
    
    boolean offerFirst(E e);
    
    将对象e插入到双端队列头部
    
    boolean offerLast(E e);
    
    将对象e插入到双端队列尾部；
    
    E removeFirst();
    
    获取并移除队列第一个元素，队列为空，抛出NoSuchElementException异常；
    
    E removeLast();
    
    获取并移除队列最后一个元素，队列为空，抛出NoSuchElementException异常；
    
    E pollFirst();
    
    获取并移除队列第一个元素，队列为空，返回null；
    
    E pollLast();
    
    获取并移除队列最后一个元素，队列为空，返回null；
    
    E getFirst();
    
    获取队列第一个元素，但不移除，队列为空，抛出NoSuchElementException异常；
    
    E getLast();
    
    获取队列最后一个元素，但不移除，队列为空，抛出NoSuchElementException异常；
    
    E peekFirst();
    
    获取队列第一个元素，队列为空，返回null；
    
    E peekLast();
    
    获取队列最后一个元素，队列为空，返回null；
    
    boolean removeFirstOccurrence(Object o);
    
    移除第一个满足 (o==null ? e==null : o.equals(e)) 的元素
    
    boolean removeLastOccurrence(Object o);
    
    移除最后一个满足 (o==null ? e==null : o.equals(e)) 的元素
    
    void push(E e);
    
    将对象e插入到双端队列头部；
    
    E pop();
    
    移除并返回双端队列的第一个元素
    
    Iterator<E> descendingIterator();
    
    双端队列尾部到头部的一个迭代器；

# 6.ArrayList和LinkedList #

## ArrayList ##

*  基于数组，在数组中搜索和读取数据是很快的。因此 ArrayList 获取数据的时间复杂度是O(1);
 *  但是添加、删除时该元素后面的所有元素都要移动，所以添加/删除数据效率不高；
 *  另外其实还是有容量的，每次达到阈值需要扩容，这个操作比较影响效率。

## LinkedList ##

*  基于双端链表，添加/删除元素只会影响周围的两个节点，开销很低；
 *  只能顺序遍历，无法按照索引获得元素，因此查询效率不高；
 *  没有固定容量，不需要扩容；
 *  需要更多的内存，如文章开头图片所示 LinkedList 每个节点中需要多存储前后节点的信息，占用空间更多些。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3podXlpbjY1NTM_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/1395233363ac41beb610a08a5127c159.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3podXlpbjY1NTM_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201219222906995.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3podXlpbjY1NTM=,size_16,color_FFFFFF,t_70