Java LinkedList源码中如何实现链表结构？

本文共计778个文字，预计阅读时间需要4分钟。

%E2%80%9CLinkedList%E7%AE%80%E4%BB%8B + LinkedList%E6%98%AF%E4%BD%BF%E7%94%A8%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8%E7%BB%93%E6%9E%84%E7%9A%84%E5%AE%B9%E5%99%A8%EF%BC%8C%E5%8F%AF%E5%8A%A8%E6%89%A9%E5%85%85%EF%BC%8C%E6%8F%92%E5%85%A5%E9%80%9F%E7%8E%87%E6%AF%94ArrayList%E5%BF%AB%EF%BC%8C%E6%9F%A5%E8%AF%A2%E9%80%9F%E7%8E%87%E6%AF%94Array%E6%85%A2%E2%80%9D

LinkedList简介

LinkedList是一个使用双向链表结构实现的容器，与ArrayList一样，它能动态扩充其长度，LinkedList相较于ArrayList，其任意位置插入速度比ArrayList要快，但是其查询速度要比ArrayList要慢；LinkedList继承自AbstractSequentialList，实现了List、Deque、Cloneable、Serializable接口。

LinkedList UML图如下：

和ArrayList一样，LinkedList也不是一个线程安全的容器。

LinkedList源码分析

构造方法

LinkedList有两个构造方法：

public LinkedList() { } //从已有的一个容器创建一个LinkedList对象 public LinkedList(Collection<? extends E> c) { this(); addAll(c); }

addAll()方法：

public boolean addAll(Collection<? extends E> c) { return addAll(size, c); } public boolean addAll(int index, Collection<? extends E> c) { //检查index是否溢出 checkPositionIndex(index); Object[] a = c.toArray(); int numNew = a.length; if (numNew == 0) return false; //获取第index位置的node元素和node的前一个元素 //succ：第index位置的node元素 //pred：index位置前一个node元素 Node<E> pred, succ; if (index == size) { succ = null; pred = last; } else { succ = node(index); pred = succ.prev; } //遍历，将元素插入链表中 for (Object o : a) { @SuppressWarnings("unchecked") E e = (E) o; Node<E> newNode = new Node<>(pred, e, 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; }

add方法

LinkedList也有两个add方法，如下：

public boolean add(E e) { //添加元素到队尾 linkLast(e); return true; } public void add(int index, E element) { //检查index是否溢出 checkPositionIndex(index); if (index == size) //index == size，直接添加到队尾 linkLast(element); else //index != size，添加元素到index位置 linkBefore(element, node(index)); }

linkLast方法：

void linkLast(E e) { final Node<E> l = last; //新建一个node，将其前一个元素指针指向原链表的最后一个元素 final Node<E> newNode = new Node<>(l, e, null); //更新尾指针 last = newNode; if (l == null) //若原last==null说明此时链表就一个元素 first = newNode; else //更新原链表尾元素指针 l.next = newNode; size++; modCount++; }

linkBefore方法：

void linkBefore(E e, Node<E> succ) { // assert succ != null; //获取指定位node元素的前一个元素pred final Node<E> pred = succ.prev; //新建一个node，将其前指针指向pred元素 final Node<E> newNode = new Node<>(pred, e, succ); //将指定位置的node元素的前指针指向新元素，完成插入 succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }

获取指定位置node指针方法node：

Node<E> node(int index) { // assert isElementIndex(index); //index > size/2时，说明在链表前半段，从前往后搜索 if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; //index < size/2时，从后往前搜索 } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }

get方法也比较简单，首先检测index是否溢出，然后直接找到index位置的元素，并返回其item。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持易盾网络。