双向链表的概念

前面章节讨论的链式存储结构的结点中只有一个指示直接后继的指针域。当访问链表中结点时，需要从某个结点出发顺着next指针域寻查其他结点。若要寻查结点的直接前驱，则必须从表头指针出发。在单链表中，这种方式在查找直接后继结点的时间复杂度为，而查找直接前驱的时间复杂度为；然而对于双向链表（Double Linked List），查找直接后继结点和直接前驱结点的时间复杂度都为。

双向结点可以简称为双链表，顾名思义每个数据结点都有两个指针，分别指向直接后继和直接前驱。如图所示：

双向链表的存储结构

从图1中可以看到，双向链表中各节点包含以下3部分信息（如图2所示）：

• 指针域：用于指向当前节点的直接前驱节点。
• 数据域：用于存储数据元素。
• 指针域：用于指向当前节点的直接后继节点。

【算法代码】

#define ElemType int
typedef struct _LinkedListNode
{
  ElemType data;				//数据类型
  struct _LinkedListNode* pre;	//指向直接前继元素的指针
  struct _LinkedListNode* next;	//指向直接后继元素的指针
}LinkedListNode, *LinkedList;//ListNode表示结点的类型，LinkedList表示指向ListNode结点类型的指针类型

其中，data表示数据，其可以是简单的类型（如int, double等等），也可以是复杂的结构体（struct类型）；pre代表的是前驱指针，它永远指向当前结点的前一个结点；注意，如果当前结点是头结点，则pre指针为空；next代表的是后继指针，它永远指向当前结点的下一个结点，注意，如果当前结点是尾结点，则next指针为空。

双向链表的创建

双向链表的创建过程和单链表创建过程相同，它也是一种动态结构。整个可用存储空间可为多个链表共同享用，每个链表占用的空间不需预先分配划定，而是由系统按需即时生成。因此，建立线性表的链式存储结构的过程就是一个动态生成链表的过程。从空表的初始状态开始，依次建立各元素的结点，并逐个插入链表。与单链表不同的是，pre指针域指向前驱结点，next指针域指向后继结点。双向链表根据结点插入位置的不同，链表的创建方法也可以分为头插法和尾插法。

【头插法】

头插法是指每次申请一个新结点，读入相应的数据元素值，然后将新结点从链表的头部之后逐个插入。

【算法代码】

//O(1)
LinkedList LinkedListCreateByHeader(LinkedList slist, ElemType elem)
{
  LinkedListNode* header = nullptr;
  if (nullptr == slist)
  {
    header = (LinkedListNode*)malloc(sizeof(LinkedListNode));
    if (nullptr == header)
    {
      cout << "创建链表头失败" << endl;
      return nullptr;
    }
    else
    {
      header->data = elem;
      header->pre = nullptr;
      header->next = nullptr;
      return header;
    }
  }
  else
  {
    LinkedListNode* node = (LinkedListNode*)malloc(sizeof(LinkedListNode));
    if (nullptr == node)
    {
      cout << "创建结点失败" << endl;
      return nullptr;
    }
    else
    {
      LinkedListNode* clist = slist;
      node->data = elem;
      node->next = clist;
      clist->pre = node;
      header = node;
      return header;
    }
  }
}

头插法建立双向链表的时间复杂度为。

【尾插法】

尾插法是通过将新结点逐个插入到链表的尾部来创建链表。同头插法一样，每次申请一个新结点，读入相应的数据元素值。不同的是，为了使新结点能插入到链表尾部，必须遍历整个线性链表找到尾指针，然后从尾指针后插入新结点。

【算法代码】

//O(n)
LinkedList LinkedListCreateByTail(LinkedList slist, ElemType elem)
{
  if (nullptr == slist)
  {
    LinkedListNode* header = (LinkedListNode*)malloc(sizeof(LinkedListNode));
    if (nullptr == header)
    {
      cout << "创建链表头失败" << endl;
      return nullptr;
    }
    else
    {
      header->data = elem;
      header->pre = nullptr;
      header->next = nullptr;
      return header;
    }
  }
  else
  {
    LinkedListNode* node = (LinkedListNode*)malloc(sizeof(LinkedListNode));
    if (nullptr == node)
    {
      cout << "创建结点失败" << endl;
      return nullptr;
    }
    else
    {
      LinkedListNode* header = slist;
      LinkedListNode* clist = slist;
      for (clist = slist; clist->next != nullptr; clist = clist->next);//寻找尾结点
      node->data = elem;
      node->pre = clist;
      node->next = nullptr;
      clist->next = node;
      return header;
    }
  }
}

尾插法建立双向链表的时间复杂度为。

双向链表的取值

双向链表的取值与单链表取值相同，只能从链表的首元结点出发，顺着链域next逐个结点向下访问。

【算法代码】

