\u57fa\u7840\u4e0d\u7262，\u5730\u52a8\u5c71\u6447\u3002<\/p>\n
\u4e0a\u4e00\u671f\u6211\u4eec\u5f7b\u5e95\u641e\u61c2\u4e86 ArrayList \u5e95\u5c42\u6570\u7ec4：<\/p>\n
\u67e5\u8be2\u5feb\u3001\u4e2d\u95f4\u589e\u5220\u6162\u3001\u9700\u8981\u6269\u5bb9\u3001\u5e95\u5c42\u8fde\u7eed\u5185\u5b58\u3002<\/p>\n
\u90a3\u65e2\u7136\u6570\u7ec4\u6709\u589e\u5220\u6162\u7684\u77ed\u677f，Java\u9760\u4ec0\u4e48\u5f25\u8865？<\/p>\n
\u7b54\u6848\u5c31\u662f\u4eca\u5929\u7684\u4e3b\u89d2：LinkedList \u53cc\u5411\u94fe\u8868\u3002<\/p>\n
\u5f88\u591a\u65f6\u5019\u6211\u4eec\u5728\u5de5\u4f5c\u4e2d\u6700\u5927\u7684\u95ee\u9898：\u6c38\u8fdc\u51ed\u611f\u89c9\u4e71\u9009\u96c6\u5408\u3002<\/p>\n
\u770b\u5b8c\u8fd9\u7bc7，\u4f60\u5f7b\u5e95\u5f04\u61c2：<\/p>\n
\u2705 \u4e3a\u4ec0\u4e48 LinkedList \u589e\u5220\u5feb？<\/p>\n
\u2705 \u4e3a\u4ec0\u4e48 LinkedList \u67e5\u8be2\u6162？<\/p>\n
\u2705 \u4e1a\u52a1\u573a\u666f\u5230\u5e95\u8be5\u7528 ArrayList \u8fd8\u662f LinkedList？<\/p>\n
\u5168\u7a0b\u5927\u767d\u8bdd + \u6781\u7b80\u6e90\u7801 + \u7cbe\u51c6\u5bf9\u6bd4，\u96f6\u57fa\u7840\u4e5f\u80fd\u5f7b\u5e95\u901a\u900f\u3002<\/p>\n
ArrayList：\u5e95\u5c42\u662f\u300c\u6570\u7ec4\u300d<\/p>\n
LinkedList：\u5e95\u5c42\u662f\u300c\u53cc\u5411\u94fe\u8868\u300d<\/p>\n
\u4e0d\u7528\u8fde\u7eed\u5185\u5b58，\u6bcf\u4e00\u4e2a\u5143\u7d20\u90fd\u662f\u4e00\u4e2a\u72ec\u7acb\u8282\u70b9\u3002<\/p>\n
\u6bcf\u4e2a\u8282\u70b9\u53ea\u8bb0\u5f55\u4e09\u4ef6\u4e8b：<\/p>\n
\u901a\u4fd7\u6bd4\u55bb：<\/p>\n
ArrayList \u50cf\u4e00\u6392\u7d27\u5bc6\u8fde\u5750\u7684\u5ea7\u4f4d，\u4e2d\u95f4\u8d70\u4eba，\u540e\u9762\u6240\u6709\u4eba\u90fd\u8981\u5f80\u524d\u632a\u3002<\/p>\n
LinkedList \u50cf\u4e00\u4e32\u73cd\u73e0\u9879\u94fe，\u62c6\u6389\u4e2d\u95f4\u4e00\u9897\u3001\u63d2\u5165\u4e00\u9897，\u53ea\u9700\u8981\u65ad\u5f00\u4e24\u8fb9\u7ef3\u5b50，\u5176\u4ed6\u73cd\u73e0\u5b8c\u5168\u4e0d\u7528\u52a8\u3002<\/p>\n
public class LinkedList<E>
\n extends AbstractSequentialList<E>
\n implements List<E>, Deque<E>, Cloneable, java.io.Serializable<\/p>\n
\u91cd\u70b9\u770b\u4e24\u4e2a：<\/p>\n
\u5b83\u6709\u51e0\u4e2a\u7279\u70b9：<\/p>\n
\u4f60\u53ef\u4ee5\u628a\u5b83\u60f3\u8c61\u6210\u4e00\u7fa4\u624b\u62c9\u624b\u7684\u5c0f\u670b\u53cb：<\/p>\n
null <- A <-> B <-> C -> null
\n first last<\/p>\n
\u6bcf\u4e2a\u5c0f\u670b\u53cb\u90fd\u77e5\u9053：<\/p>\n
LinkedList \u6700\u6838\u5fc3\u7684\u6210\u5458\u53ea\u6709\u4e09\u4e2a：<\/p>\n
transient int size = 0;
\ntransient Node<E> first;
\ntransient Node<E> last;<\/p>\n
\u6bcf\u4e2a\u8282\u70b9\u957f\u8fd9\u6837（LinkedList \u6240\u6709\u5143\u7d20，\u90fd\u662f\u4e0b\u9762\u8fd9\u4e2a Node \u8282\u70b9）：<\/p>\n
\/\/ \u53cc\u5411\u94fe\u8868\u8282\u70b9
\nprivate static class Node<E> {
\n E item; \/\/ \u5f53\u524d\u5143\u7d20
\n Node<E> next; \/\/ \u4e0b\u4e00\u4e2a\u8282\u70b9
\n Node<E> prev; \/\/ \u4e0a\u4e00\u4e2a\u8282\u70b9
\n}<\/p>\n
\u7ffb\u8bd1\u6210\u4eba\u8bdd：<\/p>\n
Node = \u5f53\u524d\u5143\u7d20 + \u524d\u4e00\u4e2a\u8282\u70b9 + \u540e\u4e00\u4e2a\u8282\u70b9<\/p>\n
\u6240\u4ee5 LinkedList \u7684\u6bcf\u4e2a\u5143\u7d20，\u90fd\u8981\u989d\u5916\u7ef4\u62a4\u4e24\u4e2a\u5f15\u7528：prev \u548c next\u3002<\/p>\n
\u8fd9\u4e5f\u662f\u5b83\u5185\u5b58\u5f00\u9500\u5927\u7684\u539f\u56e0\u3002<\/p>\n
\u8fd9\u5c31\u662f\u53cc\u5411\u94fe\u8868\u7684\u7cbe\u9ad3：\u524d\u540e\u4e92\u901a\u3002<\/p>\n
\u6240\u4ee5\u5b83\u53ef\u4ee5\u4ece\u5934\u904d\u5386\u3001\u4e5f\u53ef\u4ee5\u4ece\u5c3e\u904d\u5386，\u589e\u5220\u53ea\u9700\u8981\u6539\u5f15\u7528，\u4e0d\u9700\u8981\u79fb\u52a8\u5927\u91cf\u5143\u7d20\u3002<\/p>\n
\u5e73\u65f6\u6211\u4eec\u6700\u5e38\u7528\u7684：<\/p>\n
list.add("A");<\/p>\n
\u6e90\u7801\u6700\u7ec8\u4f1a\u8d70\u5230：<\/p>\n
public boolean add(E e) {
\n linkLast(e);
\n return true;
\n}<\/p>\n
linkLast \u662f\u5c3e\u90e8\u63d2\u5165\u6838\u5fc3：<\/p>\n
void linkLast(E e) {
\n final Node<E> l = last;
\n final Node<E> newNode = new Node<>(l, e, null);
\n last = newNode;<\/p>\n
if (l == null)
\n first = newNode;
\n else
\n l.next = newNode;<\/p>\n
size++;
\n modCount++;
\n}<\/p>\n
\u6b65\u9aa4\u62c6\u89e3：<\/p>\n
\u6240\u4ee5\u5c3e\u90e8\u6dfb\u52a0\u662f O(1) ，\u56e0\u4e3a\u4e0d\u7528\u904d\u5386，\u76f4\u63a5\u6539\u5c3e\u5df4\u3002<\/p>\n
public void addFirst(E e) {
\n linkFirst(e);
\n}<\/p>\n
\u6838\u5fc3：<\/p>\n
private void linkFirst(E e) {
\n final Node<E> f = first;
\n final Node<E> newNode = new Node<>(null, e, f);
\n first = newNode;<\/p>\n
if (f == null)
\n last = newNode;
\n else
\n f.prev = newNode;<\/p>\n
size++;
\n modCount++;
\n}<\/p>\n
\u903b\u8f91\u548c\u5c3e\u90e8\u63d2\u5165\u5bf9\u79f0：<\/p>\n
\u6240\u4ee5\u5934\u90e8\u6dfb\u52a0\u4e5f\u662f O(1) \u3002<\/p>\n
public void add(int index, E element) {
\n checkPositionIndex(index);<\/p>\n
if (index == size)
\n linkLast(element);
\n else
\n linkBefore(element, node(index));
\n}<\/p>\n
\u6ce8\u610f\u8fd9\u91cc\u6709\u4e2a\u5173\u952e\u70b9：<\/p>\n
node(index) \u662f LinkedList \u6162\u7684\u6839\u6e90\u4e4b\u4e00\u3002<\/p>\n
Node<E> node(int index) {
\n if (index < (size >> 1)) {
\n Node<E> x = first;
\n for (int i = 0; i < index; i++)
\n x = x.next;
\n return x;
\n } else {
\n Node<E> x = last;
\n for (int i = size – 1; i > index; i–)
\n x = x.prev;
\n return x;
\n }
\n}<\/p>\n
size >> 1 \u5c31\u662f size \/ 2\u3002<\/p>\n
\u610f\u601d\u5f88\u7b80\u5355：<\/p>\n
\u8fd9\u662f\u4e00\u4e2a\u5c0f\u4f18\u5316，\u4f46\u6539\u53d8\u4e0d\u4e86\u672c\u8d28：<\/p>\n
LinkedList \u968f\u673a\u8bbf\u95ee\u4ecd\u7136\u662f O(n)\u3002<\/p>\n
\u6bd4\u5982\u627e\u7b2c 5000 \u4e2a\u5143\u7d20，\u5373\u4f7f\u4ece\u4e2d\u95f4\u5f00\u59cb，\u4e5f\u8981\u8d70\u51e0\u5343\u6b65\u3002<\/p>\n
\u6240\u4ee5：<\/p>\n
public E get(int index) {
\n checkElementIndex(index);
\n return node(index).item;
\n}<\/p>\n
get(index) \u662f O(n)\u3002<\/p>\n
set(index, element) \u4e5f\u4e00\u6837：<\/p>\n
public E set(int index, E element) {
\n checkElementIndex(index);
\n Node<E> x = node(index);
\n E oldVal = x.item;
\n x.item = element;
\n return oldVal;
\n}<\/p>\n
\u5148\u627e\u5230\u8282\u70b9，\u518d\u6539\u503c\u3002<\/p>\n
\u6ca1\u6709\u8fde\u7eed\u4e0b\u6807，\u60f3\u627e\u7b2c n \u4e2a\u5143\u7d20：\u53ea\u80fd\u4ece\u5934\u8282\u70b9\/\u5c3e\u8282\u70b9\u6328\u4e2a\u904d\u5386，\u76f4\u5230\u627e\u5230\u76ee\u6807，\u901f\u5ea6\u6781\u6162 O(n)<\/p>\n
public E remove(int index) {
\n checkElementIndex(index);
\n return unlink(node(index));
\n}<\/p>\n
\u5148 node(index) \u627e\u5230\u8282\u70b9，\u518d unlink \u5220\u9664\u3002<\/p>\n
unlink \u662f\u5220\u9664\u7684\u6838\u5fc3：<\/p>\n
E unlink(Node<E> x) {
\n final E element = x.item;
\n final Node<E> next = x.next;
\n final Node<E> prev = x.prev;<\/p>\n
if (prev == null) {
\n first = next;
\n } else {
\n prev.next = next;
\n x.prev = null;
\n }<\/p>\n
if (next == null) {
\n last = prev;
\n } else {
\n next.prev = prev;
\n x.next = null;
\n }<\/p>\n
x.item = null;
\n size–;
\n modCount++;
\n return element;
\n}<\/p>\n
\u7ffb\u8bd1\u4e00\u4e0b：<\/p>\n
\u6240\u4ee5：<\/p>\n
public boolean remove(Object o) {
\n if (o == null) {
\n for (Node<E> x = first; x != null; x = x.next) {
\n if (x.item == null) {
\n unlink(x);
\n return true;
\n }
\n }
\n } else {
\n for (Node<E> x = first; x != null; x = x.next) {
\n if (o.equals(x.item)) {
\n unlink(x);
\n return true;
\n }
\n }
\n }
\n return false;
\n}<\/p>\n
\u4ece\u5934\u904d\u5386，\u627e\u5230\u5c31\u5220\u3002\u6240\u4ee5\u4e5f\u662f O(n)\u3002<\/p>\n
\u56e0\u4e3a\u5b83\u5b9e\u73b0\u4e86 Deque，\u6240\u4ee5\u6709\u5f88\u591a\u65b9\u6cd5：<\/p>\n
| \u5934\u90e8\u6dfb\u52a0<\/td>\n | addFirst\u3001offerFirst\u3001push<\/td>\n<\/tr>\n |
| \u5c3e\u90e8\u6dfb\u52a0<\/td>\n | addLast\u3001offerLast\u3001offer<\/td>\n<\/tr>\n |
| \u5934\u90e8\u5220\u9664<\/td>\n | removeFirst\u3001pollFirst\u3001pop<\/td>\n<\/tr>\n |
| \u5c3e\u90e8\u5220\u9664<\/td>\n | removeLast\u3001pollLast<\/td>\n<\/tr>\n |
| \u67e5\u770b\u5934\u90e8<\/td>\n | getFirst\u3001peekFirst\u3001peek<\/td>\n<\/tr>\n |
| \u67e5\u770b\u5c3e\u90e8<\/td>\n | getLast\u3001peekLast<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n \u6bd4\u5982\u5f53\u961f\u5217：<\/p>\n LinkedList<String> queue = new LinkedList<>(); \u5f53\u6808：<\/p>\n LinkedList<String> stack = new LinkedList<>(); \u4e0d\u8fc7\u5b9e\u6218\u91cc，\u5982\u679c\u53ea\u662f\u5f53\u961f\u5217\u6216\u6808，ArrayDeque \u901a\u5e38\u6bd4 LinkedList \u66f4\u5feb\u3001\u66f4\u7701\u5185\u5b58\u3002LinkedList \u7684\u4f18\u52bf\u662f\u5b83\u540c\u65f6\u5b9e\u73b0\u4e86 List \u548c Deque\u3002<\/p>\n \n \u516b\u3001\u904d\u5386 LinkedList \u7684\u6b63\u786e\u59ff\u52bf<\/h3>\n\u8fd9\u662f LinkedList \u6700\u5927\u7684\u5751\u3002<\/p>\n \u9519\u8bef\u5199\u6cd5：<\/p>\n for (int i = 0; i < list.size(); i++) { \u8fd9\u6837\u603b\u590d\u6742\u5ea6\u662f O(n\u00b2) ，\u6570\u636e\u4e00\u591a\u5c31\u6162\u5230\u6000\u7591\u4eba\u751f\u3002<\/p>\n \u6b63\u786e\u5199\u6cd5：<\/p>\n for (E e : list) { \u6216\u8005：<\/p>\n Iterator<E> it = list.iterator(); LinkedList \u7684\u8fed\u4ee3\u5668 ListItr \u5185\u90e8\u6301\u6709 next \u6307\u9488，\u6bcf\u6b21 next() \u53ea\u662f\u5f80\u540e\u8d70\u4e00\u6b65，\u6240\u4ee5\u904d\u5386\u662f O(n)\u3002<\/p>\n \u800c\u4e14\u8fed\u4ee3\u5668\u5220\u9664\u53ea\u9700\u8981\u6539\u6307\u9488，\u4e0d\u9700\u8981\u50cf ArrayList \u90a3\u6837\u79fb\u52a8\u6570\u7ec4\u3002<\/p>\n \u4e5d\u3001\u65b0\u589e\/\u5220\u9664\u4e3a\u4ec0\u4e48\u6bd4 ArrayList \u5feb？\u67e5\u8be2\u4e3a\u4ec0\u4e48\u6bd4ArrayList\u6162？<\/h3>\n |