这次牛逼了，面试字节被问LinkedList原理了！手足无措啊

刺骨的言语ヽ痛彻心扉 2022-10-07 07:49 142阅读 0赞

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70][]

# 概述 #

LinkedList底层是基于链表实现。链表没有长度限制，内存地址不需要固定长度，也不需要是连续的地址来进行存储，只需要通过引用来关联前后元素即可完成整个链表的连续。所以链表的优点就是添加删除元素比较快，只需要移动指针，并且不需要判断扩容。缺点就是因为没有索引，所以在查询和遍历元素时候比较慢。

使用场景：在增删操作使用较多，查询遍历操作使用较少情况下比较适合去使用；例如：拿来当栈使用。

# 数据结构 #

## 继承实现关系 ##

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

*  **`AbstractSequentialList`**：本质上面与继承`AbstractList` 没有什么区别，`AbstractSequentialList`完善了 `AbstractList`中没有实现的方法。
 *  **`List`**：实现List接口。
 *  **`Deque`**：实现Deque队列接口，拥有作为双端队列（队列和栈）的功能。
 *  **`Cloneable`**：重写clone()方法，通过创建新的LinkedList 对象，遍历拷贝数据进行对象拷贝。
 *  **`Serializable`**：重写read/writeObject() 方法实现序列化。

## 静态内部类 ##

为什么Node这个类是静态的？答案是：这跟内存泄露有关，Node类是在LinkedList类中的，也就是一个内部类，若不使用static修饰，那么Node就是一个普通的内部类，在java中，一个普通内部类在实例化之后，默认会持有外部类的引用，这就有可能造成内存泄露（内部类与外部类生命周期不一致时）。但使用static修饰过的内部类（称为静态内部类），就不会有这种问题。[【获取资料】][Link 1]

*  非静态内部类会自动生成一个构造器依赖于外部类：也是内部类可以访问外部类的实例变量的原因。
 *  静态内部类不会生成，访问不了外部类的实例变量，只能访问类变量。

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

## 基本属性 ##

// 元素数量
    2     transient int size = 0;
    3     // 头结点
    4     transient Node<E> first;
    5     // 尾节点
    6     transient Node<E> last;

## 构造方法 ##

1     public LinkedList() {
        
    2     }
    3 
    4     public LinkedList(Collection<? extends E> c) {
        
    5         this();
    6         addAll(c);
    7     }

# 主要方法解析 #

## 获取元素 ##

peek()：队列的查，获取队头元素。

public E get(int index) {
            // 根据索引获取
            checkElementIndex(index);
            return node(index).item;
        }
        Node<E> node(int index) {
        
            // assert isElementIndex(index);
            // 利用二分法查找；小于中间数从头结点开始找，否则从尾节点开始找
            //加入Java开发交流君样：756584822一起吹水聊天
            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;
            }
        }
        // 获取队头元素 ，但是不删除队列的头元素（双端队列Deque中的方法）
        public E getFirst() {
        
            final Node<E> f = first;
            if (f == null)
                throw new NoSuchElementException();
            return f.item;
        }
        // 获取队尾元素，但是不删除队列的尾元素（实现双端队列Deque中的方法）
        public E getLast() {
        
            final Node<E> l = last;
            if (l == null)
                throw new NoSuchElementException();
            return l.item;
        }
    
        // 队列的查。获取队头元素。
        public E peek() {
        
            final Node<E> f = first;
            return (f == null) ? null : f.item;
        }

添加元素  
　　offer()：队列的增，添加队尾元素，底层实现是调用add()->linkLast()。

push()：栈的增，把元素压入栈中，添加对头元素，底层实现是调用addFirst()->linkFirst()。

