深入理解LinkedList

小咪咪 2023-06-22 10:28 9阅读 0赞

### 文章目录 ###

*  什么是LinkedList？
 *  LinkedList与ArrayList的区别
 *  LinkedList继承了哪些类与接口？
 *  LinkedList中主要的成员变量
 *  LinkedList的构造方法
 *   *  LinkedList()
     *  LinkedList(Collection<? extends E> c)
     *   *  addAll(Collection<? extends E> c)方法
         *  addAll(int index, Collection<? extends E> c)方法
         *  checkPositionIndex(int index)方法
         *  isPositionIndex(int index)方法
 *  Node节点
 *  LinkedList的常用方法
 *   *  add(E e)
     *   *  linkLast(E e)
     *  add(int index, E element)
     *   *  linkBefore()
     *  remove(Object o)
     *   *  unlink()
     *  get(int index)
     *   *  node(int index)
 *  总结

# 什么是LinkedList？ #

LinkedList是一种双向链表。那什么是双向链表？根据双向链表的特点就是会有头节点和尾节点，并且节点之间是通过前驱指针和后继指针来维护关系的，而不是像数组那样通过上下标来维护节点之间的关系的。也就是说双向链表即可以从头到尾遍历，也可以从尾到头遍历

# LinkedList与ArrayList的区别 #

大致区别如下：

1、ArrayList是基于动态数组的数据结构，LinkedList是基于链表的数据结构

2、对于随机访问 get() 和 set() 操作，ArrayList优于LinkedList，因为LinkedList没有继承RandomAccess，而且LinkedList要移动指针

3、对于add（新增）操作和remove（删除）操作，LinkedList比较占优势，因为ArrayList要移动数据

# LinkedList继承了哪些类与接口？ #

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

LinkedList 类继承了 AbstractSequentialList 类，并实现了 List、Deque、Cloneable、Serializable

# LinkedList中主要的成员变量 #

// 初始化链表的长度为0
    transient int size = 0;
    
    // 指向头节点的变量
    transient Node<E> first;
    
    // 指向尾节点的变量
    transient Node<E> last;

# LinkedList的构造方法 #

## LinkedList() ##

// 创建一个空的构造方法
    public LinkedList() { 
    }

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

// 创建一个指定Collection对象作为参数的构造函数，元素的顺内由这个对象迭代返回的顺序决定
    public LinkedList(Collection<? extends E> c) { 
        this();
        addAll(c);
    }

### addAll(Collection<? extends E> c)方法 ###

// 将集合中的所有元素从指定的位置开始插入这个列表
    public boolean addAll(Collection<? extends E> c) { 
        return addAll(size, c);
    }

### addAll(int index, Collection<? extends E> c)方法 ###

public boolean addAll(int index, Collection<? extends E> c) { 
        
        // 判断下标元素是否在链表的长度范围之内
        checkPositionIndex(index);
    
        // 将集合转换为Object数组
        Object[] a = c.toArray();
        
        // 计算Object数组的长度
        int numNew = a.length;
        
        // 如果Object数组长度为0
        if (numNew == 0)
            // 返回布尔值false
            return false;
    
        // pred节点为succ节点的前驱
        Node<E> pred, succ;
        
        // 如果下标等于链表长度的时候
        if (index == size) { 
            // succ节点指向为null
            succ = null;
            // pred节点指向尾节点
            pred = last;
        } else { 
            // 否则如果下标不等于链表长度的话，那么succ节点就是node()方法通过下标索引获得
            succ = node(index);
            // 获得链表中的对应的节点对象
            pred = succ.prev;
        }
    
        // 遍历要添加内容的数组
        for (Object o : a) { 
            @SuppressWarnings("unchecked") E e = (E) o;
            // 创建新的节点，将遍历的值包装成Node节点
            Node<E> newNode = new Node<>(pred, e, null);
            
            // 如果前驱节点为null
            if (pred == null)
                // 那么新的节点就是头节点
                first = newNode;
            else
                // 否则pred指向新创建的节点
                pred.next = newNode;
            // pred节点往后移动一位
            pred = newNode;
        }
    
        // 因为pred节点是succ节点的前驱节点，反过来也就是说succ是pred的后继节点
        // 所以如果succ为null，表示pred为尾节点
        if (succ == null) { 
            last = pred;
        } else { 
            /** * 否则如果succ不是尾节点，那么只要保证pred节点是succ节点的前驱节点、 succ节点是pred的后继节点这种双向链表的关系就可以了 */
            pred.next = succ;
            succ.prev = pred;
        }
    
        // 元素个数增加
        size += numNew;
        modCount++;
        return true;
    }

### checkPositionIndex(int index)方法 ###

