1.初始化 复制代码 public LinkedList() { } 复制代码 并未开辟任何类似于数组一样的存储空间，那么链表是如何存储元素的呢？ 2.Node类型 存储到链表中的元素会被封装为一个Node类型的结点。并且链表只需记录第一个结点的位置和最后一个结点的位置。然后每一个结点，前后连接，就可以串起来变成一整个链表。 复制代码 transient Node first;//指向链表的第一个结点 transient Node last;//指向链表的最后一个结点 //LinkedList中有一个内部类Node类型 private static class Node { E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } } 复制代码 3.添加元素 复制代码 public boolean add(E e) { //默认链接到链表末尾 linkLast(e); return true; } void linkLast(E e) { //用l记录当前链表的最后一个结点对象 final Node l = last; //创建一个新结点对象，并且指定当前新结点的前一个结点为l final Node newNode = new Node<>(l, e, null); //当前新结点就变成了链表的最后一个结点 last = newNode; if (l == null) 　　　　 //如果当前链表是空的，那么新结点对象，同时也是链表的第一个结点 first = newNode; else //如果当前链表不是空的，那么最后一个结点的next就指向当前新结点 l.next = newNode; //元素个数增加 size++; //修改次数增加 modCount++; } 复制代码 4.删除元素 复制代码 public boolean remove(Object o) { //分o是否是null讨论，从头到尾找到要删除的元素o对应的Node结点对象，然后删除 if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); return true; } } } return false; } E unlink(Node x) { final E element = x.item; //用next记录被删除结点的后一个结点 final Node next = x.next; //用prev记录被删除结点的前一个结点 final Node prev = x.prev; if (prev == null) { //如果删除的是第一个结点，那么被删除的结点的后一个结点将成为第一个结点 first = next; } else { //否则被删除结点的前一个结点的next应该指向被删除结点的后一个结点 prev.next = next; //断开被删除结点与前一个结点的关系 x.prev = null; } if (next == null) { //如果删除的是最后一个结点，那么被删除结点的前一个结点将变成最后一个结点 last = prev; } else { //否则被删除结点的后一个结点的prev应该指向被删除结点的额前一个结点 next.prev = prev; //断开被删除结点与后一个结点的关系 x.next = null; } //彻底把被删除结点变成垃圾对象 x.item = null; //元素个数减少 size--; //修改次数增加 modCount++; return element; } 复制代码 5.指定位置插入元素 复制代码 public void add(int index, E element) { //检查索引位置的合理性 checkPositionIndex(index); if (index == size) //如果位置是在最后，那么链接到链表的最后 linkLast(element); else //否则在链表中间插入 //node(index)表示找到index位置的Node对象 linkBefore(element, node(index)); } void linkBefore(E e, Node succ) { // pred记录被插入位置的前一个结点 final Node pred = succ.prev; //构建一个新结点 final Node newNode = new Node<>(pred, e, succ); //把新结点插入到succ的前面 succ.prev = newNode; //如果被插入点是链表的开头，那么新结点变成了链表头 if (pred == null) first = newNode; else //否则pred的next就变成了新结点 pred.next = newNode; //元素个数增加 size++; //修改次数增加 modCount++; } 复制代码 6.总结 对于频繁的插入或删除元素的操作，建议使用LinkedList类，效率较高。因为不涉及到移动元素，只需要修改前后结点的关系。也不需要涉及到扩容 此类虽然提供按照索引查找与操作的方法，但是效率不高，如果需要按索引操作，那么建议使用动态数组https://www.cnblogs.com/duoduotouhenying/p/10136441.html