• LinkedList介绍
  • 1. LinkedList 简介
    • 1.1 实现细节
      • 1.1.1 实现和继承关系
      • 1.1.2 底层实现
        • 1.1.2.1 主要成员
        • 1.1.2.2 方法分类
  • 2. LinkedList 高级特性

LinkedList介绍

1. LinkedList 简介

  LinkedList是双向链表,大致长下面的样子

1.1 实现细节

  基于JDK 1.8版本;
  public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

1.1.1 实现和继承关系

• 继承 抽象类AbstractSequentialList,它也可以被当作堆栈、队列或双端队列进行操作;
• 实现 List 接口，能对它进行队列操作。
• 实现 Cloneable接口,即覆盖了clone()方法,能被克隆;
• 实现 java.io.Serializable 接口,支持序列化,能通过序列化去传输;
• 实现 Deque 接口，即能将LinkedList当作双端队列使用

 [继承关系]
 java.lang.Object
   ↳     java.util.AbstractCollection<E>
         ↳     java.util.AbstractList<E>
               ↳     java.util.AbstractSequentialList<E>
                     ↳     java.util.LinkedList<E>

1.1.2 底层实现

1.1.2.1 主要成员

• 节点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;
        }
    }
  //链表由递归构成,双向节点存在一个prev的指向,指向上一个节点;
  //以及一个next的指向,指向下一个节点;
  //E item 说明保存的元素类型为泛型类型;

• 头结点[即链表第一个节点]

   /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

• 尾节点[即链表最后一个节点]

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

1.1.2.2 方法分类

  LinkedList实现了List和Deque接口,源代码中具备了实现List和Queue的特性;
  重点来看下LinkedList是如何实现栈(Stack)和Queue(队列)的功能的,主要体现在它的方法分类上:

• LinkedList中等效 Queue方法 | Queue队列方法 | LinkedList等效方法 | 作用 | 返回值 | 非空判断 | | —- | —- | —- | —- | —- | | add(e) | addLast(e) | 队列尾部添加元素 | void | false | | offer(e) | offerLast(e) | 队列尾部添加元素 | boolean | false | | remove() | removeFirst() | 移除队列头部元素 | 泛型E | true | | poll() | pollFirst() | 移除队列头部元素 | 泛型E | false | | element() | getFirst() | 获取队列头部元素 | 泛型E | true | | peek() | peekFirst() | 获取队列头部元素 | 泛型E | false |

• LinkedList中等效Stack的方法 | Stack栈方法 | LinkedList等效方法 | 实质调用 | 作用 | 返回值 | 非空判断 | | —- | —- | —- | —- | —- | —- | | push(e) | push(e) | addFirst | 栈中压入元素 | void | false | | pop(e) | pop(e) | removeFirst | 栈中弹出元素 | void | false | | peek(e) | peek(e) | peek(e) | 获取队列头部元素 | void | false |

2. LinkedList 高级特性

• LinkedList线程不安全性
• LinkedList模拟队列,栈实现数据结构操作(TODO :之后遇到会调重点的举例说明)