大话数据结构学习笔记（二）—— 线性表

对于没有指针的编程语言，可以用数组替代指针，来描述链表。让数组的每个元素由data和cur两部分组成，其中cur相当于链表的next指针，这种用数组描述的链表叫做静态链表，这种描述方法叫做游标实现法。我们对数组的第一个和最后一个元素做特殊处理，不存数据。让数组的第一个元素cur存放第一个备用元素（未被占用的元素）下标，而数组的最后一个元素cur存放第一个有值的元素下标，相当于头结点作用。空的静态链表如下图：

当存放入一些数据时（”甲””乙””丁””戊””己””庚”），静态链表为：

静态链表的插入操作

在静态链表第三个位置插入”丙”后，结果如下：

静态链表的删除操作

删除”甲”后，静态链表如下：

静态链表的优缺点

静态链表的插入思路：

（1）找到带插入索引前一个元素，获取到此时的cur值和下标tmp

（2）获取此时首元素存储的cur：备用链表的下标，也是此时待插入元素的下标 – newCur

（3）将前一个元素的cur指向此时待插入元素的下标 – newCur；

（4）将待插入元素的cur指向原来前一个元素的cur值，tmp

（5）将首元素存储的cur变成原来的值+1；

/**
	 * 向指定位置插入数据
	 * 1.先将带插入的这个放在备用链表的第一条，记做k，然后将首元素的游标指向备用链表的下一个的下标k+1
	 * 2.不在第一条的情况：插入前index-1的位置list[index-1].cur = list[k]的下标
	 * 3.list[k]的游标指向原来第三个位置处的坐标
	 * @param index
	 * @param element
	 * @return
	 */
	public boolean addTo(int index, Object element) {
		if (index < -1 || index > length || element == null) {
			return false;
		}
		// 备用链表的第一个元素下标，也是待插入元素位置的下标newcur
		int newCur = linklist[0].cur;
 
		// 拿到前一个元素的下标
		int ccur = linklist.length - 1;// 获取第一个有效元素的下标
		for (int i = 1; i < index; i++) {
			ccur = linklist[ccur].cur;
		}
		// 出来后ccur=2
		int tmp = linklist[ccur].cur;//存储原来前一个元素的cur == 3（此时为3）
		linklist[ccur].cur = newCur;// 将原来之前有个元素的游标设置为新插入的元素位置的下标（newcur）
		linklist[newCur].cur = tmp;// 将新插入的这个元素的下标设置为插入前，index元素前一个元素的游标ccur
		linklist[newCur] = new Node(tmp, element);
		linklist[0].cur = newCur + 1;
		length++;
		return true;
	}

静态链表的删除思路：

（1）找出删除位置的前一个元素的cur，也就是删除位置的下标tmp；

（2）根据tmp获取删除位置的cur，用来赋值给前一个元素的cur

（3）获取首元素的cur，也就是删除前备用链表的第一个位置的下标newfree；

（4）将删除元素的cur设置成newFree；将首元素的cur设置成删除元素的下标；代表这个删除位置已经到备用链表中的第一个位置，下次新增优先插到这个地方；

/**
	 * 1.找出前一个元素的cur ，也就是删除位置元素的下标 --- 并将前一个元素的cur指向删除索引的后一个元素的下标
	 * 2.删除的这个索引处元素进入备用链表的第一个，cur指向原来的备用链表第一个下标，首元素cur指向该索引处元素下标
	 * 
	 * @param index
	 * @return
	 */
	public boolean delete(int index) {
 
		// 以index = 1为例
		if (index < -1 || index > length) {
			return false;
		}
		int ccur = size - 1;
		for (int i = 1; i < index; i++) {
			ccur = linklist[ccur].cur;
		}
 
		int tmp = linklist[ccur].cur;// 获取前一个元素的cur，也就是删除元素的下标
		int newCur = linklist[tmp].cur;// 获取删除元素的cur
		linklist[ccur].cur = newCur;
 
		int newFree = linklist[0].cur;// 获取原来链表的备用链表的第一个坐标
 
		linklist[0].cur = tmp;// 将首元素的cur设置成删除位置处的下标
		linklist[tmp].cur = newFree;
		size--;
		return true;
	}

循环链表

将单链表终端结点的指针域由空指针改为指向头结点，形成一个环，这种头尾相接的单链表称为循环列表。

循环列表的结构如下图所示：

循环链表的优点：可以从任意一个结点出发，遍历所有结点。

将两个具有尾指针的循环链表合并成一个表非常方便，如下图所示：

合并之后：

双向链表

在每个数据结点中都有两个指针，分别指向直接后继和直接前驱，这样的链表称为双向链表。

双向链表的结构如图所示：