导航：首页 > 互联网科技 >

如何用源码分析LinkedList

发表于：2025-02-02 作者：千家信息网编辑

千家信息网最后更新 2025年02月02日，这篇文章将为大家详细讲解有关如何用源码分析LinkedList，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。LinkedList简介public cl

千家信息网最后更新 2025年02月02日如何用源码分析LinkedList

这篇文章将为大家详细讲解有关如何用源码分析LinkedList，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。

LinkedList简介

public class LinkedList    extends AbstractSequentialList    implements List, Deque, Cloneable, java.io.Serializable{}

LinkedList继承了AbstractSequentialList，主要方法通过迭代器实现。
LinkedList实现了List；所以它是一个队列，支持添加、删除、修改、遍历等操作。
LinkedList实现了Deque；能将它可以当做双端队列进行使用。
LinkedList实现了Cloneable接口，重写了clone方法，因此可以进行克隆。
LinkedList实现了Serializable接口，因此可以进行序列化。
LinkedList的操作是非线程安全的

成员变量

/** 当前集合的头节点 **/transient Node first;/** 当前集合的尾节点 **/transient Node last;/** 当前集合的实际节点数量 **/transient int size;

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

双向链表的具体节点类，每个节点每个节点又包含三个变量：

item保存当前节点的具体数据
prev保存当前节点的上一个节点
next保存当前节点的下一个节点

构造函数

/** 无参构造一个空的集合 **/public LinkedList() {}/** 根据已有集合构造一个LinkedList **/public LinkedList(Collection c) {    this();    addAll(c);}

元素添加

集合添加元素方法主要有以下几个方法：

在集合头部添加元素，通过linkFirst方法实现；如：addFirst(E e)、offerFirst(E e)、push(E e)。
在集合尾部添加元素，通过linkLast方法实现；如：add(E e)、addLast(E e)、offer(E e)、offerLast(E e)。
在集合指定位置添加元素；如：add(int index, E element)。
在集合中添加新的集合；如：addAll(Collection c)、addAll(int index, Collection c)。

linkFirst(E e)

private void linkFirst(E e) {    final Node f = first;    final Node newNode = new Node<>(null, e, f);    first = newNode;    if (f == null) last = newNode;    else f.prev = newNode;    size ++;    modCount ++;}public void addFirst(E e) {    linkFirst(e);}public boolean offerFirst(E e) {    addFirst(e);    return true;}public void push(E e) {    addFirst(e);}

先获取到首部节点first，再根据首部节点生成新的首部节点newNode
如果原首部节点first为空，那么尾部节点也为newNode，否则设置原节点的上一个为newNode

linkLast(E e)

private void linkLast(E e) {    final Node l = last;    final Node newNode = new Node<>(l, e, null);    last = newNode;    if (l == null) {        first = newNode;    } else {        l.next = newNode;    }    size ++;    modCount ++;}public boolean add(E e) {    linkLast(e);    return true;}public void addLast(E e) {    linkLast(e);}public boolean offer(E e) {    return add(e);}public boolean offerLast(E e) {    addLast(e);    return true;}

先获取到尾部节点last，再根据尾部节点生成新的尾部节点newNode
如果原尾部节点last为空，那么首部节点也为newNode，否则设置原节点的下一个为newNode

add(int index, E element)

