一、双向链表跟单向链表相比的缺点

1、需要更多空间

双向链表比单向链表多维护一个指向前驱结点的指针，相比单向链表需要更多的存储空间。

2、实现复杂度更高

在实现双向链表的过程中需要维护两个指针域，包括对头结点、尾节点的特殊处理，一个节点既有前驱也有后继，实现起来比单向链表更复杂。

3、插入和删除操作可能更慢

相对于单向链表，在双向链表中插入或删除一个节点，需要同时修改前驱节点的 next 指针和后继节点的 prev 指针，操作比较复杂，并且需要处理指针的指向关系，所以在某些情况下，双向链表的插入和删除操作可能不如单向链表快速。

4、需要更多的指针操作

相对于单向链表，双向链表的每个节点维护了两个指针，需要更多的指针操作来维护整个链表。

二、单链表简介

1、概念

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素（数据元素的映象）+ 指针（指示后继元素存储位置），元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性链表（单链表），单链表是链式存取的结构。

2、单链表定义

c语言结构定义：

typedef char DataType; //假设结点的数据域类型为字符typedef struct node{ //结点类型定义DataType data; //结点的数据域struct node *next;//结点的指针域}ListNode;typedef ListNode *LinkList;ListNode *p;LinkList head;

注意：

3、单链表的建立

单链表的建立有头插法、尾插法两种方法。

头插法：

单链表是用户不断申请存储单元和改变链接关系而得到的一种特殊数据结构，将链表的左边称为链头，右边称为链尾。头插法建单链表是将链表右端看成固定的，链表不断向左延伸而得到的。头插法最先得到的是尾结点。

由于链表的长度是随机的，故用一个while循环来控制链表中结点个数。假设每个结点的值都大于O，则循环条件为输入的值大于o。申请存储空间可使用malloc()函数实现，需设立一申请单元指针，但malloc()函数得到的指针并不是指向结构体的指针，需使用强制类型转换，将其转换成结构体型指针。刚开始时，链表还没建立，是一空链表，head指针为NULL。链表建立的过程是申请空间、得到数据、建立链接的循环处理过程。

尾插法：

若将链表的左端固定，链表不断向右延伸，这种建立链表的方法称为尾插法。尾插法建立链表时，头指针固定不动，故必须设立一个搜索指针，向链表右边延伸，则整个算法中应设立三个链表指针，即头指针head、搜索指针p2、申请单元指针pl。尾插法最先得到的是头结点。

三、双链表简介

1、概念

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

2、链表的操作

线性表的双向链表存储结构：

typedef struct DuLNode{ElemType data;struct DuLNode *prior,*next;}DuLNode,*DuLinkList;

带头结点的双向循环链表的基本操作：

void InitList(DuLinkList L){ /* 产生空的双向循环链表L */L=(DuLinkList)malloc(sizeof(DuLNode));if(L)L->next=L->prior=L;elseexit(OVERFLOW);}

销毁双向循环链表L：

void DestroyList(DuLinkList L){DuLinkList q,p=L->next; /* p指向名列前茅个结点 */while(p!=L) /* p没到表头 */{q=p->next;free(p);p=q;}free(L);L=NULL;}

延伸阅读1：动态存储函数

上一篇

算法和数据结构什么关系?

下一篇

trello收费吗?