JDK容器学习之LinkedList:底层存储&读写逻辑

LinkedList的底层结构及读写逻辑

链表容器,通常适用于频繁的新增删除,遍历的方式访问数据元素的场景

LinkedList 底层数据结构为链表,非线程安全,本片博文则简单分析下增删改对链表的操作姿势,以及LinkedList的迭代实现

I. 数据结构

双向链表存储,内部保存表头和表尾对象,size用来记录List的长度

transient int size = 0;

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;


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

双向链表的定义,确保LinkedList支持正向和反向的迭代

II. 新增,删除,读取逻辑

1. 读取逻辑

获取链表中某个索引处的值,只能通过遍历来实现查找

因为是双向链表,若以根据索引index和实际的长度size,可以判定是从前往后找快还是从后往迁找快,查看源码,判断具体实现是否有做区分

public E get(int index) {
    // 越界判断
    checkElementIndex(index);
    return node(index).item;
}

Node<E> node(int 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;
    }
}

实现方式和我们的预期相同,二分判断,若index在前半段,则从链表头开始查找;否则从链表尾进行查找

2. 新增元素

添加元素,区分为在链表尾添加和在链表中间进行添加,算是基本数据结构中链表操作方法

public void add(int index, E element) {
    // 越界判断
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else {
      // 先获取到index索引对应的节点,然后在该节点之前插入新的元素
        linkBefore(element, node(index));
    }
}

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) {
  // 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++;
}

新增元素示意图

3. 删除元素

链表中元素删除比较简单,修改前后节点的next,first引用即可

public boolean remove(Object o) {
  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);
              return true;
          }
      }
  }
  return false;
}

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;
  size--;
  modCount++;
  return element;
}

说明

  • 删除一个不存在的元素,返回false
  • LinkedList中可以存null

III. 小结

  1. LinkedList底层结构为双向链表
  2. 可以塞入null到链表中
  3. 有序,非线程安全
  4. 适用场景
    • 不要求线程安全
    • 插入删除频繁
    • 通过遍历方式访问元素(或较少的根据索引来查询元素)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏cmazxiaoma的架构师之路

浅谈CGLIB动态代理和JDK动态代理 学习笔记

57840
来自专栏猿人谷

顺序栈的实现和两栈共享空间

顺序栈的实现和两栈共享空间 一.顺序栈的实现        栈(stack)是限定仅在表尾进行插入或删除操作的线性表。我们把允许插入和删除的一端称为栈顶(t...

57080
来自专栏老马说编程

(39) 剖析LinkedList / 计算机程序的思维逻辑

上节我们介绍了ArrayList,ArrayList随机访问效率很高,但插入和删除性能比较低,我们提到了同样实现了List接口的LinkedList,它的特点与...

21680
来自专栏haifeiWu与他朋友们的专栏

死磕Java之聊聊LinkedList源码(基于JDK1.8)

我们主要看研究一下下面的几个方法,LinkedList其他方法都是通过调用这几个方法来实现功能,包括LinkedList的双端队列的方法也是。

14040
来自专栏海说

14、Iterator跟ListIterator的区别

14、Iterator与ListIterator的区别       在使用List,Set的时候,为了实现对其数据的遍历,会经常使用到Iterator(跌代器)...

19800
来自专栏魂祭心

原 Promise 实现

30250
来自专栏数据结构与算法

BZOJ4939: [Ynoi2016]掉进兔子洞(莫队 bitset)

那么第$i$个询问的答案为$r1 - l1 + r2 - l2 + r3 - l3 + 3 - min(cnt1[x], cnt2[x], cnt3[x])$

9210
来自专栏电光石火

3X3 九宫格

题目:3X3 的九宫格,每个横竖斜相加都等于15,使用1-9数字。 要求:PHP语言,1-9数字不重复。 解题思路分析: 1:可以知道和为15,所以获...

51070
来自专栏武培轩的专栏

Leetcode#500. Keyboard Row(键盘行)

给定一个单词列表,只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。

19530
来自专栏Java技术栈

你知道void和Void的区别吗?

区别 void 用于无返回值的方法定义。 Void Void是void的包装方法,和其他基础类型的包装方法不同是Void不能被实例化,Void还可用于一直返回n...

350110

扫码关注云+社区

领取腾讯云代金券