/** 添加元素element到当前集合的index位置 **/public void add(int index, E element) {    //校验index是否合法    checkPositionIndex(index);    if (index == size)        linkLast(element);    else        linkBefore(element, node(index));}/** 检查index合法 **/private void checkPositionIndex(int index) {    if (index < 0 || index > size) {        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);    }}/** 在给定元素前插入元素 **/void linkBefore(E e, Node succ) {    final Node prev = succ.prev;    final Node newNode = new Node<>(prev, e, succ);    succ.prev = newNode;    if (prev == null) {        first = newNode;    } else {        prev.next = newNode;    }    size ++;    modCount ++;}/** 根据index定位元素 **/private Node node(int index) {    if (index < size >> 1) {        Node e = first;        for (int i = 0; i < index; i++) e = e.next;        return e;    } else {        Node e = last;        for (int i = size - 1; i > index; i--) e = e.prev;        return e;    }}

先校验index位置，如果是最后一个则直接调用linkLast(E e)
不是最后的位置，则先根据index查找Node节点；如果index小于总长度一般，就从头往尾找，否则就从尾往头部找
最后将元素插入到找到的Node节点前面

addAll(Collection c)

/** 通过下面的addAll(int index, Collection c)方法实现**/public boolean addAll(Collection c) {    return addAll(size, c);}/** 在当前集合index位置插入集合c中所有元素 **/public boolean addAll(int index, Collection c) {    //校验index    checkPositionIndex(index);    Object[] a = c.toArray();    int numNew = a.length;    if (numNew == 0) return false;    Node succ, pred;    if (index == size) {        succ = null;        pred = last;    } else {        succ = node(index);        pred = succ.prev;    }    for (Object o : a) {        Node newNode = new Node(pred, o, null);        if (pred == null) first = newNode;        else pred.next = newNode;        pred = newNode;    }    if (succ == null) {        last = pred;    } else {        pred.next = succ;        succ.prev = pred;    }    size += numNew;    modCount ++;    return true;}

元素移除

元素移除主要有以下几个方法：

移除指定位置的元素，通过unlink方法实现；如：``remove(int index)`。
移除链表中指定的对象；如：remove(Object o)。
移除集合头部元素，通过unlinkFirst方法实现；如：remove()、removeFirst()、poll()、pollFirst()、pop()。
移除集合尾部元素，通过unlinkLast方法实现；如：removeLast()、pollLast()。

remove(int index)

E unlink(Node x) {    final E element = x.item;    final Node prev = x.prev;    final Node next = x.next;    if (prev == null) {        first = next;    } else {        prev.next = next;        x.prev = null;    }    if (next == null) {        last = prev;    } else {        last.prev = prev;        x.next = null;    }    x.item = null;    size --;    modCount ++;    return element;}public E remove(int index) {    checkElementIndex(index);    return unlink(node(index));}private void checkElementIndex(int index) {    if (index < 0 || index >= size) {        throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);    }}

通过checkElementIndex方法校验索引index。
通过unlink方法移除掉此节点。

remove(Object o)

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

先判断对象o是否为null。
循环所有节点判断每个节点的元素值是否和对象o相等；如果相等就移除掉该节点并返回true。

unlinkFirst(Node f)

private E unlinkFirst(Node f) {    final E element = f.item;    final Node next = f.next;    f.item = null;    f.next = null;    first = next;    if (next == null) {        last = null;    } else {        next.prev = null;    }    size --;    modCount ++;    return element;}public E remove() {    return removeFirst();}/** 移除集合头部元素，如果元素为空，抛出NoSuchElementException异常 **/public E removeFirst() {    final Node f = first;    if (f == null) throw new NoSuchElementException();    return unlinkFirst(f);}public E poll() {    return pollFirst();}/** 移除集合头部元素，如果元素为空则返回null **/public E pollFirst() {    final Node f = first;    return f == null ? null : unlinkFirst(f);}public E pop() {    return removeFirst();}

unlinkLast(Node l)

private E unlinkLast(Node l) {    final E element = l.item;    final Node prev = l.prev;    l.item = null;    l.prev = null;    last = prev;    if (prev == null) {        first = null;    } else {        prev.next = null;    }    size --;    modCount ++;    return element;}/** 移除集合尾部元素，如果元素为空，抛出NoSuchElementException异常 **/public E removeLast() {    final Node l = last;    if (l == null) throw new NoSuchElementException();    return unlinkLast(l);}/** 移除集合尾部元素，如果元素为空则返回null **/public E pollLast() {    final Node l = last;    return l == null ? null : unlinkLast(l);}

元素查找

元素查找主要有以下几个方法：

查找指定位置的元素；如：get(int index)。
查找集合头部元素；如：element()、getFirst()、peek()、peekFirst()。
查找集合尾部元素；如：getLast()、peekLast()。

get(int index)

public E get(int index) {    checkElementIndex(index);    return node(index).item;}

getFirst()

public E element() {    return getFirst();}/** 查找集合头部元素，如果元素为空，抛出NoSuchElementException异常 **/public E getFirst() {    final Node e = first;    if (e == null) throw new NoSuchElementException();    return e.item;}public E peek() {    final Node node = first;    return node == null ? null : node.item;}/** 查找集合头部元素，如果元素为空就返回null **/public E peekFirst() {    final Node node = first;    return node == null ? null : node.item;}

getLast()

/** 查找集合尾部元素，如果元素为空，抛出NoSuchElementException异常 **/public E getLast() {    final Node e = last;    if (e == null) throw new NoSuchElementException();    return e.item;}/** 查找集合尾部元素，如果元素为空就返回null **/public E peekLast() {    final Node node = last;    return node == null ? null : node.item;}

元素更新

元素更新只有一个方法：set(int index, E e)

set(int index, E element)

public E set(int index, E element) {    checkElementIndex(index);    //查询index位置的节点    Node node = node(index);    E oldValue = node.item;    //设置为最新元素    node.item = element    return oldValue;}