資料結構與演算法：雙向鏈表詳解與實現

資料結構與演算法如同好基友，生死不相離。單講資料結構難見用處，結合演算法演示，方覺解決電腦問題之美妙。本文聚焦雙向鏈表。

雙向鏈表定義與結構

每個節點含兩個指標，分別指向直接前驅與直接後繼。從任一節點可雙向遍歷。通常採用帶頭節點的循環鏈表形式。

typedef struct _DOUBLE_LINK_NODE {
  int data;
  struct _DOUBLE_LINK_NODE *prev;
  struct _DOUBLE_LINK_NODE *next;
} DOUBLE_LINK_NODE;

頭節點 first：data 域可不存數據或存特殊值；prev 指向尾節點，next 指向首節點。滿足 p == p→prev→next == p→next→prev。

為何需要雙向鏈表？

如火車到站後倒退一站，無需掉頭——火車兩頭均可連接車頭，這就是雙向鏈表的生活實例。

核心操作實現（C++ 程式碼）

1. 節點創建

DOUBLE_LINK_NODE* CreateDoubleLink(int data) {
  DOUBLE_LINK_NODE* head = (DOUBLE_LINK_NODE*)malloc(sizeof(DOUBLE_LINK_NODE));
  ASSERT(head != NULL);
  head->data = data;
  head->prev = head->next = NULL;
  return head;
}

2. 插入操作

步驟：找位置 → 新節點後驅指向當前後驅 → 新節點前驅指向當前 → 當前後驅指向新節點 → 原後驅前驅指向新節點。

int insert_data_into_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data) {
  DOUBLE_LINK_NODE *pNode, *pIndex;
  if (!ppDLinkNode) return 0;
  if (!*ppDLinkNode) { *ppDLinkNode = CreateDoubleLink(data); return 1; }
  if (find_data_in_double_link(*ppDLinkNode, data)) return FALSE;
  pNode = CreateDoubleLink(data);
  pIndex = *ppDLinkNode;
  while (pIndex->next) pIndex = pIndex->next;
  pNode->prev = pIndex;
  pNode->next = pIndex->next;
  pIndex->next = pNode;
  return 1;
}

3. 刪除、查找、統計、列印

// 刪除
int delete_data_from_double_link(DOUBLE_LINK_NODE** ppDLinkNode, int data) {
  DOUBLE_LINK_NODE* pNode = find_data_in_double_link(*ppDLinkNode, data);
  if (!pNode) return 0;
  if (pNode == *ppDLinkNode) {
    if (!pNode->next) *ppDLinkNode = NULL;
    else { *ppDLinkNode = pNode->next; (*ppDLinkNode)->prev = NULL; }
  } else {
    if (pNode->next) pNode->next->prev = pNode->prev;
    pNode->prev->next = pNode->next;
  }
  free(pNode); return 1;
}

// 查找
DOUBLE_LINK_NODE* find_data_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode, int data) {
  DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;
  while (pNode) { if (data == pNode->data) return pNode; pNode = pNode->next; }
  return NULL;
}

// 統計
int count_number_in_double_link(const DOUBLE_LINK_NODE* pDLinkNode) {
  int count = 0;
  DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;
  while (pNode) { count++; pNode = pNode->next; }
  return count;
}

// 列印
void print_double_link_node(const DOUBLE_LINK_NODE* pDLinkNode) {
  DOUBLE_LINK_NODE* pNode = (DOUBLE_LINK_NODE*)pDLinkNode;
  while (pNode) { printf("%d\n", pNode->data); pNode = pNode->next; }
}

編寫測試程式驗證極為重要，務必補全。

本文出自「驛落黃昏」博客，轉載請保留出處：https://yiluohuanghun.blog.51cto.com/3407300/1262417