链表 vs 数组

链表和数组的最大区别在于链表不支持随机访问，不能像数组那样对任意一个（索引）位置的元素进行访问，而需要从头节点开始，一个一个往后访问直到查找到目标位置。

单链表

与顺序表相对，链表是一种链式存储方式。单链表是实现顺序表最简单的一种链表，根据是否包含虚拟头节点，分为含虚拟头节点和不含虚拟头节点两种方式。本文以含虚拟头节点为例，用C++实现单链表数据结构ADT。

节点：链表的组成元素，每个节点包含数据域data和指针域next。例程为了简化设计，data用int类型表示。

虚拟头节点：链表的第一个节点，为了维护链表操作方便，但不存放数据。

虚拟头节点(dummy head) VS 无虚拟头节点

含虚拟头节点的链表优势：所有的数据节点（除去头节点）都是对等的，对链表节点的API操作一般不影响头节点本身指针变化（除去头节点next域）。

缺点：需要额外考虑头节点影响，比如IsEmpty()判断条件, 和Length()是否对等(IsEmpty <=> length==0?)，头节点对用户是否可见，能否被用户直接remove等。

单链表结构设计

含虚拟头节点的单链表list如下图所示，包含一个虚拟头节点V0，而V1~Vn通过前驱节点next域进行链接，从而形成一个单向链式结构。

虚拟头节点V0，不包含数据；V1~Vn包含数据，Vn->next = NULL

名称	描述	代表自定义符号
虚拟头节点	不包含数据	Vh/head
尾节点	链表的最后一个节点，特征：next=NULL	Vn-1/tail
普通数据节点	包含具有实际意义数据的节点	V0~Vn-1
长度	包含实际意义数据节点数为n（不包括Vh）	length
空链表	虚拟头节点为空，即head=NULL	V0=NULL
位置	从V0开始（Vh后继节点）开始计数0，直到Vn-1(尾节点)的节点对应位置。范围[0,n-1]	position
插入节点	在指定位置处插入节点，除插入节点及前驱和后继，不改变链表其他节点关系	insert
删除节点	在指定位置处删除节点, 除插入节点及前驱和后继，不改变链表其他节点关系	remove

单链表ADT设计

1. 链表节点ADT Node.h

/**
 * 单链表节点类
 */
class Node
{
	int data;
	Node *next;

public:
	Node();
	Node(Node*, int);
};

2. 单链表ADT LinkedList.h

/**
 * 单链表类
 * @description 带虚拟头节点
 */
class LinkedList
{
private:
	Node *head;
	Node *tail;

public:
	LinkedList();
	virtual ~LinkedList();
	Status Init();          // 初始化链表
	Status Destroy();       // 销毁链表

	int Length();           // 求链表长度(有效节点)节点个数
	bool IsEmpty();         // 链表是否为空
	Status Insert(int pos, int value);  // 在指定位置生产节点, 并插入数据
	Status Remove(int pos);  // 删除指定位置节点
	int GetValue(int pos);   // 读取指定位置节点数据
	Node* GetAddress(int pos); // 获取知道位置节点的地址
	int SearchPosition(int value); // 搜索第一个出现的元素值的节点位置
	Status Update(int pos, int value); // 更新指定位置节点数据
	Status ClearList(); // 清除链表数据(不包含头节点)
	Status PrintList(); // 顺序打印链表节点数据
	Status Reverse();   // 反转链表
};

3. Node实现 Node.cpp

#include "Node.h"
#include <cstdlib>

Node::Node() {
	data = 0;
	next = NULL;
}

Node::Node(Node* newNext, int newValue)
{
	data = newValue;
	next = newNext;
}

Node::~Node()
{
	// TODO Auto-generated destructor stub
}

4. 链表实现LinkedList.cpp

#include "LinkedList.h"
#include <cstdlib>
#include <iostream>

using namespace std;

LinkedList::LinkedList() {
	head = NULL;
	tail = NULL;
}

LinkedList::~LinkedList() {
	Destroy();
}

/**
 * 初始化链表
 */
Status LinkedList::Init()
{
	// 创建虚拟头节点
	head = new Node(NULL, 0);

	if(head != NULL)
	{
		return OK;
	}

	return ERROR;
}

/**
 * 销毁链表
 * @description 与初始化操作相对, 删除所有链表节点, 包括头节点
 */
Status LinkedList::Destroy()
{
	if(head)
	{
		Node *curP = head;

		while(head)
		{
			curP = head->next;
			delete head;
			head = curP;
		}

		return OK;
	}
	else
	{
		cout <<"The list is NULL"<<endl;
				return ERROR;
	}
}

/**
 * 求链表长度(有效节点)节点个数
 * @description 从虚拟头节点的下一个节点开始计算有效节点数
 */
int LinkedList::Length()
{
	if(!head)
	{
		cout <<"The list is NULL"<<endl;
		exit(-1);
	}

	Node *curP = head->next;
	int n = 0;
	while(curP != NULL)
	{
		n ++;
		curP = curP->next;
	}

	return n;
}

/**
 * 判断链表是否为空
 * @description 判断依据: 虚拟头节点head == NULL
 * 注: 长度为0 不代表链表为空
 */
bool LinkedList::IsEmpty()
{
	return (head == NULL);
}

/**
 * 在指定位置生产节点, 并插入数据
 * @param pos [in] 待插入位置. 从头节点的后继开始为0计数，所需要经过的节点数。范围：0~n-1
 * @param value [in] 待插入节点数据域
 */
Status LinkedList::Insert(int pos, int value)
{
	if(IsEmpty())
	{
		cout <<"The list is NULL. Pls Create an List and init it first."<<endl;
		exit(-1);
	}

	// create a new Node
	Node *newNode = new Node(NULL, value);

	if(pos == 0)
	{
		newNode->next = head->next;
		head->next = newNode;
	}
	else if(pos >0 && pos <= Length())
	{
		// find the predecessor node to be inserted
		Node *p = GetAddress(pos-1);

		// insert the new Node to List
		if(p != NULL)
		{
			if(p->next != NULL)
			{// not tail
				newNode->next  = p->next;
			}
			p->next = newNode;
		}
	}
	else
	{
		cout<<"Error: Input param Pos is illegal(<0)"<<endl;
		return ERROR;

	}

	return OK;
}

/**
 * 删除指定位置节点
 * @param pos [in] 待插入位置. pos有效范围: [0, n), 0代表虚拟节点后面一个节点, 虚拟节点无法通过此API删除
 *
 */
Status LinkedList::Remove(int pos)
{
	Node *preNode = NULL;
	Node *curNode = NULL;
	Node *nextNode = NULL;

	if(pos < 0 || pos >= Length())
	{
		cout << "Remove node with error position"<<endl;
		exit (-1);
	}
	else if(pos == 0)
	{// find the prior node, namely , head node
		preNode = head;
	}
	else if(pos < this->Length())
	{
		// find the prior node
		preNode = GetAddress(pos - 1);
	}

	if(!preNode)
	{
		return ERROR;
	}

	curNode = preNode->next;
	if(curNode)
	{
		nextNode = curNode->next;
		preNode->next = nextNode;
		delete curNode;
	}

	return OK;
}

/**
 * 读取指定位置节点数据
 */
int LinkedList::GetValue(int pos)
{
	// find the  node
	Node *curP = GetAddress(pos);
	if(curP != NULL)
	{
		return curP->data;
	}
	else
	{
		return 0;
	}
}

/**
 * 获取位置节点的地址
 * @param pos [in] 从头节点的后继开始为0计数，所需要经过的节点数。范围：[0, n-1], n是链表长度(有效数据节点数)
 * @return 节点的地址
 */
Node* LinkedList::GetAddress(int pos)
{
	// valid list is null or not
	if(!head)
	{
		cout <<"The list is NULL"<<endl;
		exit(-1);
	}

	// valid intput param
	if(pos < 0 || pos >= Length())
	{
		cout <<"Insert position is out of the list's bounds"<<endl;
		exit(-1);
	}

	// 顺序查找位置pos的节点
	int i = 0;
	Node *curP = head->next;
	while(curP != NULL)
	{
		if(i == pos)
		{
			return curP;
		}

		i ++;

		curP = curP->next;
	}

	return NULL;
}

/**
 * 搜索第一个出现的元素值的节点位置
 * @param value 待查找值
 * @return 链表第一个节点的数据域=value的位置
 * - ERROR 错误
 * - >=0 位置序号
 */
int LinkedList::SearchPosition(int value)
{
	// valid list is null or not
	if(!head)
	{
		cout <<"The list is NULL"<<endl;
		exit(-1);
	}

	// sequential search
	Node *p = head->next;
	int i = 0;
	while(p != NULL)
	{
		i ++;
		if(p->data == value)
			return i;
		else
			p = p->next;
	}

	cout<< "Can't find the value in list"<<endl;
	return ERROR;
}

/**
 * 更新指定位置节点数据
 * @param pos [in] 待更新节点位置
 * @param value [in] 待更新节点要修改的目标值
 * @return 更新结果
 * - OK 正常更新
 * - ERROR 没有找到待更新节点, 可能由位置错误或者链表为空导致
 */
Status LinkedList::Update(int pos, int value)
{
	// find the node
	Node *curP = GetAddress(pos);
	if(curP != NULL)
	{
		curP->data = value;
		return OK;
	}

	return ERROR;
}

/**
 * 清除链表数据(不包含头节点)
 */
Status LinkedList::ClearList()
{
	// valid list is null or not
	if(!head)
	{
		cout <<"The list is NULL"<<endl;
		exit(-1);
	}

	Node *p = head->next;
	Node *tmp = NULL;

	while(p!=NULL)
	{
		tmp = p;
		p = p->next;
		delete tmp;
	}

	head->next = NULL;

	return OK;
}

/**
 * 顺序打印链表节点数据
 */
Status LinkedList::PrintList()
{
	// valid list is null or not
	if(IsEmpty())
	{
		cout <<"The list is NULL. Pls Create an List and init it first."<<endl;
		return ERROR;
	}

	cout <<"List:[ ";
	if(Length() == 0)
	{
		cout<<"NULL";
	}
	else
	{
		Node *p = head->next;

		while(p != NULL)
		{
			cout<<p->data<<" ";
			p = p->next;
		}
	}
	cout <<"] "<<endl;
	return OK;
}

/**
 * 反转链表, 除虚拟头节点
 */
Status LinkedList::ReverseList()
{
	// valid list is null or not
	if(IsEmpty())
	{
		cout <<"The list is NULL. Pls Create an List and init it first."<<endl;
		exit(-1);
	}

	if(Length() == 0)
	{
		cout <<"The list length = 0. Pls insert new Node."<<endl;
		exit(-1);
	}

	// reverse List
	Node *pre = head->next; // precursor Node
	Node *cur = pre->next;  // current Node
	Node *nxt = NULL;       // successor Node

	while(cur != NULL)
	{
		nxt = cur->next;
		cur->next = pre;
		pre = cur;
		cur = nxt;
	}

	// set the tail Node
	head->next->next = NULL;

	// set the head Node's next field
	head->next = pre;

	return OK;
}

6. 测试结果

可以看到已经实现了链表基本的插入、打印、反转等功能。