LinkedList源码详解

2024-07-13 07:22| 来源: 网络整理| 查看: 265

LinkedList源码详解

上文对ArrayList进行详情介绍，不少小伙伴表示学到了学到了。这次对LinikedList 源码得介绍，也希望大家会喜欢。先提出几个面试问题，看看大家都答得怎么样？

1. 浅谈ArrayList 和 LinkedList 得区别？ 2. LinkedList 底层数据结构是什么？加入你回答出来了，是循环双向链表吗？你又回答出来了，为什么不选择循环双向链表？ 3. LinkedList 是头插还是尾插？一、关键属性 /** * 链表长度（大小） */ transient int size = 0; /** * 头节点 * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */ transient Node first; /** * 尾节点 * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */ transient Node last;

LinkedList 重要得属性就这三个，size 表示链表长度（大小），first，last 头尾节点。那first，last具体是什么呢？

/** * linkedList 内部类 * Node 是链表数据结构，更准确的说，是双向链表。它不仅有 item 值，next 下一个节点，它 * 还有一个prev 表示上一个节点的属性。这样就是它前后都可以遍历 */ 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; } } 二、容器初始化

LinkedList 的构造方法比ArrayList 简单初始化方式：

/*** * 我们常用的就是一个无惨构造方法 */ public LinkedList() { } 三、核心add方法

整体流程图：在这里插入图片描述

/** * 字面意思可以看出：尾插法 **/ public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { final Node l = last; // 实例化新Node final Node newNode = new Node(l, e, null); last = newNode; // 判断此前是否有节点 if (l == null) first = newNode; else // 设置上一个节点的next l.next = newNode; // 大小加1 size++; modCount++; } 从add()方法可得知，linkedList 是尾插法

对于linkedList 来说，不存在扩容一说，每次新增节点，只需要指定当前节点的next属性以及新节点的prev属性，就可实现新增。

四、核心get方法

get 方法相对于add方法是比较耗时，这也是ArrayList 和 LinkedList 的区别之一。 ArrayList 可以快速定位，而LinkedList 不可以。主要原因是两个底层的数据结构性质不同，一个是数组（天生的快速定位），一个链表（快速修改）。不过LinikedList 也针对查找进行了优化，当index （下标）小于size一半的时候，从头first 开始搜索，否则从尾last。

public E get(int index) { // 下标检查（你不可以是小于0的吧，你也不可以大于size吧） checkElementIndex(index); // 获取节点值 return node(index).item; } Node node(int index) { // assert isElementIndex(index); if (index > 1)) { // 从头查 Node x = first; for (int i = 0; i return removeFirst(); } /** * 移除头结点 */ public E removeFirst() { final Node f = first; if (f == null) throw new NoSuchElementException(); return unlinkFirst(f); } /** * 删除头节点 **/ private E unlinkFirst(Node f) { // assert f == first && f != null; final E element = f.item; final Node next = f.next; // 帮助GC （交给GC了） f.item = null; f.next = null; // help GC first = next; // 如果没有next节点，说明空了 last为null if (next == null) last = null; else // 不空说明，next节点要作为头节点了 next.prev = null; size--; modCount++; return element; } 2. remove(int i) 删除指定下标

LinkedList 的 remove(下标) 方法，是根据下标找到 node，根据node进行删除remove(node) 而ArrayList 的remove(Object o ) 是先定位下标，再remove(下标)直接删除

public E remove(int index) { checkElementIndex(index); // 根据下标找到 node 再删除node return unlink(node(index)); } /** * 对于列表来说删除的逻辑很简单 * 将前一个节点（假如存在）的next 指定后一个节点 * 将后一个节点（假如存在）的prev 指定前一个节点 **/ E unlink(Node x) { // assert x != null; final E element = x.item; // 后节点 final Node next = x.next; // 前节点 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; } 3. remove(Obejct o) 删除指定对象 /** * 核心还是 unlink方法 **/ public boolean remove(Object o) { 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; }

注意：remove(Obejct o) 只会删除一个。

六、 contains() 方法

判断是否包含指定元素，主要是遍历链表，对一个元素一个元素进行判断。

public boolean contains(Object o) { return indexOf(o) != -1; } public int indexOf(Object o) { int index = 0; if (o == null) { for (Node x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; }

#七、总结这样看来，LinkedList 也不是想象中的那么复杂。如果有时间的话了，下一篇就是HashMap吧。

【本文地址】

公司简介

联系我们