LinkedList详解

柔情只为你懂 2022-05-31 06:49 141阅读 0赞

LinkedList

> 1、 类结构

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

1.  LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
2.  LinkedList 实现 List 接口，能对它进行队列操作。
3.  LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
4.  LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
5.  LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
6.  LinkedList 是非同步的。非线程安全的

> 2、 数据结构

成员变量  
![70][]

transient int size = 0; //容量
    transient Node<E> first;// 第一个节点
    transient Node<E> last;//最后一个节点

从上图可以看出，LinkedList内部是一个双端队列结构，成员变量first指向链表头部Node对象，成员变量last指向链表尾部Node对象。  
Node对象是LinkedList的一个内部类

private static class Node<E> {
            E item; // 当前对象值
            Node<E> next;// 下一个Node节点
    Node<E> prev;// 上一个Node节点
                                    // 构造函数
            Node(Node<E> prev, E element, Node<E> next) {
                this.item = element;
                this.next = next;
                this.prev = prev;
            }
    }

从Node对象包含3个变量，当前元素，下一个节点、上一个节点。影城，从Node的定义可以看出链表是一个双端链表的结构

3、 构造函数  
和ArrayList差不多，一个无参数，一个初始化集合的有参构造函数

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

当使用第二个构造方法时，会调用addAll()方法将集合中的元素添加到链表中，添加的操作后面会详细介绍。  
4、 添加元素

// 添加一个元素，默认添加在最后面
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    // 指定位置添加一个元素
     public void add(int index, E element) {
        checkPositionIndex(index);
    
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
    
    // 在前面添加一个元素 
    public void addFirst(E e) {
        linkFirst(e);
    }
    
    // 在后面添加一个元素
    public void addLast(E e) {
        linkLast(e);
    }
    
    
    // 添加一个集合，默认添加到最后面
    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;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }
    
        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;
    }
    
    // 讲元素推到第一个位置，等价于addFirst
    public void push(E e) {
        addFirst(e);
    }
    
    // 将元素堆到最后一个位置，等价于add，addLast
    public boolean offer(E e) {
        return add(e);
    }
    // 讲元素推到第一个位置等价于push
    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }
    // 将元素堆到最后一个位置，等价于offer
    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

5、 删除

// 队列移除第一个，返回第一个对象
    public E remove() {
        return removeFirst();
    }
    // 栈弹出第一个, 返回第一个对象
    public E pop() {
        return removeFirst();
    }
    Remove()和pop()可以很明显看出是等价的
    
    // 检测删除第一个元素，返回移除的元素
    public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
    // 检测删除第一个元素，返回移除的元素
    public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
    // 检测删除最后一个元素，返回移除的元素
    public E pollLast() {
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }

6、 修改

// 修改下标为index的值为element，并返回原来的旧值
    public E set(int index, E element) {
        checkElementIndex(index);
        Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

7、 查询、获取

LinkedList<String> all = new LinkedList<>();
       all.add("all0");
       all.add("all1");
       all.add("all2");
       all.add("all3");
       System.out.println(all.get(1));// 得到第下标为1的元素
       System.out.println(all.poll());// 移除第一个元素，并将第一个元素返回
       System.out.println(all.peek());//检索，但是不删除，这个列表的头(第一个元素)。
       System.out.println(all.element());//检索，但是不删除，这个列表的头(第一个元素)。

打印结果：all1、all0、all1、all1

[70]: /images/20220531/2f25bef269bb4f7da9400bad18537992.png