前言

数据结构，一门数据处理的艺术，精巧的结构在一个又一个算法下发挥着他们无与伦比的高效和精密之美，在为信息技术打下坚实地基的同时，也令无数开发者和探索者为之着迷。

也因如此，它作为博主大二上学期最重要的必修课出现了。由于大家对于上学期C++系列博文的支持，我打算将这门课的笔记也写作系列博文，既用于整理、消化，也用于同各位交流、展示数据结构的美。

此系列文章，将会分成两条主线，一条“数据结构基础”，一条“数据结构拓展”。“数据结构基础”主要以记录课上内容为主，“拓展”则是以课上内容为基础的更加高深的数据结构或相关应用知识。

欢迎关注博主，一起交流、学习、进步，往期的文章将会放在文末。

这一节我们将开始总结一个常见的数据结构：线性表。
由于线性表的内容较多，本节只能总结部分内容。
主要为两种基础的线性表，数组和链表。在简单介绍其定义之后，重点会放在实现对其各种操作的简单实现及封装。
本节思维导图如下:

链式存储结构——链表

链表也是一种线性表，相较于数组不同的是，链表中的元素的存储结构是链接式的。

作为一种线性表，元素在逻辑上是连续的，有顺序且呈线性排列；但在存储上他们并不像顺序表一般占据连续的空间，而是随机分布在空间各处，每个结点通过指针来记录后继的地址形成链接。

从上面例子中也可看出，每个结点在其所占的空间中除了要存储本身的数据外，还需要单独使用一片空间存储其后继的指针。

所以一个结点可以大致表示成如下形式：

他们链接起来可以表示成：

可以注意到，链表的尾结点没有后继，所以其后继指针需要指向空。且由于链表的内容是随机分布在空间中的各处。所以为了便于访问他们，我们需要保留头结点的指针，也就是知道头结点的位置，对于后面的元素便可以通过后继节点依次访问到他们。

链表的优点在于其空间上的灵活，链接式的存储似的其长度可以任意改变，不像数组的长度是定值。缺点就在于其失去了顺序表中静态访问结点的能力，不能直接按照下标访问某元素，使得访问给定下标的元素必须遍历链表。

单链表的实现

知道了链表的设计方案，下面我们就来将设计方案付诸实践，变成代码。

实际上正如上文所说，链表的内容相较于一般的节点来说只是多出了后继指针，所以我们完全可以在一般的数据结点的基础上加上后继指针来得到链表元素。

单链表元素

//C
typedef struct _Node{ 
    int value;
    struct _Node * next;
}Node;
Node * head;

//Java
class Node{ 
	int value;
	Node next;
}
Node head;

单链表的遍历

遍历整个单链表，必不可少的条件就是获得头指针。有了头指针就可以根据后继指针依次访问后面的元素。
那么什么时候链表遍历结束呢？通过上文的例子不难发现，链表的尾结点的后继指针为空，所以可以根据是否为空来判断这一结点是否是有效结点，这样既可以在遍历过尾结点后准确而迅速的结束遍历，也可以应对链表为空的情况（头指针为空）

下面以遍历链表获得所有元素加和为例：

//C
int getSum(Node * head){ 
	int sum = 0;
	while(head){ 
		sum += head->value;
		head = head->next;
	}
	return sum;
}

//java
class LinkedList{ 
	Node head;
	public int getSum(){ 
		int sum = 0;
		Node cur = head;//不能直接使用头引用进行遍历
		while(cur != null){ 
			sum += cur.value;
			cur = cur.next;
		}
		return sum;
	}
}

复杂度：O(n)

插入元素

向链表的优秀之处在于其数据组织是动态的，插入一个元素可以不需要像数组一样将后面的元素向后移动。可以通过对后继指针的操作来完成插入。

以将元素node插入下标为index(0 ≤ index ≤ len)的位置为例，该函数需要返回操作后的头指针：

//C
Node * insert(Node * head,Node * node,int index){ 
	int curIdx = 0;
	if(index == 0){ //新元素位于队首
		node->next = head;
		return node;
	}
	while(head){ 
		if(curIdx = index - 1 || head->next = NULL){ 
			node->next = head->next;
			head->next = node;
			break;
		}
		head = head->next;
		curIdx++;
	}
	return head; 
}

//Java
class LinkedList{ 
	Node head;
	public Node insert(Node node,int index){ 
		if(index == 0){ //插入头
			node.next = head;
			head = node;
		}
		int curIdx = 0;
		Node cur = head;
		while(cur != null){ 
			if(curIdx = index - 1 || cur.next == null){ 
				node.next = cur.next;
				cur.next = node;
				break;
			}
			cur = cur.next;
			curIdx++;
		}
		return head;
	}
}

