## 1. 概述

LinkedList 内部是一个双向链表，并且实现了 List 接口和 Deque 接口，因此它也具有 List 的操作以及双端队列和栈的性质。双向链表的结构如下：

## 2. 代码分析

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

``// list 的长度transient int size = 0;// 链表头结点transient Node<E> first;// 链表尾结点``transient Node<E> last;``

### 2.2 构造器

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

``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;elsepred.next = newNode;pred = newNode;}// 若插入到末尾，则数组中的最后一个元素就是尾结点if (succ == null) {last = pred;} else {// 若插入到指定位置，将数组中最后一个元素与下一个位置关联起来pred.next = succ;succ.prev = pred;}size += numNew;modCount++;return true;``}``

``Node<E> node(int index) {// assert isElementIndex(index);// 若下标在前一半，则从前往后遍历；否则从后往前遍历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;}``}``

``public E get(int index) {checkElementIndex(index);return node(index).item;``}``

### 2.3 常用方法

``public boolean offerLast(E e) {addLast(e);return true;}public void addLast(E e) {linkLast(e);}public boolean add(E e) {linkLast(e);return true;``}``

``void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;// 若链表为空，则新结点为头结点if (l == null)first = newNode;// 若链表不为空，将新结点插入到链表尾部elsel.next = newNode;size++;modCount++;``}``

``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 removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);``}``

``private E unlinkFirst(Node<E> f) {// assert f == first && f != null;final E element = f.item;final Node<E> next = f.next;f.item = null;f.next = null; // help GCfirst = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;return element;``}``

``public void push(E e) {addFirst(e);}public E pop() {return removeFirst();``}``

## 3. 线程安全性

``public ListIterator<E> listIterator(int index) {checkPositionIndex(index);return new ListItr(index);}private class ListItr implements ListIterator<E> {private Node<E> lastReturned;private Node<E> next;private int nextIndex;// 初始化时二者是相等的private int expectedModCount = modCount;ListItr(int index) {// assert isPositionIndex(index);next = (index == size) ? null : node(index);nextIndex = index;}public E next() {checkForComodification();if (!hasNext())throw new NoSuchElementException();lastReturned = next;next = next.next;nextIndex++;return lastReturned.item;}public void remove() {checkForComodification();if (lastReturned == null)throw new IllegalStateException();Node<E> lastNext = lastReturned.next;unlink(lastReturned);if (next == lastReturned)next = lastNext;elsenextIndex--;lastReturned = null;expectedModCount++;}// ...// 是否有其他线程对当前对象进行结构修改final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}``}``

## 4. 小结

1. LinkedList 内部是「双向链表」，同时实现了 List 接口和 Deque 接口，因此也具备 List、双端队列和栈的性质；
2. 线程不安全。

1 声望

0 粉丝

0 条评论

## 1. 概述

LinkedList 内部是一个双向链表，并且实现了 List 接口和 Deque 接口，因此它也具有 List 的操作以及双端队列和栈的性质。双向链表的结构如下：

## 2. 代码分析

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

``// list 的长度transient int size = 0;// 链表头结点transient Node<E> first;// 链表尾结点``transient Node<E> last;``

### 2.2 构造器

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

``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;elsepred.next = newNode;pred = newNode;}// 若插入到末尾，则数组中的最后一个元素就是尾结点if (succ == null) {last = pred;} else {// 若插入到指定位置，将数组中最后一个元素与下一个位置关联起来pred.next = succ;succ.prev = pred;}size += numNew;modCount++;return true;``}``

``Node<E> node(int index) {// assert isElementIndex(index);// 若下标在前一半，则从前往后遍历；否则从后往前遍历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;}``}``

``public E get(int index) {checkElementIndex(index);return node(index).item;``}``

### 2.3 常用方法

``public boolean offerLast(E e) {addLast(e);return true;}public void addLast(E e) {linkLast(e);}public boolean add(E e) {linkLast(e);return true;``}``

``void linkLast(E e) {final Node<E> l = last;final Node<E> newNode = new Node<>(l, e, null);last = newNode;// 若链表为空，则新结点为头结点if (l == null)first = newNode;// 若链表不为空，将新结点插入到链表尾部elsel.next = newNode;size++;modCount++;``}``

``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 removeFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return unlinkFirst(f);``}``

``private E unlinkFirst(Node<E> f) {// assert f == first && f != null;final E element = f.item;final Node<E> next = f.next;f.item = null;f.next = null; // help GCfirst = next;if (next == null)last = null;elsenext.prev = null;size--;modCount++;return element;``}``

``public void push(E e) {addFirst(e);}public E pop() {return removeFirst();``}``

## 3. 线程安全性

``public ListIterator<E> listIterator(int index) {checkPositionIndex(index);return new ListItr(index);}private class ListItr implements ListIterator<E> {private Node<E> lastReturned;private Node<E> next;private int nextIndex;// 初始化时二者是相等的private int expectedModCount = modCount;ListItr(int index) {// assert isPositionIndex(index);next = (index == size) ? null : node(index);nextIndex = index;}public E next() {checkForComodification();if (!hasNext())throw new NoSuchElementException();lastReturned = next;next = next.next;nextIndex++;return lastReturned.item;}public void remove() {checkForComodification();if (lastReturned == null)throw new IllegalStateException();Node<E> lastNext = lastReturned.next;unlink(lastReturned);if (next == lastReturned)next = lastNext;elsenextIndex--;lastReturned = null;expectedModCount++;}// ...// 是否有其他线程对当前对象进行结构修改final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}``}``

## 4. 小结

1. LinkedList 内部是「双向链表」，同时实现了 List 接口和 Deque 接口，因此也具备 List、双端队列和栈的性质；
2. 线程不安全。