数据结构—双向链表

admin管理员组

文章数量:1794759

数据结构—双向链表

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点，时间复杂度为O(1)。

双链表具有以下优点：

1、删除单链表中的某个结点时，一定要得到待删除结点的前驱，得到该前驱有两种方法，第一种方法是在定位待删除结点的同时一路保存当前结点的前驱。第二种方法是在定位到待删除结点之后，重新从单链表表头开始来定位前驱。尽管通常会采用方法一。但其实这两种方法的效率是一样的，指针的总的移动操作都会有2*i次。而如果用双向链表，则不需要定位前驱结点。因此指针总的移动操作为i次。

2、查找时也一样，我们可以借用二分法的思路，从head（首节点）向后查找操作和last（尾节点）向前查找操作同步进行，这样双链表的效率可以提高一倍。

可是为什么市场上单链表的使用多于双链表呢？

从存储结构来看，每个双链表的节点要比单链表的节点多一个指针，而长度为n就需要 n*length（这个指针的length在32位系统中是4字节，在64位系统中是8个字节） 的空间，这在一些追求时间效率不高应用下并不适应，因为它占用空间大于单链表所占用的空间；这时设计者就会采用以时间换空间的做法，这时一种工程总体上的衡量。

代码实现：

#define _CRT_SECURE_NO_WARNINGS
#include "iostream"using namespace std;typedef struct Person  //数据
{int number;char name[32];
}DATATYPE;typedef struct Node	//结点
{DATATYPE data;Node *pri;Node *next;
}linkNode;typedef struct List		//链表
{linkNode *head;int clen;
}linkLIst;//链表初始化
linkLIst * initList()
{linkLIst *tmp = new linkLIst;if (NULL == tmp){perror("list_init Linklist");exit(1);}tmp->clen = 0;tmp->head = NULL;return tmp;
}//头插
int insertHead(linkLIst *mlist,DATATYPE *data)
{linkNode *newnode = new linkNode;	//创建要添加的结点newnode->next = NULL;newnode->pri  = NULL;if (NULL == newnode){perror("insertHead newnode");return 1;}newnode->data = *data;newnode->next = mlist->head;mlist->head = newnode;mlist->clen++;return 0;
}//尾插
int insertTail(linkLIst *mlist, DATATYPE *data)
{linkNode *newnode = new linkNode;		//创建要添加的结点if (NULL == newnode){perror("insrtTail newnode");return 1;}newnode->data = *data;newnode->next = NULL;newnode->pri = NULL;if (NULL == mlist->head){mlist->head = newnode;}else{linkNode* tmp = mlist->head;while (tmp->next){tmp = tmp->next;}tmp->next = newnode;newnode->pri = tmp;}	mlist->clen++;return 0;
}//查找
linkNode* findList(linkLIst *mlist,char *pname)
{linkNode *tmp = mlist->head;while (tmp){if (0 == strcmp(tmp->data.name,pname)){return tmp;}tmp = tmp->next;}return NULL;
}//删除元素
int delList(linkLIst *mlist, char *pname)
{if (NULL == mlist->head)			//判断链表是否为空{cout << "链表已为空" << endl;return 1;}if (NULL == mlist->head->next)				//判断是否只有表头{if (0 == strcmp(mlist->head->data.name,pname)){delete mlist->head;mlist->head = NULL;}else{cout << "未查到。。。" << endl;return 1;}}else{linkNode *p = mlist->head;linkNode *q = mlist->head;while (p){if (0 == strcmp(p->data.name,pname))		{if (p == q)					//判断是否为表头{mlist->head = p->next;p->next->pri = NULL;}else{q->next = p->next;p->next->pri = q;}delete p;p = NULL;mlist->clen--;return 0;}else{q = p;p = p->next;			}}}cout << "未找到要删除的元素。。。" << endl;return 1;
}//链表逆序
int reverseList(linkLIst *mlist)
{linkNode *p = mlist->head->next;linkNode *q = mlist->head;while (p){q->next = p->next;if (p->next){p->next->pri = q;}p->next = mlist->head;p->pri = NULL;mlist->head = p;p = q->next;}return 0;
}//链表排序
int sortList(linkLIst *mlist)
{if (NULL == mlist->head){cout << "链表为空" << endl;return 1;}if (NULL == mlist->head->next){cout << "链表只有一个表头" << endl;return 0;}else{linkNode *p, *q, temp;q = mlist->head;while (q->next != NULL){p = q->next;while (p != NULL){if (p->data.number < q->data.number){temp.data = p->data;p->data = q->data;q->data = temp.data;}p = p->next;}q = q->next;}	}cout << "排序完成" << endl;return 0;
}//修改链表元素
int updataList(linkLIst *mlist,char *oldname,char *newname)
{linkNode *temp;temp = findList(mlist,oldname);strcpy(temp->data.name, newname);return 0;
}//销毁链表
int destoryList(linkLIst *mlist)
{linkNode *tmp = mlist->head;while (mlist->head)			//逐个删除每个结点{tmp = mlist->head;mlist->head = tmp->next;delete tmp;}tmp = NULL;delete mlist;mlist = NULL;cout << "释放完成" << endl;return 0;
}//打印链表
int showList(linkLIst *mlist)
{linkNode *tmp = mlist->head;while (tmp){cout << "ID:" << tmp->data.number << " " << "名字：" << tmp->data.name << endl;tmp = tmp->next;}return 0;
}int main()
{linkLIst *m_list = initList();DATATYPE data1 = { 1,"刘德华" };DATATYPE data2 = { 0,"周润发" };cout << "头插：" << endl;insertHead(m_list, &data1);insertHead(m_list, &data2);	cout << "当前链表长度：" << m_list->clen << endl;showList(m_list);DATATYPE data3[3] = {{2,"张学友"},{3,"郭富城"},{4,"黎明"}};DATATYPE data4 = { 1,"周星驰" };cout << "尾插：" << endl;insertTail(m_list, &data3[0]);insertTail(m_list, &data3[1]);insertTail(m_list, &data3[2]);insertTail(m_list, &data4);sortList(m_list);cout << "当前链表长度：" << m_list->clen << endl;showList(m_list);cout << "---------------------------------------------------" << endl;cout << "链表逆序：" << endl;reverseList(m_list);cout << "链表长度：" << m_list->clen << endl;showList(m_list);cout << "---------------------------------------------------" << endl;cout << "查找元素：" << endl;linkNode* res = findList(m_list, "刘德华");if (NULL != res){cout << "ID：" << res->data.number << " " << "姓名：" << res->data.name << endl;}else{cout << "未找到。。。" << endl;}cout << "---------------------------------------------------" << endl;cout << "删除元素：" << endl;delList(m_list, "刘德华");cout << "链表长度：" << m_list->clen << endl;showList(m_list);cout << "---------------------------------------------------" << endl;cout << "修改链表元素：" << endl;updataList(m_list, "张学友", "成龙");showList(m_list);cout << "---------------------------------------------------" << endl;cout << "销毁链表：" << endl;destoryList(m_list);system("pause");	return 0;
}	

本文标签： 数据结构双向链表