LinkedList相关知识总结_liankedlist常考知识点

一、概述

LinkedList 是链表实现的线性表（双链表）。是 Java 集合中比较常用的数据结构，与 ArrayList 一样，实现了 List 接口，只不过 ArrayList 是基于数组实现的，遍历时很快，但是插入、删除时都需要移动后面的元素，效率略差些。而 LinkedList 是基于链表实现的，插入、删除时只需要改变前后两个节点指针指向即可。所以 LinkedList 插入和删除方面要优于 ArrayList，而随机访问上ArrayList 性能更好。

除了 List 接口之外，LinkedList 还实现了 Deque，Cloneable，Serializable 三个接口。这说明该数据结构支持队列，克隆和序列化操作的。与 ArrayList 一样，允许 null 元素的存在，且是不支持多线程的。

二、特征

1、数据是按照插入有序，输出顺序与输入顺序一致

2、数据是可以重复插入的

3、集合是可以存储null的

4、底层采用的数据结构是双向链表

5、要找到某个结点，必须从头开始遍历。（查询慢，增删快）

三、

1.继承关系

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

AbstractSequentialList抽象类继承自AbstractList，是对常见的方法做了实现，便于子类直接复用

该接口也实现了list借口，能够实现克隆，实现序列化

实现了deque接口，而该接口是一个双端队列接口，LinkedList也是Queue接口的实现类，而且可以借助于该队列实现队列、可以实现栈

Deque提供了特定方法如下：

提供了从头、从尾的增删改查操作

 2.属性和默认值

LinkedList底层是一个双向链表

//定义了集合中数据的格式
transient int size = 0;
//头节点位置
    transient Node<E> first;
//尾节点位置
    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;
        }
    }

3.构造函数

//无参构造函数
public LinkedList() {
    }
 
//通过Collection集合来实例化LInkedList的实例
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

四、常见的方法分析

1.add:添加元素

    public boolean add(E e) {
        linkLast(e);
        return true;
    }
 
    void linkLast(E e) {
        final Node<E> l = last;
        //新构造node节点以链表的尾节点作为前驱，将新节点插入到链表的尾部，尾插法
        final Node<E> newNode = new Node<>(l, e, null);
        //将新节点作为尾节点
        last = newNode;
        
        if (l == null)
            //当前插入的是第一个节点，first=last=newNode
            first = newNode;
        else
            //当前链表上已经存在节点
            l.next = newNode;
        size++;
        modCount++;
    }

添加元采用尾将尾节点插入链表，将size+1

2.remove：删除元素

本质上是双向链表的删除节点的过程

    public boolean remove(Object o) {
        //删除的元素判断是否为null，判断相等逻辑会不同 o==null? ==:equals
        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;
    }
 
//删除双向链表的节点逻辑
    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;
    }

3.get()：获取节点元素

    public E get(int index) {
        //判断位置的合法性
        checkElementIndex(index);
        return node(index).item;
    }
    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }
 
//从链表中的位置index来找到节点Node
   Node<E> node(int index) {
       //通过二分查找来确定要查找元素的位置，在size/2前半部分，采用从前往后查找，否则，从后往前查找
        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;
        }
    }

总结：

1. 从源码可以看出 LinkedList 是基于链表实现的。

2. 在查找和删除某元素时，区分该元素为 null和不为 null 两种情况来处理，LinkedList 中允许元素为 null。

3. 基于链表实现不存在扩容问题。

4. 查找时先判断该节点位于前半部分还是后半部分，加快了速度

5. 因为基于链表，所以插入删除极快，查找比较慢。

6. 实现了栈和队列的相关方法，所以可作为栈，队列，双端队列来用。

ArrayList和LinkedList区别：

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

2、对于随机访问的get和set方法，ArrayList有优于LInkedList，因为LInkedList要移动指针

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

应用场景：

ArrayList使用在查询比较多场景，而LinkedList适用于插入删除比较多场景