//O(n)
LinkedList GetLinkedList(LinkedList slist, int pos)
{
  if (nullptr == slist)
  {
    cout << "空链表" << endl;
    return nullptr;
  }
  else if (pos <= 0)
  {
    cout << "输入位置错误" << endl;
    return slist;
  }
  else
  {
    int index = 1;
    LinkedListNode* clist = slist;
    for (clist = slist; index < pos && clist->next != nullptr; clist = clist->next, ++index);
    if (index < pos)
    {
      cout << "寻找位置 " << pos << " 超出链表长度" << index << " ，默认输出尾结点" << endl;
    }
    return clist;
  }
}

双向链表取值的时间复杂度为。

双向链表的插入

双向链表插入过程如图所示：

双向链表插入新结点时，根据插入的位置不同，分为以下3种情况：

• 插入到链表的头部（头节点之后），作为首元节点。
• 插入到链表中间的某个位置。
• 插入到链表的尾部，作为链表中最后一个数据元素。

对于每一次的双向链表的插入操作，首先需要创建一个独立的结点并通过malloc操作开辟相应的空间；其次选中这个新创建的独立结点，将其的pre指针指向所需插入位置的前一个结点；同时，其所需插入的前一个结点的next指针修改指向为该新的结点，同理，该新的结点的next指针将会指向一个原本的下一个结点，而修改下一个结点的pre指针为指向新结点自身。

【算法代码】

//O(n)
LinkedList LinkedListInsert(LinkedList slist, ElemType elem, int pos)
{
  if (nullptr == slist)
  {
    cout << "空链表" << endl;
    return nullptr;
  }
  else if (pos <= 0)
  {
    cout << "输入位置错误" << endl;
    return slist;
  }
  else
  {
    LinkedListNode* nlist = (LinkedListNode*)malloc(sizeof(LinkedListNode));
    if (nullptr == nlist)
    {
      cout << "创建结点失败" << endl;
    }
    else
    {
      if (1 == pos)
      {
        nlist->data = elem;
        nlist->pre = nullptr;
        nlist->next = slist;	//指向下一个结点
        slist->pre = nlist;
        slist = nlist;//插入的结点作为新的头结点
      }
      else
      {
        int index = 1;
        LinkedListNode* clist = slist;
        for (clist = slist; index < pos && clist->next != nullptr; clist = clist->next, ++index);
        if (index == pos)
        {
          nlist->data = elem;
          nlist->next = clist;		//指向下一个结点
          nlist->pre = clist->pre;
          clist->pre->next = nlist;	//指向插入结点
          clist->pre = nlist;
        }
        else
        {
          cout << "插入位置 " << pos << " 超出链表长度" << index << " ，默认插入到尾结点"<< endl;
          nlist->data = elem;
          nlist->next = nullptr;
          nlist->pre = clist;
          clist->next = nlist;
        }
      }
    }
    return slist;
  }
}

双向链表插入的时间复杂度为。

双向链表的删除

双向链表删除过程如图所示：

从图中可以看出，删除操作过程是选择需要删除的结点，将前一个结点的next指针指向自己的下一个结点；同时，将一个结点的pre指针修改指向自己的上一个结点；最后释放需要删除的结点。

【算法代码】

//O(n)
LinkedList LinkedListDelete(LinkedList slist, int pos)
{
  if (nullptr == slist)
  {
    cout << "空链表" << endl;
    return nullptr;
  }
  else if (pos <= 0)
  {
    cout << "输入位置错误" << endl;
    return slist;
  }
  else
  {
    LinkedListNode* nlist = nullptr;
    if (1 == pos) //删除头结点
    {
      nlist = slist;
      slist = slist->next;
      free(nlist);
    }
    else
    {
      int index = 1;	//头结点位置
      LinkedListNode* clist = slist;//当前结点
      for (clist = slist; index < pos && clist->next != nullptr; clist = clist->next, ++index);
      if (index == pos)
      {
        nlist = clist;
        clist->next != nullptr ? clist->pre->next = clist->next : clist->pre->next = nullptr;
        clist->next != nullptr ? clist->next->pre = clist->pre : nullptr;
        free(nlist);
      }
      else
      {
        cout << "删除位置 " << pos << " 超出链表最大长度 " << index << endl;
      }
      return slist;
    }
    return slist;
  }
}

双向链表删除的时间复杂度为O(n)。

获取链表长度

遍历链表中每一个结点，直到指针域next为空结束，则遍历的次数就是链表的长度。

【算法代码】

//O(n)
int GetLinkedListLength(LinkedList slist)
{
  if (nullptr == slist)
  {
    cout << "空链表" << endl;
    return 0;
  }
  else
  {
    int index = 1;
    LinkedListNode* clist = slist;
    for (clist = slist; clist->next != nullptr; clist = clist->next, ++index);
    return index;
  }
}

完整代码

GitHub: https://github.com/MrYuxiangZhu/DataStructure/tree/master/01.%20LinkedList