private void checkPositionIndex(int index) { 
        if (!isPositionIndex(index))
            // 抛出 IndexOutOfBoundsException 异常
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

### isPositionIndex(int index)方法 ###

private boolean isPositionIndex(int index) { 
        // 这个这么简单就不解释了吧
        return index >= 0 && index <= size;
    }

# Node节点 #

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

# LinkedList的常用方法 #

## add(E e) ##

// 使用双向链表的尾插法
    public boolean add(E e) { 
        // 将元素插入到链表尾部
        linkLast(e);
        return true;
    }

### linkLast(E e) ###

// 插入的节点为尾节点
    void linkLast(E e) { 
        // 创建一个节点并初始化为尾节点
        final Node<E> l = last;
        
        // 初始化新的节点，前驱的节点为l，后继节点为null
        final Node<E> newNode = new Node<>(l, e, null);
        
        // 因为是在链表的尾部插入节点，所以新的节点作为尾节点（这个不难理解）
        last = newNode;
        
        // l节点作为newNode节点的前驱节点，如果l为空，则说明newNode前驱节点为空
        if (l == null)
            // 在双向链表中，前驱节点为空，那么该节点为头节点
            first = newNode;
        else
            // 否则 l 的下一个节点指向该节点
            l.next = newNode;
        
        // 链表长度+1
        size++;
        modCount++;
    }

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

// 指定位置插入元素
    public void add(int index, E element) { 
        // 判断下标索引是否在链表长度范围内（上述讲到过）
        checkPositionIndex(index);
    
        // 如果下标索引等于链表长度
        if (index == size)
            // 则采用尾插法（刚刚讲到过）
            linkLast(element);
        else
            // 否则采用头插法
            linkBefore(element, node(index));
    }

### linkBefore() ###

// 插入的节点为头节点，在节点succ之前插入元素e
    void linkBefore(E e, Node<E> succ) { 
        // assert succ != null;
        // succ节点的前驱节点为pred
        final Node<E> pred = succ.prev;
        
        // 初始化新的前驱节点为pred，后继节点为succ（简单地说就是在pred和succ节点之间插入元素）
        final Node<E> newNode = new Node<>(pred, e, succ);
        
        // 后继节点为succ，succ的前驱节点为newNode
        succ.prev = newNode;
        
        // 如果pred为null
        if (pred == null)
            // 则newNode为头节点
            first = newNode;
        else
            // 否则pred的下一个节点指向newNode
            pred.next = newNode;
        // 链表长度+1
        size++;
        modCount++;
    }

## remove(Object o) ##

// 删除元素
    public boolean remove(Object o) { 
        /** 通过双向链表的前后关系，遍历双向链表。 * 判断是否存在元素和要删除的元素相同。 * 如果遍历到了，那么就删除元素，并且返回true */
        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;
                }
            }
        }
        // 如果没遍历到，那么就返回false
        return false;
    }

### unlink() ###

// 删除非空节点
    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;
    
        // 如果前驱节点pred为null
        if (prev == null) { 
            // 表示当前要删除的节点为头节点，让pred的后继节点作为头节点
            first = next;
        } else { 
            // 否则直接使用双向链表删除节点
            prev.next = next;
            // 将删除节点x的前驱节点设置为null
            x.prev = null;
        }
    
        // 如果后继节点为null
        if (next == null) { 
            // 表示当前删除的节点为尾节点，将前驱节点作为尾节点
            last = prev;
        } else { 
            // 否则如果后继节点不为null，使用双向链表删除节点
            next.prev = prev;
            // 将删除节点x的后继节点设置为null
            x.next = null;
        }
    
        // 将删除节点的值设置为null，方便垃圾回收
        x.item = null;
        
        // 链表长度-1
        size--;
        modCount++;
        return element;
    }

## get(int index) ##

// 获取下标元素
    public E get(int index) { 
        // 判断下标是否在链表长度范围内（上述讲到过）
        checkElementIndex(index);
        // 获取下标节点，返回节点的值
        return node(index).item;
    }

### node(int index) ###

// 获取下标节点
    Node<E> node(int index) { 
        // assert isElementIndex(index);
    
        // 判断下标索引是靠近头节点还是尾节点
        if (index < (size >> 1)) { 
            // 获取头节点
            Node<E> x = first;
            
            // 遍历index的节点
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else { 
            // 获取尾节点
            Node<E> x = last;
            
            // 遍历index的节点
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

# 总结 #

1、LinkedList 添加的元素在取的时候与添加的时候的顺序一致。因为向双向链表的尾部添加元素，然后按照头节点顺序遍历获取，所以一致

2、LinkedList 允许添加重复元素

3、LinkedList 不是线程安全的集合

4、LinkedList 允许添加 null 元素

5、add 方法插入元素是在双向链表的尾部插入

6、get 方法遍历双向链表，先判断下标靠近头节点还是尾节点，这样会减少多余的循环