【Java集合】-- LinkedList源码解析

深碍√TFBOYSˉ_ 2023-07-10 14:12 2阅读 0赞

### 文章目录 ###

*  继承体系
 *  数据结构
 *  源码解析
 *   *  1.属性
     *  2.构造方法
     *   *  LinkedList()
         *  LinkedList(Collection<? extends E> c)
     *  3.添加元素
     *   *  add(E e)
         *  addFirst(E e)
         *  addLast(E e)
         *  add(int index, E element)
         *  offer(E e)
         *  offerFirst(E e)
         *  offerLast(E e)
         *  总结
     *  4.获取元素
     *   *  get(int index)
         *  getFirst()
         *  getLast()
         *  peek()
     *  5.删除元素
     *   *  remove()
         *  removeLast()
         *  removeLast()
         *  pollFirst()
         *  pollLast()
 *  总结

LinkedList是一种以带头尾指针的双向链表实现的 List，与 ArrayList 相比，其插入元素快，不需要将元素向后移动，但是其获取元素却没有 ArrayList 方便。

# 继承体系 #

![图片][format_png]

# 数据结构 #

![图片][format_png 1]

在linkedList中维护了一个双向链表

# 源码解析 #

## 1.属性 ##

//长度，默认为0
    transient int size = 0;
    //首节点
    transient Node<E> first;
    //尾节点
    transient Node<E> last;

## 2.构造方法 ##

### LinkedList() ###

public LinkedList() { 
    }

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

public LinkedList(Collection<? extends E> c) { 
        this();
        addAll(c);
    }
    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;
        //在链表的index处添加元素
        if (index == size) { 
            succ = null;
            pred = last;
        } else { 
            succ = node(index);
            pred = succ.prev;
        }
    
        //把c中元素添加到链表中
        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;
    }

## 3.添加元素 ##

### 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;
        //判断链表中是否存在节点
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

### addFirst(E e) ###

public void addFirst(E e) { 
        linkFirst(e);
    }
    //通过头插法存入元素
    private void linkFirst(E e) { 
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

### addLast(E e) ###

public void addLast(E e) { 
        //同add方法通过尾插法，插入元素
        linkLast(e);
    }

### add(int index, E element) ###

public void add(int index, E element) { 
        //边界值检测
        checkPositionIndex(index);
        if (index == size)
        //插入位置等于元素个数，直接插在链表尾部
            linkLast(element);
        else
        //获取对应index位置的元素
            linkBefore(element, node(index));
    }
    //把e元素生成的节点添加到succ前面
    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++;
    }

### offer(E e) ###

public boolean offer(E e) { 
        return add(e);
    }

将指定元素添加到链表尾部。

### offerFirst(E e) ###

public boolean offerFirst(E e) { 
        addFirst(e);
        return true;
    }

将指定元素添加到链表头

### offerLast(E e) ###

public boolean offerLast(E e) { 
        addLast(e);
        return true;
    }

链表尾部添加节点

### 总结 ###

向链表中间添加元素效率较慢，为O（n）。其他方式添加元素快，时间复杂度为O（1）

## 4.获取元素 ##

### get(int index) ###

public E get(int index) { 
        checkElementIndex(index);
        return node(index).item;
    }
    //获取指定索引位置的元素
    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;
        }
    }

### getFirst() ###

public E getFirst() { 
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

### getLast() ###

public E getLast() { 
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }

### peek() ###

public E peek() { 
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

## 5.删除元素 ##

### remove() ###

public E remove() { 
        return removeFirst();
    }
    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;
    }

### removeLast() ###

public E removeLast() { 
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(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;
    }

### removeLast() ###

public E removeLast() { 
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }

### pollFirst() ###

public E pollFirst() { 
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

### pollLast() ###

public E pollLast() { 
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }

# 总结 #

*  LinkedList是一个以双向链表实现的List；
 *  LinkedList还是一个双端队列，具有队列、双端队列、栈的特性；
 *  LinkedList在队列首尾添加、删除元素非常高效，时间复杂度为O(1)；
 *  LinkedList在中间添加、删除元素比较低效，时间复杂度为O(n)；
 *  LinkedList不支持随机访问，所以访问非队列首尾的元素比较低效；
 *  LinkedList在功能上等于ArrayList + ArrayDeque；

ArrayList代表了List的典型实现，LInkedList代表了Deque的典型实现，同时LinkedList也实现了List，通过这两个类一首一尾正好可以把整个集合贯穿起来。

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWRlci5zaGltby5pbS9mL25DR2hXZWtEakVvT1B5OVAucG5nIXRodW1ibmFpbA?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWRlci5zaGltby5pbS9mL3NPcEl3d3ZNeks4UWtyS3MucG5nIXRodW1ibmFpbA?x-oss-process=image/format,png