上面的程序可以完成将指定元素插入到指定下标的操作。

需要注意的是，该程序特殊规定对于下标超出当前链表规模时会默认插入队尾。

由于链表不能直接静态的找到某下标的位置，所以遍历寻找到该下标的位置还是不可避免的开销，主要的复杂度就产生在这里。
复杂度：O(n)

哨位结点

注意到上面的插入操作中如果将元素插入队首，那么头指针需要更新成为新元素。那么为了避免频繁的更改头指针，我们可以引入哨位结点来解决这个问题。

哨位结点又称哨兵结点，它是一个空节点，没有实际意义，是人为规定的默认队首。真正的队首一定是哨兵节点的后继节点，这样一来，插入元素至队首就变成了插入元素到哨兵节点后面。此时可以保证不论如何头指针不会更改。

使用哨位节点，我们可以重新实现插入操作，此时头指针不会发生改变。

//C
int insert(Node * head,Node node,int index){ 
	int curIdx = 0;
	while(head){ 
		if(curIdx == index || head->next == NULL){ 
			node->next = head->next;
			head->next = node;
			break;
		}
		head = head->next;
		curIdx++;
	}
	return 1;
}

//Java
class LinkedList{ 
	Node head;
	public boolean insert(Node node,int index){ 
		int curIdx = 0;
		Node cur = head;
		while(cur != null){ 
			if(curIdx = index || cur.next == null){ 
				node.next = cur.next;
				cur.next = node;
				break;
			}
			cur = cur.next;
			curIdx++;
		}
		return true;
	}
}

统一了插入队首和插入队中，美感增加了呢。
复杂度：O(n)

单链表的不足

单链表存在一个问题，其中的元素的只能单向访问不能逆序遍历。也就是说，我们仅知道一个节点的后继节点却不知道其前驱结点。

为了解决这个问题，我们需要引入循环链表和双向链表。

循环链表

循环链表指的是将一个单链表首尾相接，使尾结点的后继为头结点，使头结点的前驱为尾结点。

在循环链表中，为了方便对空链表的处理，最好要保留哨位结点。

因此，对于空链表，就是仅有哨位结点作为“头结点”，其后继指向它自身：

这也提示了我们如何创建并初始化一个循环链表：就是初始化一个哨位结点，并使它的后继指针指向自己：

创建/初始化循环链表

通过上面的叙述不难发现，循环链表仅是改变了尾结点的指针，并没有改变结点本身的结构。所以我们可以沿用单链表的结点定义。

//c
Node * createCircularList(){ 
    Node * head = (Node *)malloc(sizeof(Node));
    head->next = head;
    return head;
}

//java
public class CircularList { 
	class Node{ 
		int value;
		Node next;
	}
	
	Node head;
	
	public CircularList() { 
		head = new Node();
		head.next = head;
	}
}

循环链表寻找前驱

下面我们就来使用循环链表来寻找一个元素的前驱。

思路非常的简单，就是不断的向后遍历，直到寻找到一个元素的后继等于询问元素即可。

//c
Node * getPrecursor(Node * curr){ 
    Node * node = curr;
    while(node->next != curr){ 
        node = node->next;
    }
    return node;
}

//java
public class CircularList { 
	class Node{ 
		int value;
		Node next;
	}
	
	Node head;
	
	
	public Node getPrecursor(Node curr) { 
		Node node = curr;
		while(node.next != curr) { 
			node = node.next;
		}
		return node;
	}
}

复杂度：O(n)
对于常规的增删改查操作，循环链表的操作基本上同单向链表没有本质上的区别。

一个需要注意的地方就是循环链表的遍历，由于循环链表的尾结点的后继是头结点，所以在判断遍历结束时条件需要更改为后继节点是否为头结点。其余操作这里就不再一一赘述了。

双向链表

双向链表是在单链表的基础上修改结点结构得到的，在一个结点上不仅记录该节点的后继还记录该节点的前驱，从而在结点之间形成双向连接。

一个结点可以表示成这样：

这样就需要我们对数据结点的结构进行修改：

//C
typedef struct _DoublyNode{ 
    int value;
    DoublyNode * prev;
    DoublyNode * next;
}DoublyNode;

//java
public class DoublyList { 
	class Node{ 
		int value;
		Node prev;
		Node next;
	}
	private Node head;
}

