如何在C++程序中创建链表

链表是一种常用的数据结构，它在C++程序中的应用非常广泛。本文将介绍如何在C++程序中创建链表，并提供了一些基本的链表操作示例。通过本文的学习，读者将了解链表的概念、创建链表的方法和常见的链表操作技巧。

一、链表简介

链表是一种常用的数据结构,它通过一系列节点在内存中实现存储和访问。每个节点由两部分组成:数据域和指针域。数据域存储节点的数据,指针域存储下一个节点的地址。链表没有固定大小,可以动态地调整节点个数。

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

链表可以是一个简单的单向链表,也可以是双向链表。链表没有随机访问的能力,需要通过指针逐个访问节点。但它提供了高效的插入和删除操作。

二、在C++中创建单向链表

要在C++程序中创建单向链表,需要实现链表节点类和链表类。链表节点类如下:

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

链表类中需要一个头指针head指向链表的头节点。可以实现如下操作:

• 初始化一个空链表
• 在链表头添加新节点
• 在链表尾部添加新节点
• 删除指定节点
• 查找指定节点

示例代码:

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);
  }

  // 其他操作代码
};

三、创建双向链表

双向链表比单向链表增加了一个prev指针,使得节点可以向前和向后访问。实现一个双向链表,节点类如下:

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

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

双向链表类的实现与单向链表类似,需要维护一个头指针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;
    }
  }
  
  // 其他操作
};

四、总结

• 链表通过指针将节点在内存中链接起来,可以动态地调整大小
• 单向链表只能向一个方向遍历,双向链表可以双向遍历
• 实现链表时需要编写节点类和链表类,包含操作链表的方法
• 链表是一种高效的插入和删除的数据结构

通过上述示例代码,可以在C++程序中实现链表功能,用于各种算法和程序中。链表是一种非常重要和常用的基础数据结构。