02.Java 集合 - LinkedList
02.Java 集合 - LinkedList
夕阳晒裤衩 发表于11个月前
02.Java 集合 - LinkedList
  • 发表于 11个月前
  • 阅读 9
  • 收藏 1
  • 点赞 0
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

##基本概念

在探究 LinkedList 之前首先要明白一个词:链表。

  • 概念:链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

  • 结构:由一系列节点组成,节点包括值域和指针域两个部分,其中值域用来存储数据元素的值,指针域用来存储上(下)一个节点的地址。

  • 特点:链表查找和修改相应的时间复杂度分别是 O(n)、O(1)

  • 类型:链表有单链表和双链表之分,单链表只有一个指针域,指向该节点的下一个节点位置;双链表则有两个指针域,分别执向它的前节点、后节点。


原理

在这里主要探究的是 LinkedList 的内部构造,以及它常用的增删改查方法。

以下源码来自 JDK 1.7

###1.节点元素

首先来看 LinkedList 中一个重要的静态内部类:

private static class Node<E> {
	E item; // 值域
	Node<E> next; // 后指针
	Node<E> prev; // 前指针

	Node(Node<E> prev, E element, Node<E> next) {
		this.prev = prev;
		this.item = element;
		this.next = next;
	}
}

Node,也称节点。通过代码可以发现构建一个节点需要三种元素:值域、前指针、后指针,缺一不可。其中:

  • 值域:用来存放元素的值。
  • 前后指针:指针可以指向别的节点,具体作用稍后再讲。

根据描述可以绘制 Node 的结构如下:

输入图片说明


###2.内部结构

介绍完节点的概念,再来看看 LinkedList 的内部构造。

// 元素个数
transient int size = 0;

// 尾节点
transient Node<E> last;

// 头结点
transient Node<E> first;

// 构造函数
public LinkedList() { }

LinkedList 的三个成员变量,分别代表元素个数、尾节点、头节点,并且它们都无法被序列化。因此可以猜测其内部构造是一个链表,由多个节点链接而成。

观察它的构造函数,是一个默认构造函数。说明 LinkedList 默认创建出来后是一个空的集合,与 ArrayList 不同,它不需要指定容量,因为它的容量是可变的。

空的集合我们还看不出它具体的内部结构,因此需往集合中添加一个元素后,再作分析。

// 添加指定元素
public boolean add(E e) {
	linkLast(e);
	return true;
}


// 链接(添加)到末尾位置
void linkLast(E e) {

	final Node<E> l = last;

	// 关键-> 创建一个值域为 e 的节点,其前指针指向 l (即原来的尾节点)
	final Node<E> newNode = new Node<>(l, e, null);
	
	// 将新创建的节点设置为尾节点
	last = newNode;

	// 第一次往 LinkedList 中添加元素时 last 为空节点
	if (l == null){
		// 关键 ->将新创建的节点设置为首节点,说明只有一个节点时,该节点既是首节点又是尾节点
		first = newNode;
	}else{
		// 修改 l 的后指针
		l.next = newNode;
	}

	size++;
	modCount++;
}

根据代码,可以绘制 LinkedList 创建过程如下:

输入图片说明


###3.添加操作

这里要分析的 LinkedList 常用的添加操作有:不指定位置(添加到链表末尾)、指定位置(添加到链表指定位置)

  • 前者在上面介绍内部结构时已经分析过原理,这里不在阐述。
  • 后者与前者相比,多了查询指定位置元素的步骤。

下面来看看在指定位置添加元素的过程:

public void add(int index, E element) {
	// 校验位置是否合法
	checkPositionIndex(index);

	// 判断指定位置是否为链表末尾
	if (index == size){
		linkLast(element);
	}else{
		// 关键-> 先找到该位置的元素,再添加到该元素前面。
		linkBefore(element, node(index));
	}
}

// 校验位置是否合法
private void checkPositionIndex(int index) {
	if (!isPositionIndex(index)){
		// 抛出异常...
	}
}
private boolean isPositionIndex(int index) {
	return index >= 0 && index <= size;
}

// 找到指定位置节点
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;
	}
}

// 关键-> 这里 e 表示要添加的元素,succ 表示指定位置上的元素
void linkBefore(E e, Node<E> succ) {
	
	final Node<E> pred = succ.prev;	
	
	// ①构建新节点,节点值为 e,并指定前后节点分别为 succ 的前节点、succ
	final Node<E> newNode = new Node<>(pred, e, succ);

	// ②修改前后节点的指针
	succ.prev = newNode;
	if (pred == null){
		first = newNode;
	}else{
		pred.next = newNode;
	}
	size++;
	modCount++;
}

分析代码,在 LinkedList 的指定位置添加元素大概需要以下几个步骤:

  • 检验指定位置是否合法
  • 根据指定位置选择遍历方向,从头节点或从尾节点
  • 找到为指定位置的节点
  • 构建新节点并插入链表(关键)

整个过程最为关键的步骤在最后一步,这里绘制出整个插入过程如下(①② 对应 linkBefore 方法的注释):

输入图片说明


###4.修改操作

LinkedList 的修改操作与添加操作类似,这里不再探究,只贴出源码:

public E set(int index, E element) {
	checkElementIndex(index);
	Node<E> x = node(index);
	E oldVal = x.item;
	x.item = element;
	return oldVal;
}

