鏈表是一種常用的數(shù)據(jù)結(jié)構(gòu)，它在C++程序中的應(yīng)用非常廣泛。本文將介紹如何在C++程序中創(chuàng)建鏈表，并提供了一些基本的鏈表操作示例。通過本文的學(xué)習(xí)，讀者將了解鏈表的概念、創(chuàng)建鏈表的方法和常見的鏈表操作技巧。

一、鏈表簡介

鏈表是一種常用的數(shù)據(jù)結(jié)構(gòu),它通過一系列節(jié)點(diǎn)在內(nèi)存中實(shí)現(xiàn)存儲(chǔ)和訪問。每個(gè)節(jié)點(diǎn)由兩部分組成:數(shù)據(jù)域和指針域。數(shù)據(jù)域存儲(chǔ)節(jié)點(diǎn)的數(shù)據(jù),指針域存儲(chǔ)下一個(gè)節(jié)點(diǎn)的地址。鏈表沒有固定大小,可以動(dòng)態(tài)地調(diào)整節(jié)點(diǎn)個(gè)數(shù)。

struct Node {
  int data; 
  Node* next;
};

鏈表可以是一個(gè)簡單的單向鏈表,也可以是雙向鏈表。鏈表沒有隨機(jī)訪問的能力,需要通過指針逐個(gè)訪問節(jié)點(diǎn)。但它提供了高效的插入和刪除操作。

二、在C++中創(chuàng)建單向鏈表

要在C++程序中創(chuàng)建單向鏈表,需要實(shí)現(xiàn)鏈表節(jié)點(diǎn)類和鏈表類。鏈表節(jié)點(diǎn)類如下:

class ListNode {
public:
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(NULL) {}
};

鏈表類中需要一個(gè)頭指針head指向鏈表的頭節(jié)點(diǎn)?？梢詫?shí)現(xiàn)如下操作:

• 初始化一個(gè)空鏈表
• 在鏈表頭添加新節(jié)點(diǎn)
• 在鏈表尾部添加新節(jié)點(diǎn)
• 刪除指定節(jié)點(diǎn)
• 查找指定節(jié)點(diǎn)

示例代碼:

class LinkedList {
private:
  ListNode *head; 
public:
  LinkedList() {
    head = NULL;
  }

  void addHead(int val) {
    ListNode *node = new ListNode(val);
    node->next = head;
    head = node;
  }
  
  void append(int val) {
    if (head == NULL) {
      head = new ListNode(val);
      return;
    }
    ListNode *current = head;
    while (current->next != NULL) {
      current = current->next; 
    }
    current->next = new ListNode(val);
  }

  // 其他操作代碼
};

三、創(chuàng)建雙向鏈表

雙向鏈表比單向鏈表增加了一個(gè)prev指針,使得節(jié)點(diǎn)可以向前和向后訪問。實(shí)現(xiàn)一個(gè)雙向鏈表,節(jié)點(diǎn)類如下:

class DoublyListNode {
public:
  int val;
  DoublyListNode *next;
  DoublyListNode *prev;

  DoublyListNode(int x) : val(x), next(NULL), prev(NULL) {} 
};

雙向鏈表類的實(shí)現(xiàn)與單向鏈表類似,需要維護(hù)一個(gè)頭指針head和尾指針tail。示例代碼：

class DoublyLinkedList {
private:
  DoublyListNode *head;
  DoublyListNode *tail;

public:
  DoublyLinkedList() {
    head = NULL;
    tail = NULL;
  }

  void addHead(int val) {
    DoublyListNode *node = new DoublyListNode(val);
    if (head == NULL) {
      head = tail = node;
    } else {
      node->next = head;
      head->prev = node;
      head = node;
    }
  }
  
  // 其他操作
};

四、總結(jié)

• 鏈表通過指針將節(jié)點(diǎn)在內(nèi)存中鏈接起來,可以動(dòng)態(tài)地調(diào)整大小
• 單向鏈表只能向一個(gè)方向遍歷,雙向鏈表可以雙向遍歷
• 實(shí)現(xiàn)鏈表時(shí)需要編寫節(jié)點(diǎn)類和鏈表類,包含操作鏈表的方法
• 鏈表是一種高效的插入和刪除的數(shù)據(jù)結(jié)構(gòu)

通過上述示例代碼,可以在C++程序中實(shí)現(xiàn)鏈表功能,用于各種算法和程序中。鏈表是一種非常重要和常用的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)。