依据这样的结构，他们连接起来可以表示成：

当然我们也可以给他们加上哨位结点并且使用环形结构：

双向链表的操作相较于单链表会复杂不少，这里我们重新来封装一下基于双链表的增删查。由于双向链表需要同时维护前驱和后继指针，所以为了便于插入和删除，我们有必要使用首位两个哨位结点来控制。

初始化双向链表

那么初始化或者创建一个双向链表的工作就不同于单向链表了，需要初始化两个哨位结点，并且将它们相连。

//c
DoublyNode * createDoublyList(){ 
	DoublyNode * head = (DoublyNode *)malloc(sizeof(DoublyNode));
	DoublyNode * tail = (DoublyNode *)malloc(sizeof(DoublyNode));
	
	head->next = tail;
	head->prev = NULL;
	tail->next = NULL;
	tail->prev = head;
	
	return head;
}

//java
public class DoublyList{ 
	private Node head;
	private Node tail;
	
	public DoublyList(){ 
		head = new Node();
		tail = new Node();

		head.next = tail;
		head.prev = null;
		tail.next = null;
		tail.prev = head;
	}
}

插入元素

向链表中插入一个元素，需要断开原有的链接，重建两次链接。

重建链接的过程会有一些绕，因为它涉及到后继元素的前驱指针，这需要嵌套两次，并且更改前驱和后继节点的顺序也有可能造成bug。

//C
int insert(DoublyNode * node,DoublyNode * head,int index){ 
	if(index < 0 || node == NULL)
		return 0;
	int curr = 0;
	while(head->next){ 
		if(curr == index || head->next->next == null){ 
			head->next->prev = node;
			node->next = head->next;
			node->prev = head;
			head->next = node;
			break;
		}
		curr++;
		head = head->next;
	}
	return 1;
}

//java
public class DoublyList{ 
	private Node head;
	public boolean insert(int index,Node node){ 
		if(index < 0 || node == null)
			return false;
		Node head = this.head;
		while(head.next != null){ 
			if(curr == index || head.next.next != null){ 
				head.next.prev = node;
				node.next = head.next;
				node.prev = head;
				head.next = node;
				break;
			}
			curr++;
			head = head.next;
		}
	} 
	return true;
}

查询元素前驱

用双向链表获得前驱真的是最简单的事情了，因为前驱就在结点中存储着，直接返回就好。

//c
DoublyNode * getPrecursor(DoublyNode * node){ 
	if(node)
		return node->prev;
	return NULL;
}

复杂度：O(1)
快速的时间复杂度来源于双向链表在空间复杂度上面的妥协。可以说双向链表的取钱去操作是空间换时间的典范

删除元素

删除元素，需要重建两条边并且删除结点。难点在于释放元素的时机，和修改前驱结点的后继以及修改后继结点的前驱。

//c
int delete(DoublyNode * head,int index){ 
	if(index < 0)
		return  0;
	int curr = 0;
	head = head->next;//先向后跳一格，查看当前元素是否是待删除元素
	while(head->next){ 
		if(curr == index){ 
			head->prev->next = head->next;
			head->next->prev = head->prev;
			 
			 free(head);
			 return 1;
		}
	}
	return 0;
}

//java
public class DoublyList{ 
	private Node head;
	private Node tail;

	public boolean delete(int index){ 
		if(index < 0)
			return  false;
		int curr = 0;
		Node head = this.head;
		head = head.next;//先向后跳一格，查看当前元素是否是待删除元素
		while(head.next != null){ 
			if(curr == index){ 
				head.prev.next = head.next;
				head.next.prev = head.prev;
				 
				 return true;
			}
		}
		return false;
	}
}

三种链表的简单总结

上面简单介绍了三种链表的定义及各种操作以及链表中的哨位结点。

有些同学可能会纳闷他们能否组合使用，还是说像是只有单链表才能组织成循环链表的形式这种限制。

博主认为：链表循环、哨位结点乃至双向链表是链表结构的不同设计思想，并不专属于某种设计。我们可以看到哨位结点在单向、循环链表中的使用，也可以看到双向的循环链表。所有的结构都是为算法或功能服务的，为了配合他们完成任务，可以使用各种合适的设计方案。

往期博客

• 【数据结构基础】数据结构基础概念
• 【数据结构基础】线性数据结构——线性表概念 及 数组的封装

参考资料：

• 《数据结构》（刘大有，杨博等编著）
• 《算法导论》（托马斯·科尔曼等编著）
• 《图解数据结构——使用Java》（胡昭民著）