LinkedList 一篇就够

左手的ㄟ右手 2022-12-20 08:53 121阅读 0赞

## 创建 ##

List<Integer> list = new LinkedList<>();

## 结构 双向链表 ##

![在这里插入图片描述][20201111201519763.png_pic_center]

## 继承关系 ##

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

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

*  Serializable  
    接口中内容是空的，是一个标志接口，一个类只有实现了Serializable接口，它的对象才能被序列化，将对象状态转换为可保持或传输的格式的过程。标识给jvm帮忙序列化。
 *  Collection，List  
    集合的统一接口。统一定义了一套单列集合的接口
 *  Queue，Deque  
    他不仅是列表还是队列，双端队列（非线程安全，非阻塞队列）

## 核心属性 ##

*  int size = 0;存放元素个数
 *  Node< E> first;链表的头节点
 *  Node< E> last;链表的尾节点

## 构造方法 ##

*  public LinkedList()
 *  public LinkedList(Collection<? extends E> c)  
    将参数中的元素放进新创建的LinkedList中，addAll方法稍后再看

public LinkedList() { 
    }
    public LinkedList(Collection<? extends E> c) { 
    	this();
    	addAll(c);
    }

## 核心方法 public boolean add(E e) ##

添加元素到linkLast的末尾。

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;
        //当之前记录下的尾节点为null时，说明链表是空的。
        //那么当前构造的节点既是头结点也是尾节点
        //否则之前尾节点的后继节点为构造的节点
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 2]

## 核心方法 public E remove(int index) ##

移除指定位置的元素，一共分为下面三种情况。

*  移除中间结点

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

*  移除头节点的情况

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 5]

*  移除尾节点的情况  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 6]  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 7]  
    先做下标检查，再找到要移除的Node，最后移除Node  
    找到Node的时候根据index的位置选择正序还是倒序查找。  
    移除结点时，分三种情况，头结点，尾节点中间结点

public E remove(int index) { 
        //下标检查
        checkElementIndex(index);
        //先找到node，再移除node
        return unlink(node(index));
    }

从指定位置获取节点

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;
        }
    }

断开链表中的某个节点

E unlink(Node<E> x) { 
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;
        //节点的前驱为null，说明要移除的是头结点
        if (prev == null) { 
            //直接移动头指针 图1
            first = next;
        } else { 
            //前驱指向当前节点的后继 图2
            prev.next = next;
            //help gc
            x.prev = null;
        }
        //后继为Null，移除的是尾节点
        if (next == null) { 
            //移动尾指针为要移除结点的前驱 图3
            last = prev;
        } else { 
            //不为尾节点 后继的前驱指向前驱 图4
            next.prev = prev;
            //help gc
            x.next = null;
        }
        //help gc
        x.item = null;
        size--;
        modCount++;
        return element;
    }

## 核心方法 public E remove(Object o) ##

正序移除**一个**相等的元素

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;
    }

## 作为队列的使用 ##

队列的核心方法就是入队off，和出队poll，peek，下面看看各个方法

## offer ##

方法比较简单，只是调用了add方法。

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

## poll ##

返回头节点，并且断开连接。如果头节点为空，返回Null

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

/** * 移除链接非空的第一个节点f */
    private E unlinkFirst(Node<E> f) { 
        //先记录元素
        final E element = f.item;
        //找到头节点的下一个节点
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; 
        //修改头节点指针指向
        first = next;
        //下一个节点为空，那么链表为空，头尾指针都置空
        if (next == null)
            last = null;
        else
            //原头节点的下一节点的前驱置空
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

## peek ##

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

双端队列无非是可以在队列的两头进行入队出队操作，原理一致不再赘述。

[20201111201519763.png_pic_center]: /images/20221120/06c8a66252e34bb88fb7c5e0df93c24f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201111173747441.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201111201957770.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201111202032936.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201111205826610.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/2020111121010827.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/20201111210150837.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 6]: https://img-blog.csdnimg.cn/2020111121023562.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ==,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 7]: https://img-blog.csdnimg.cn/2020111121025255.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ==,size_16,color_FFFFFF,t_70#pic_center