1.列表的介绍

列表是采用动态储存策略的典型结构，它的基本单位是节点。各节点通过引用或者指针彼此连接，在逻辑上构成一个线性序列。相邻节点彼此互称为前驱（predecessor）和后继（successor），如果前驱或后继存在则必然唯一，没有前驱（后继）的节点被称为首（末）节点（在有些列表的实际实现中，首（末）节点是拥有前驱（后继）的，它们被称为头（尾）节点，这两个节点并没有实际作用，也不会对外暴露，只是为了方便某些操作而产生的。）。

与向量不同的是，列表在物理上并不是一段连续的内存空间，所以无法通过秩直接访问其中的元素。因此列表更常用的是寻位置访问，也就是通过节点中的互相引用找到每个元素的位置。

2.列表的接口

作为组成列表的基本单位，节点至少需要这些接口：

由节点所组成的列表，则需要如下接口：

/**
 * 列表的寻秩访问，时间复杂度O(n)
 * @param r 待访问元素的秩
 * @return 对应秩的节点
 */
public ListNode get(int r) {
	//判断秩是否合法
	if (r >= this.size || r < 0) {
		throw new ArrayIndexOutOfBoundsException("下标越界");
	}
	//得到列表的首节点
	ListNode node = this.first();
	//从首节点出发，依次指向后继节点，递推r次则得到秩为r的元素
	while (r-- > 0) {
		node = node.succ();
	}
	return node;
}

/**
 * 列表的前驱插入操作(后继插入操作正好相反)，时间复杂度O(1)
 * @param node
 * @param e
 * @return
 */
public ListNode insertBefore(ListNode node, T e) {
	//增加列表的规模
	this.size++;
	//构造一个新节点，新节点的前驱是该节点的前驱，新节点的后继是该节点。
	ListNode<T> newNode = new ListNode(e, node.getPred(), node);
	//将该节点前驱的后继设为新节点
	node.getPred().setSucc(node);
	//将该节点的前驱设为新节点
	node.setPred(node);
	//返回新节点
	return newNode;
}

/**
 * 删除一个合法位置的节点，时间复杂度O(1)
 * @param node 待删除的节点
 * @return 该节点的元素
 */
public T remove(ListNode<T> node) {
	//减少列表的规模
	this.size--;
	//备份节点中的元素
	T e = node.getDate();
	//将该节点前驱的后继节点设为该节点的后继
	node.getPred().setSucc(node.getSucc());
	//将该节点后继的前驱节点设为该节点的前驱
	node.getSucc().setPred(node.getPred());
	//删除该节点的引用
	node = null;
	//返回该节点的元素
	return e;
}

4.有序列表

有序列表同有序向量一样，再去重上会有更高的性能。列表和有序列表的去重操作与向量和有序向量类似，时间复杂度也相当：

/**
 * 列表的去重操作 时间复杂度O(n^2)
 * @return 删除的元素总数
 */
public int deduplicate() {
	//记录去重之前的规模
	int oldSize = this.size;
	//从首节点开始遍历
	ListNode node = this.first();
	//记录当前的位置
	int r = 1;
	//依次遍历直到尾节点
	while ((node = node.getSucc()) != this.trailer) {
		//在node的r个前驱中寻找是否有与它内容相同的节点
		ListNode temp = this.find(node.getDate(), r, node);
		//如果存在相同的节点 删除该节点，否则增加前驱范围
		if (temp != null) {
			this.remove(temp);
		} else {
			r++;
		}
	}
	//返回规模变化量
	return oldSize - this.size;
}

/**
 * 有序列表的去重操作 时间复杂度O(n)
 * @return 删除的元素总数
 */
public int uniquify() {
	//记录每个区间的第一个元素和下个区间的第一个元素的位置
	int oldSize = this.size;
	//从首节点开始遍历
	ListNode node = this.first();
	//记录下一个节点
	ListNode next;
	//依次遍历直到尾节点
	while ((next = node.getSucc()) != this.trailer) {
		//删除每一个相同节点
		if (node.getDate().equals(next.getDate())) {
			this.remove(next);
		} else {
			node = next;
		}
	}
	//返回规模变化量
	return oldSize - this.size;
}

但是由于列表是寻位置访问而不是寻秩访问，导致有序列表并不能在查找中产生更高的效率。所以有序列表的查找时间复杂度和普通列表一样都是O(n)。

注：本课为清华大学邓俊辉老师在学堂在线的Mooc课程《数据结构》，下次开课时间是2015年春季。如果感兴趣的同学可以去看看，个人觉得这门课无论广度还是深度都高于其他数据结构课。

[MOOC笔记]第三章 列表(数据结构)