1     // 添加元素，默认在链表尾部添加
     2     public boolean add(E e) {
        
     3         linkLast(e);
     4         return true;
     5     }//加入Java开发交流君样：756584822一起吹水聊天
     6     // 指定索引添加元素
     7     public void add(int index, E element) {
        
     8         checkPositionIndex(index);  // 检验下标是否越界
     9 
    10         if (index == size)  // 如果要插入的索引等于现有元素长度，说明是要在尾部插入元素
    11             linkLast(element);
    12         else    // 否则，获取该索引节点，在该节点之前插入元素
    13             linkBefore(element, node(index));
    14     }
    15 
    16     public boolean addAll(Collection<? extends E> c) {
        
    17         return addAll(size, c);
    18     }
    19     public boolean addAll(int index, Collection<? extends E> c) {
        
    20         checkPositionIndex(index);  // 检验下标是否越界
    21 
    22         Object[] a = c.toArray();
    23         int numNew = a.length;
    24         if (numNew == 0)
    25             return false;
    26 
    27         // pred:前置节点，在该节点之后插入元素。succ：该索引位节点。
    28         Node<E> pred, succ;
    29         if (index == size) {
        
    30             succ = null;
    31             pred = last;
    32         } else {
        
    33             succ = node(index);
    34             pred = succ.prev;
    35         }
    36         // 将数组设置为链表
    37         for (Object o : a) {
        
    38             @SuppressWarnings("unchecked") E e = (E) o;
    39             Node<E> newNode = new Node<>(pred, e, null);    // 新建一个节点，指向前置节点
    40             if (pred == null)   // 如果前置节点为空，说明该链表为空。将头节点指向当前节点
    41                 first = newNode;
    42             else    // 前置节点的后继节点指向当前节点
    43                 pred.next = newNode;
    44             pred = newNode; // 将当前节点设置为前置节点，供后面需要插入的节点使用
    45         }//加入Java开发交流君样：756584822一起吹水聊天
    46 
    47         if (succ == null) {
        
    48             last = pred;
    49         } else {
        
    50             pred.next = succ;
    51             succ.prev = pred;
    52         }
    53 
    54         size += numNew;
    55         modCount++;
    56         return true;
    57     }
    58 
    59     // 添加元素到头结点（实现双端队列Deque中的方法）
    60     public void addFirst(E e) {
        
    61         linkFirst(e);
    62     }
    63     private void linkFirst(E e) {
        
    64         final Node<E> f = first;    // 原头节点
    65         final Node<E> newNode = new Node<>(null, e, f); // 新建一个节点，要添加的元素
    66         first = newNode;    // 将头结点指向该新建的节点
    67         if (f == null)  // 如果原头结点为空，说明原链表为空。这是添加的第一个元素，将尾结点也指向该新建的节点
    68             last = newNode;
    69         else    // 如果原头结点不为空，则将原头结点的前置节点指向该新建的节点
    70             f.prev = newNode;
    71         size++; // 元素数量+1
    72         modCount++; // 修改次数+1
    73     }
    74     // 添加元素到尾结点（实现双端队列Deque中的方法）
    75     public void addLast(E e) {
        
    76         linkLast(e);
    77     }
    78     void linkLast(E e) {
        
    79         final Node<E> l = last; // 原尾结点
    80         final Node<E> newNode = new Node<>(l, e, null); // 新建一个节点，要添加的元素
    81         last = newNode; // 将尾结点指向该新建的节点
    82         if (l == null)  // 如果尾头结点为空，说明原链表为空。这是添加的第一个元素，将头结点也指向该新建的节点
    83             first = newNode;
    84         else    // 如果原尾结点不为空，则将原尾结点的后继节点指向该新建的节点
    85             l.next = newNode;
    86         size++; // 元素数量+1
    87         modCount++; // 修改次数+1
    88     }
    89 
    90     // 队列的添加方法
    91     public boolean offer(E e) {
        
    92         return add(e);
    93     }
    94 
    95     // 栈的添加方法
    96     public void push(E e) {
        
    97         addFirst(e);
    98     }

# 删除元素 #

poll()：队列的删，获取对头元素并且对头元素删除。

pop()：栈的删，返回的是栈顶元素并将栈顶元素删除。

1     public boolean remove(Object o) {
        
     2         if (o == null) {
        
     3             for (Node<E> x = first; x != null; x = x.next) {
        
     4                 if (x.item == null) {
        
     5                     unlink(x);
     6                     return true;
     7                 }
     8             }
     9         } else {
        
    10             for (Node<E> x = first; x != null; x = x.next) {
        
    11                 if (o.equals(x.item)) {
        
    12                     unlink(x);
    13                     return true;
    14                 }
    15             }
    16         }
    17         return false;
    18     }
    19     public E remove(int index) {
        
    20         checkElementIndex(index);
    21         return unlink(node(index));
    22     }
    23     // 将该节点前置节点的下一个节点指向该节点后继节点，将该节点后继节点的上一个节点指向该节点前置节点。并将该节点置为空
    24     E unlink(Node<E> x) {
        
    25         // assert x != null;
    26         final E element = x.item;
    27         final Node<E> next = x.next;
    28         final Node<E> prev = x.prev;
    29 
    30         if (prev == null) {
        
    31             first = next;
    32         } else {
        
    33             prev.next = next;
    34             x.prev = null;
    35         }
    36 
    37         if (next == null) {
        
    38             last = prev;
    39         } else {
        
    40             next.prev = prev;
    41             x.next = null;
    42         }
    43 
    44         x.item = null;
    45         size--;
    46         modCount++;
    47         return element;
    48     }
    49     // 将头结点的下一个节点设置为新的头结点，并将原头节点置为空
    50     private E unlinkFirst(Node<E> f) {
        
    51         // assert f == first && f != null;
    52         final E element = f.item;
    53         final Node<E> next = f.next;
    54         f.item = null;
    55         f.next = null; // help GC
    56         first = next;
    57         if (next == null)
    58             last = null;
    59         else
    60             next.prev = null;
    61         size--;
    62         modCount++;
    63         return element;
    64     }
    65     //加入Java开发交流君样：756584822一起吹水聊天
    66     // 将尾结点的上一个节点设置为新的尾结点，并将原尾节点置为空
    67     private E unlinkLast(Node<E> l) {
        
    68         // assert l == last && l != null;
    69         final E element = l.item;
    70         final Node<E> prev = l.prev;
    71         l.item = null;
    72         l.prev = null; // help GC
    73         last = prev;
    74         if (prev == null)
    75             first = null;
    76         else
    77             prev.next = null;
    78         size--;
    79         modCount++;
    80         return element;
    81     }
    82 
    83     public E remove() {
        
    84         return removeFirst();
    85     }
    86 
    87     // 队列的删除方法
    88     public E poll() {
        
    89         final Node<E> f = first;
    90         return (f == null) ? null : unlinkFirst(f);
    91     }
    92     // 栈的删除方法
    93     public E pop() {
        
    94         return removeFirst();
    95     }

**最后，祝大家早日学有所成，拿到满意offer**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqMTMxNDI1MA_size_16_color_FFFFFF_t_70]: /images/20221005/4f08bb0970b6492e9233acee858123c3.png
[Link 1]: https://shimo.im/docs/9GTP6XrJg9J88cJD/