整个过程如下:

  • 检验指定位置是否合法
  • 找到指定位置的节点
  • 替换节点的值域(元素)

###5.删除操作

这里要分析 LinkedList 常用的删除操作有三种,分别是:不指定元素的删除操作、删除指定位置的元素、删除指定元素。

  • 不指定元素的删除操作,默认是移除链表的首节点。源码如下:
public E remove() {
	return removeFirst();
}

public E removeFirst() {
	final Node<E> f = first;
	if (f == null){
		throw new NoSuchElementException();
	}
	return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
	
	final E element = f.item;
	final Node<E> next = f.next;
	
	/// 将节点的值域置空,让 GC 回收
	f.item = null;

	// 将节点的后指针置空
	f.next = null; 

	// 设置新的头节点
	first = next;

	// next 为空, 表示只有一个节点
	if (next == null){
		// 关键-> 链表只有一个节点时,该节点(f)既是头节点,也是尾节点
		// 这里要删除 f,所以要把 last 置空
		last = null;
	}else{
		// 修改后节点的前指针
		next.prev = null;
	}
	
	size--;
	modCount++;
	return element;
}
  • 移除指定元素
public E remove(int index) {
	checkElementIndex(index);

	// 关键 -> 从链表中移除
	return unlink(node(index));
}
  • 移除指定位置的元素,与前者相比多了查找指定位置元素的步骤:
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;
}

在上面的代码中,第二、第三种删除操作的真正执行过程都发生下 unlink 方法,其作用是将指定元素从链表中移除。下面来看它的源码:

E unlink(Node<E> x) {

	final E element = x.item;
	final Node<E> next = x.next;
	final Node<E> prev = x.prev;
	
	// prev 为空,说明整个链表只有该节点一个节点
	if (prev == null) {
		first = next;
	} else {
		// ①与前节点断开链接
		prev.next = next;
		x.prev = null;
	}
	
	// next 为空,说明该节点是链接的尾节点
	if (next == null) {
		last = prev;
	} else {
		// ②与后节点断开链接
		next.prev = prev;
		x.next = null;
	}
	
	// ③将节点的值域置空,让 GC 回收
	x.item = null;
	
	size--;
	modCount++;
	return element;
}

不考虑前后节点为空的情况下, 可以绘制其操作过程如下:

Alt text

总的来讲,在 LinkedList 中删除操作的步骤如下:

  • 校验指定位置是否合法,并找到要操作的元素
  • 断开与前节点的链接,包括本节点的前指针、前节点的后指针
  • 断开与后节点的链接,包括本节点的后指针、后节点的前指针
  • 将节点的值域置空让 GC 生效

值得注意的是,若操作的元素为头节点或尾节点时,需要设置新的头/尾节点


###6.遍历操作

一般的来说集合的遍历操作是通过迭代器(Iterator)来完成的,具体调用如下:

List<String> list = new LinkedList<String>();
Iterator<String> iter = list.iterator();
while(iter.hasNext()){
	System.out.println(iter.next());
}

首先来看 LinkedList 的继承关系,从上到下依次是:list -> AbstractList -> AbstractSequentialList-> LinkedList。如下图所示:

输入图片说明

再来看看 itertor 方法的调用过程:

// 在 List 中定义如下:
 Iterator<E> iterator();

// 在 AbstractSequentialList 中定义如下:
public Iterator<E> iterator() {
	// 该方法继承自 AbstractList 类
	return listIterator();
}

// 在 AbstractList 中定义如下:
public ListIterator<E> listIterator() {
	return listIterator(0);
}

// 在 LinkedList 中定义如下:
public ListIterator<E> listIterator(int index) {
	checkPositionIndex(index);
	return new ListItr(index);
}

最后来探究下遍历操作的实现过程:

// 该类是 LinkedList 的内部类
private class ListItr implements ListIterator<E> {
	private Node<E> lastReturned = null;
	private Node<E> next;
	private int nextIndex;
	private int expectedModCount = modCount;
	
	// 构造函数
	ListItr(int index) {
		// nextIndex 表示开始遍历操作的位置
		// next 表示该位置的上的节点
		next = (index == size) ? null : node(index);
		nextIndex = index;
	}
	
	public boolean hasNext() {
		return nextIndex < size;
	}

	public E next() {
		checkForComodification();
		if (!hasNext()){
			// 抛出异常...
		}
		lastReturned = next;
		next = next.next;
		nextIndex++;
		return lastReturned.item;
	}
	final void checkForComodification() {
		if (modCount != expectedModCount){
			// 抛出异常...
		}	
	}

	//省略其他代码...
}

##总结

LinkedList 内部由非循环的双向链表 构成,而链表的特点是:便于修改,不便于查询。

LinkedList 与 ArrayList 不同的是,ArrayList 内容由**数组(即线性表)**构成, 数组的特点是:便于查询,不便于修改。

正是由于它们的内部构造不同导致它们有了不同的特性,因此要根据不同的场景选择不同的 List。

若是频繁修改的,则选择 LinkedList 的效率更好;若是频繁查询的,则选择 ArrayList 的执行效率更好。

标签: Java LinkedList 集合
共有 人打赏支持
粉丝 2
博文 15
码字总数 18485
×
夕阳晒裤衩
Thanks
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: