[数据结构与算法]双向链表的实现

定义一个双向链表

// 定义双向链表
typedef struct LinkNode {
	int data;	//数据域
	LinkNode *next;	//下一个节点
	LinkNode *last;	//上一个节点
}LinkNode,			//节点域
LinkList;			//头结点

初始化空的双向链表

// 初始化空的双向链表
bool List_Init(LinkList *&list) {
	list = new LinkNode;	
	if (!list) return false;
	list->next = NULL;	//下一个节点置空
	list->last = NULL;	//上一个节点置空
	return true;
}

前插法插入节点

// 前插法插入节点
bool List_Add_front(LinkList *&list, LinkNode *node) {
	LinkNode *p = list;		//临时指针变量
	if (!list || !node)return false;
	if (list->next == NULL) {	//从头节点后插入元素
		node->next = NULL;		//新节点的下一个元素指向空
		node->last = list;		//新节点的上一个指向头节点
		list->next = node;			//p指向新元素	
	} else {
		list->next->last = node;	//头结点往后一个节点的上一个指向新元素
		node->next = list->next;	//新节点的下一个指向之前头结点指向的节点
		node->last = list;			//新节点的上一个指向头节点
		list->next = node;			//头节点的下一个指向新节点
	}
	return true;
}

尾插法插入节点

// 尾插法插入节点
bool List_Add_Back(LinkList *&list, LinkNode *node) {
	LinkNode *last = NULL;
	if (!list || !node) return false;
	last = list;			
	while (last->next) {	
		last = last->next;	//指向最后一个
	}
	node->next = NULL;	// 新节点下一个置空
	node->last = last;	// 新节点的上一个节点指向最后一个
	last->next = node;	// 最后一个节点的下一个指向新节点
	return true;
}

指定位置插入节点

// 指定位置插入节点
bool List_Insert(LinkList *&list, int i, int &e) {
	if (!list || !list->next) return false;
	if (i < 1) return false;
	int j = 0;
	LinkList *p = NULL, *s = NULL;
	p = list;
	while (p && j < i) {	//查找第i个节点,然后p指向该节点
		p = p->next;
		j++;
	}
	if (!p || j != i) {
		cout << "要插入的节点不存在" << endl;
		return false;
	}
	s = new LinkNode;
	s->data = e;
	p->last->next = s;	// p的上一个节点的下一个指向新节点
	s->last = p->last;	// 新节点的上一个指向p的上一个节点
	s->next = p;		// 新节点的下一个指向p
	p->last = s;		// p的上一个指向新节点
	return true;
}

获取指定节点的数据

bool List_GetElem(LinkList *&list, int i, int &e) {
	//在带头结点的双向链表 list 中查找第 i 个元素 
	//用 e 记录 list中第 i 个数据元素的值
	LinkList *p = NULL;	//临时指针
	int index;			//计数
	if (!list || !list->next) return false;
	p = list->next;	
	index = 1;
	while (p && index < i) {	//找到第i个节点
		p = p->next;		
		index++;
	}
	if (!p || index > i) return false;	//i 值不合法,i>index 或 i<=0
	e = p->data;	//找到的数据赋值给e
	return true;
}

删除指定位置的节点

// 删除指定位置的节点
bool List_Delete(LinkList *&list, int i) {
	LinkNode *p = NULL;	//临时查找节点
	int j = 0;			//计数
	if (!list || !list->next) return false;
	if (i < 1) return false;
	p = list;
	while (p && j < i) {
		p = p->next;
		j++;
	}
	if (!p) {
		return false;
	}
	if (!p->next) {				//删除最后一个节点
		p->last->next = NULL;	//最后一个节点的上一个节点置空
		delete p;
		return true;
	}
	p->last->next = p->next;	
	p->next->last = p->last;
	delete p;
	return true;
}

销毁双向链表

// 销毁双向链表
void List_Destroy(LinkList *&list) {
	LinkList *p = list;
	cout << "销毁链表!" << endl;
	while (p) {
		list = list->next;
		delete p;
		p = list;
	}
}

输出双向链表

// 输出双向链表
void List_Print(LinkList *&list) {
	LinkNode *p = NULL;

	if (!list) return;
	p = list;

	while (p->next) {
		cout << p->next->data << "\t";
		p = p->next;
	}
	cout << endl;
	/*cout << endl << "逆向输出" << endl;
	while (p && p!=list) {
		cout << p->data << "\t";
		p = p->last;
	}
	cout << endl;*/
}

main函数

int main(void) {
	LinkList *list = NULL;
	LinkNode *node = NULL;
	int n = 0;	
	// 1.初始化双向链表
	List_Init(list);

	// 2.前插法
	cout << "请输入插入的数量: ";
	cin >> n;
	for (int i = 0; i < n; i++) {
		node = new LinkNode;		//生成新节点
		node->data = i+1;
		List_Add_front(list, node);	//插入node元素
	}

	// 输出链表
	List_Print(list);

	 尾插法
	//cout << "请输入插入的数量: ";
	//cin >> n;
	//for (int i = 0; i < n; i++) {
	//	node = new LinkNode;		//生成新节点
	//	node->data = i + 1;
	//	List_Add_Back(list, node);	//插入node元素
	//}
	
	指定位置插入数据
	//int site = 0;	//位置
	//int data = 0;	//数据
	//cout << "请输入要插入的位置: ";
	//cin >> site;
	//cout << "请输入要插入的数据: ";
	//cin >> data;
	//if (List_Insert(list, site, data)) {
	//	cout << site << "位置插入数据: " << data << "成功!" << endl;
	//} else {
	//	cout << site << "位置插入数据: " << data << "失败!" << endl;
	//}

	从链表中获取指定位置节点的数据
	//int site = 0;	//位置
	//int data = 0;	//数据
	//cout << "请输入要获取数据的位置: ";
	//cin >> site;
	//if (List_GetElem(list, site, data)) {
	//	cout << "查找第" << site << "个节点成功, 数据:" << data << endl;
	//} else {
	//	cout << "查找第" << site << "个节点失败!" << endl;
	//}

	//删除指定位置的节点
	int n;
	cout << "请输入要删除节点的位置: ";
	cin >> n;
	if (List_Delete(list, n)) {
		cout << "删除第" << n << "个节点成功!" << endl;
	} else {
		cout << "删除第" << n << "个节点失败!" << endl;
	}

	//销毁双向链表
	List_Destroy(list);

	// 输出链表
	List_Print(list);
	
	system("pause");
	return 0;
}