双链表的操作示例（附代码）

什么是双链表？

双链表是在操作系统中常用的数据结构，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱，其结点组成如下：

其示意图举例如下：

双链表的操作示例

1、双链表结点定义：

/* 数据元素类型 */
typedef int Type;

/* 双链表结点结构体 */
typedef struct _DListNode
{
    struct _DListNode * prior; /* 指向直接前趋结点 */
    struct _DListNode * next;  /* 指向直接后继结点 */
    Type data;		       /* 数据 		   */		
}DListNode;

2、相关操作示例

/* 函数声明 */
static DListNode *dlist_create(void);
static int dlist_find(DListNode *dlist, Type find_data);
static DListNode *dlist_change(DListNode *dlist, int pos, Type new_data);
static DListNode *dlist_insert(DListNode *dlist, Type insert_data, int pos);
static DListNode *dlist_delete(DListNode *dlist, Type del_data);
static void dlist_print_int(DListNode *dlist);

（1）创建一个双链表：（5，2，0，13，14）

示意图：

代码：

static DListNode *dlist_create(void)
{
  /* 创建第一个结点 */
  DListNode *node = (DListNode*)malloc(sizeof(DListNode));
  node->prior = NULL;
  node->next = NULL;
  node->data = list[0];

  /* 创建头指针并指向第一个结点 */
  DListNode *head = node;

  /* 创建其它结点并链接成双链表 */
  for (int i = 1; i < LEN; i++)
  {
    /* 创建新结点 */
    DListNode *new_node = (DListNode*)malloc(sizeof(DListNode));	
    new_node->next = NULL;		
    new_node->prior = head;	/* 关键点1：新结点的prior指针指向前驱结点 */
    new_node->data = list[i];

    /* 改变前驱结点的next指针指向 */
    head->next = new_node;	/* 关键点2：前驱结点的next指针指向新结点 */

    /* 头指针后移 */
    head = head->next;
  }

  return node;
}

（2）元素查找：

static int dlist_find(DListNode *dlist, Type find_data)
{
  DListNode* temp = dlist;
  int pos = 1;

  while (temp)
  {
    if (find_data == temp->data)
    {
      return pos;	
    }
    else
    {
      temp = temp->next;
      pos++;
    }
  }

  return ERROR;
}

（3）元素替换：

static DListNode *dlist_change(DListNode *dlist, int pos, Type new_data)
{
  DListNode* temp = dlist;

  for (int i = 1; i < pos; i++)
  {
    temp = temp->next;
  }
  temp->data = new_data;

  return dlist;
}

（4）结点插入：

头部插入：

中间插入：

尾部插入：

static DListNode *dlist_insert(DListNode *dlist, Type insert_data, int pos)
{	
  /* 创建新结点待插入 */
  DListNode *new_node = (DListNode*)malloc(sizeof(DListNode));	
  new_node->next = NULL;
  new_node->prior = NULL;
  new_node->data = insert_data;

  if (pos > LEN + 1)
  {
    printf("插入的位置错误!\n");
  }

  /* 头部插入 */
  if (1 == pos)
  {
    dlist->prior = new_node; /* 步骤1 */	 
    new_node->next = dlist;  /* 步骤2 */
    dlist = new_node;	     /* 步骤3 */
  }
  else
  {
    DListNode *temp = dlist;
    for (int i = 1; i < pos-1; i++)
    {
      temp = temp->next;
    }
    /* 中间插入 */
    if (temp->next != NULL)
    {
      new_node->next = temp->next;	/* 步骤1 */
      new_node->prior = temp;		/* 步骤2 */
      temp->next->prior = new_node;	/* 步骤3 */
      temp->next = new_node;		/* 步骤4 */
    }
    /* 尾部插入 */
    else
    {
      temp->next = new_node;	/* 步骤1 */
      new_node->prior = temp;   /* 步骤2 */
    }
  }

  return dlist;
}

（5）结点删除：

static DListNode *dlist_delete(DListNode *dlist, Type del_data)
{
  DListNode *temp = dlist;

  while (temp)
  {
    if (del_data == temp->data)
    {
      temp->next->prior = temp->prior;
      temp->prior->next = temp->next;
      free(temp);
      return dlist;
    }
    temp = temp->next;
  }

  return dlist;
}

3、验证

主函数：

int main(void)
{
  printf("创建一个双链表:");
  DListNode *dlist = dlist_create();
  dlist_print_int(dlist);

  printf("元素13所在的位置是:");
  int pos = dlist_find(dlist, 13);
  if (ERROR == pos)
  {
    printf("该元素不存在。\n");
  }
  else
  {
    printf("%d\n", pos);
  }

  printf("把第1个位置的元素替换为2020得到新的双链表为:");
  dlist = dlist_change(dlist, 1, 2020);
  dlist_print_int(dlist);

  printf("第2个位置插入888得到新的双链表为:");
  dlist = dlist_insert(dlist, 888, 2);
  dlist_print_int(dlist);

  printf("删除元素2得到新的双链表为：");
  dlist = dlist_delete(dlist, 2);
  dlist_print_int(dlist);

  return 0;
}