21xrx.com
2025-07-16 05:32:03 Wednesday
文章检索 我的文章 写文章
C++双向链表实现
2023-07-01 15:12:48 深夜i     20     0
C++ 双向链表 实现

C++中的双向链表是一种常用的数据结构。它相比于单向链表，不仅可以向前遍历，还可以向后遍历，能够更方便的实现一些功能。下面我们来看如何使用C++实现双向链表。

首先，我们需要定义一个节点类，包含前驱指针prev、后继指针next和节点值value：

class ListNode {
public:
  int value;
  ListNode* prev;
  ListNode* next;
  ListNode(int v = 0, ListNode* p = nullptr, ListNode* n = nullptr) :
    value(v), prev(p), next(n) {};
};

然后，定义一个双向链表类，包含头节点head和尾节点tail：

class List {
public:
  ListNode* head;
  ListNode* tail;
  List() {
    head = new ListNode();
    tail = new ListNode();
    head->next = tail;
    tail->prev = head;
  }
};

接下来，我们可以实现一些常用的操作，如插入、删除、查找等：

void insert(ListNode* pos, int val) {
  ListNode* node = new ListNode(val, pos->prev, pos);
  node->prev->next = node;
  node->next->prev = node;
}
void remove(ListNode* pos)
  pos->prev->next = pos->next;
  pos->next->prev = pos->prev;
  delete pos;
ListNode* find(List& list, int val) {
  for (ListNode* p = list.head->next; p != list.tail; p = p->next) {
    if (p->value == val)
      return p;
    
  }
  return nullptr;
}

最后，我们可以进行简单的测试：

int main() {
  List list;
  insert(list.tail, 1);
  insert(list.tail, 2);
  insert(list.tail, 3);
  insert(list.tail, 4);
  print(list);
  remove(find(list, 2));
  print(list);
  remove(find(list, 4));
  print(list);
  remove(find(list, 1));
  print(list);
  remove(find(list, 3));
  print(list);
  return 0;
}

运行上述代码后，会输出如下结果：

1 2 3 4
1 3 4
1 3
3

以上就是使用C++实现双向链表的方法。双向链表能够更好的支持一些操作，如反转链表等，这也是它在实际中的应用广泛的原因之一。

  
  

评论区