C++ 链表 |21xrx.com

C++ 链表

2023-07-05 05:16:27 深夜i 17 0

C++语言链表数据结构单向链表双向链表循环链表

C++ 链表是一种数据结构，用于存储一组元素，每个元素都有一个指针指向下一个元素。链表可以动态增长和缩小，而且插入和删除操作很快。这使得它成为一种常用的数据结构，常用于实现队列、栈和哈希表等数据结构。

在 C++ 中，链表可以使用指针来实现。指针是一个变量，它存储了另一个变量的地址。使用指针，我们可以在内存中分配空间来存储链表节点，并将它们连接成一个链表。这里有两种常见的链表实现：单链表和双链表。

单链表只包含一个指向下一个元素的指针，而双链表包含一个指向前一个元素的指针和一个指向下一个元素的指针。双链表允许我们在任意位置插入和删除元素。

在 C++ 中，我们可以使用类来表示链表节点。一个节点类通常包含两个成员变量：一个值和一个指向下一个节点的指针。一个链表类通常包含一个指针指向头节点，头节点不存储任何值。链表类还包含一些方法来插入、删除和访问元素。

下面是一个使用单链表实现栈的代码示例：

class ListNode {
public:
  int val;
  ListNode* next;
  ListNode(int x) : val(x), next(NULL) {}
};
class MyStack {
public:
  /** Initialize your data structure here. */
  MyStack()
    head = NULL;
  
  /** Push element x onto stack. */
  void push(int x) {
    ListNode* node = new ListNode(x);
    node->next = head;
    head = node;
  }
  /** Removes the element on top of the stack and returns that element. */
  int pop() {
    if (head == NULL)
      return -1;
    
    ListNode* temp = head;
    int val = temp->val;
    head = head->next;
    delete temp;
    return val;
  }
  /** Get the top element. */
  int top() {
    if (head == NULL)
      return -1;
    
    return head->val;
  }
  /** Returns whether the stack is empty. */
  bool empty()
    return head == NULL;
  
private:
  ListNode* head;
};

这个代码示例演示了如何使用单链表来实现一个栈。我们使用一个头节点来表示栈顶，每次 push 时将新元素放在头节点之前，每次 pop 时删除头节点，并返回它的值。

总之，链表是一种非常有用的数据结构，它允许我们动态地添加和删除元素。使用 C++ 中的指针和类，我们可以轻松地实现链表。

上一篇: idea打包java可执行jar包

下一篇: 阿里巨头的Node.js面试题

评论区

相似文章