LinkedList底层原理

2023-12-28 11:45:09

LinkedList在Java中是一个实现List接口的集合类,它的底层数据结构是一个双向链表。

  1. 节点(Node)结构: LinkedList中的每个元素都是一个内部类Node的实例。Node类通常包含三个主要部分:

    • item:存储元素对象的引用。
    • prev:指向前一个节点的引用。
    • next:指向后一个节点的引用。
    • 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;
              }
          }

  2. 主要成员变量

    • transient int size: 用于存储链表中元素的数量。
    • transient Node first: 指向链表的第一个节点(头节点)。
    • transient Node last: 指向链表的最后一个节点(尾节点)。
  3. 添加元素

    • addFirst(E e): 在链表的开头添加新元素。这涉及到更新first节点,并将新节点的next指向原first节点,原first节点的prev指向新节点。
    • addLast(E e): 在链表的末尾添加新元素。这涉及到更新last节点,并将原last节点的next指向新节点,新节点的prev指向原last节点。
    • add(int index, E element): 在指定索引位置插入新元素。这需要从头节点开始遍历到指定位置,然后进行相应的节点连接操作。
  4. 删除元素

    • removeFirst(): 删除并返回链表的第一个元素。这涉及到更新first节点为原first节点的下一个节点,并将原first节点的next节点的prev引用设为null。
    • removeLast(): 删除并返回链表的最后一个元素。这涉及到更新last节点为原last节点的前一个节点,并将原last节点的prev节点的next引用设为null。
    • remove(Object o): 删除首次出现的指定元素。这需要遍历链表,找到匹配的元素后进行类似的节点连接操作。
  5. 访问元素

    • get(int index): 返回指定索引位置的元素。这需要从头节点开始遍历到指定位置,然后返回该位置节点的item
    • set(int index, E element): 替换指定索引位置的元素。这需要先通过get方法找到该位置的节点,然后更新其item字段。
  6. 迭代: 由于LinkedList是双向链表,它支持双向迭代。迭代器可以从前向后或从后向前遍历链表。

????????LinkedList的主要优点包括高效的元素插入和删除(尤其是在列表的两端),而缺点是在中间进行元素访问时可能效率较低,因为需要从头或尾开始遍历链表。此外,LinkedList的空间开销比ArrayList等基于数组的集合略大,因为它需要额外的存储空间来保存节点之间的链接。

文章来源:https://blog.csdn.net/g877835148/article/details/135260349
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。