双链表

双链表：前面介绍的单链表中只有后继节点的地址，增加节点的一个指针域指向前趋节点后便成了双链表。

typedef struct dnode
{
 datatype data;
 struct dnode *next;
 struct dnode *prior;
}dlinklist, pdlinklist;

int DlistInsert(pdlinklist head, int i, datatype e)
{
 int j = 0;
 pdlinklist *p, *s;

 p = head;

//下面同样是首先找到要插入位置之前的那个节点。注意，判断结束的条件。

 while (j < i -1 && p->next != head)
 {
  p = p->next;
  j++;
 }

 if (j != i-1)
 {
  printf("Cannot insert the element");
  return 0;
 }

 s = (pdlinklist)malloc(sizeof(dlinklist));
 s->data = e;
 s->prior = p;
 s->next = p->next;
 p->next->prior = s;
 p->next = s;

 return 1;
}

int DListDelete(pdlinklist head, int i)
{
 int j = 0;
 plinklist p;
 p = head;

//下面同样是先找到要删除节点的前面一个节点
 while (j < i-1 && p->next != head)
 {
  p = p->next;
  j++;
 }

//下面节点的判断条件如下：

j ！= i-1：是么有找到节点。

i = 0： 是不能删除头节点。

p->next == head：要删除的节点不存在。

 

 if (j != i-1 ||i == 0 || p->next == head)
 {
  return 0;
 }

 p->next->next->prior = p;
 p->next = p->next->next;
 free(p->next);
}

 

链表总结：不管是单链表，双链表还是循环链表。最主要的操作就是插入和删除节点。算法都差不多：首先是要找到需要操作的位置，或者说是它的前一个节点。都是用一个变量j和对应位置上的节点p来表示。最后通过j来判断是否找到正确的位置。找到节点后操作就容易了。