集合框架有哪些类（集合框架——LinkedList集合源码分析）

时间2025-08-03 09:31:17分类IT科技浏览5459

导读：总结： LinkedList继承自List，具备有序性 LinkedList继承自Deque，具备链表关联性 LinkedList集合进行增删改查操作底层实际是操作Node节点的前后链接关系 LinkedList进行增删操作时，仅需要操作节点的前后链接关系，因此...

总结：

LinkedList继承自List ，具备有序性 LinkedList继承自Deque ，具备链表关联性 LinkedList集合进行增删改查操作底层实际是操作Node节点的前后链接关系 LinkedList进行增删操作时，仅需要操作节点的前后链接关系，因此效率较ArrayList高 LinkedList进行查找操作时，必须从头或者从尾进行查找，因此较底层依靠数组进行存储的ArrayList查找效率低

示例代码

public class LinkedList01 { public static void main(String[] args) { LinkedList linkedList = new LinkedList(); //执行第1步 linkedList.add(1); //执行第2步 linkedList.add(2); //执行第3步 linkedList.add(3); //执行第4步 linkedList.add(1 , new Intger(8)); //执行第8步 linkedList.add(5); linkedList.remove(); //执行第5步 linkedList.remove(2); //执行第6步 linkedList.remove(new Integer(3)); //执行第7步 System.out.println(linkedList); } }

底层代码

第1步（初始化集合） //LinkedList类默认构造器 public LinkedList() {} transient int size = 0; //集合存放对象个数 transient Node<E> first; //集合中第一个节点 transient Node<E> last; //集合中最后一个节点 ... //AbstractSequentialList类默认构造器 protected AbstractSequentialList() {} ... //AbstractList类默认构造器 protected AbstractList() {} protected transient int modCount = 0; ... //AbstractCollection类默认构造器 protected AbstractCollection() {} ... //Object类默认构造器 public Object() {}

结果：还没有存放对象，属于空集合

第2步（往集合中添加一个元素） public boolean add(E e) { //e = 1 linkLast(e); return true; } ... void linkLast(E e) { final Node<E> l = last;//l = null final Node<E> newNode = new Node<>(l, e, null);//创建新的节点，当前节点的prev和next属性均为null ，将存入集合的对象赋值给item last = newNode;//LinkedList集合的last属性指向新节点 if (l == null)//此时i=null ，条件成立 first = newNode;//LinkedList集合的first属性指向新节点 else l.next = newNode; size++;//LinkedList集合的容量自加1 modCount++;//LinkedList集合修改次数自加1 } ...... //Node是LinkedList类的内部类 private static class Node<E> { E item; //LinkedLIst实际存放的对象 Node<E> next; //当前节点的下一个节点 Node<E> prev; //当前节点的前一个节点 Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }

结果：集合中存放1个元素，LinkedList类中first与last属性相同，Node类中prev与next属性为null

第3步（往集合中添加第二个元素） public boolean add(E e) { //e = 2 linkLast(e); return true; } ... void linkLast(E e) { final Node<E> l = last;//l = 1，表示上一个节点 final Node<E> newNode = new Node<>(l, e, null);//创建新的节点，节点的prev属性指向上一个节点，item属性存放当前对象 last = newNode;//LinkedList集合的last属性指向新节点 if (l == null)//此时i！=null，条件不成立 first = newNode; else l.next = newNode;//上一个节点的next属性指向当前节点，即新创建的节点 size++;//LinkedList集合的容量自加1 modCount++;//LinkedList集合修改次数自加1 }

结果：

第4步（往集合中添加第三个元素） public boolean add(E e) { //e = 3 linkLast(e); return true; } ... void linkLast(E e) { final Node<E> l = last;//l = 2 ，表示上一个节点 final Node<E> newNode = new Node<>(l, e, null);//创建新的节点，节点的prev属性指向上一个节点， item属性存放当前对象 last = newNode;//LinkedList集合的last属性指向新节点 if (l == null)//此时i！=null ，条件不成立 first = newNode; else l.next = newNode;//上一个节点的next属性指向当前节点，即新创建的节点 size++;//LinkedList集合的容量自加1 modCount++;//LinkedList集合修改次数自加1 }

结果：

LinkedList添加元素流程示意图第5步（删除集合中第一个元素） public E remove() { return removeFirst(); } ... 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; //将集合中第一个节点的item 属性赋值给element final Node<E> next = f.next; //将集合中第一个节点的next属性赋值给next f.item = null; f.next = null; // help GC first = next; //将原集合中的第二个节点赋给集合的first属性 if (next == null) last = null; else next.prev = null;//将原集合中的第二个节点的prev属性赋值为null size--; //集合元素个数自减1 modCount++; //集合修改次数自加1 return element; //返回被删除的节点item值 } 第6步（根据索引来删除集合中的元素） public E remove(int index) { //index = 2 checkElementIndex(index); //1.嵌套执行下边两个方法①和② ，确定索引正确后继续往下执行 return unlink(node(index)); //2.执行方法③与④ } ... //方法① private void checkElementIndex(int index) { if (!isElementIndex(index)) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } ... //方法② private boolean isElementIndex(int index) { return index >= 0 && index < size; } ... //方法③ Node<E> node(int index) { //index = 2, size = 4 // assert isElementIndex(index); if (index < (size >> 1)) { //index < size/2时 Node<E> x = first; //x记录首个节点 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; } } ... //方法④ E unlink(Node<E> x) { //需要删除的节点 // assert x != null; final E element = x.item; final Node<E> next = x.next; final Node<E> prev = x.prev; if (prev == null) { //对于首个节点的情况 first = next; } else { prev.next = next; x.prev = null; } if (next == null) { //对于尾端节点的情况 last = prev; } else { next.prev = prev; x.next = null; } x.item = null; //此时该节点中的属性item 、prev 、next均为null size--; //集合元素个数自减1 modCount++; //集合修改次数自加1 return element; //返回被删除节点中的内容 } 第7步（根据对象内容来删除集合中的元素） //本方法可以用来删除集合中对象和null public boolean remove(Object o) { o = new Integer(3) if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); return true; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); //调用方法与第6步中流程一致 return true; } } } return false; } 第8步（根据索引位置往集合中添加元素） public void add(int index, E element) { //index=1, element = new Integer(8) checkPositionIndex(index); //检查索引没有问题 if (index == size) //如果索引与集合大小相等 linkLast(element); else linkBefore(element, node(index)); //node(index)方法找到该索引位置的节点，然后采用linkBefore方法在其节点前链接入新的节点 } ... 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; else l.next = newNode; size++; modCount++; } ... void linkBefore(E e, Node<E> succ) { //e = new Integer(8)待链接入的节点，succ为原index位置的节点 // assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。