使用C语言实现双向链表 |21xrx.com

使用C语言实现双向链表

2023-06-18 06:25:29 深夜i -- --

C语言双向链表节点

双向链表是一种常见的数据结构，它可以实现O(1)时间复杂度的插入和删除操作。在C语言中使用双向链表可以很方便地实现许多算法和数据结构。下面我们将详细介绍如何使用C语言编写双向链表。

1.定义链表节点结构体

首先我们需要定义一个结构体来表示链表的每个节点，这里包含了一个指向前驱节点和后继节点的指针，以及一个节点值。


typedef struct node {
  int data;      //节点值
  struct node *next;  //指向后继节点的指针
  struct node *prev;  //指向前驱节点的指针
} Node;

2.创建链表对象

我们定义一个链表对象来表示整个链表。它包含了指向链表头、尾节点的指针，以及链表中节点的总数。


typedef struct linked_list {
  Node *head;     //指向链表头的指针
  Node *tail;     //指向链表尾的指针
  int size;      //链表中节点数量
} LinkedList;

3.初始化链表

初始化链表时我们需要为链表头尾节点分配内存，并将链表中节点数设为0。


void initialize(LinkedList *list) {
  list->head = (Node *)malloc(sizeof(Node));
  list->tail = (Node *)malloc(sizeof(Node));
  list->head->prev = NULL;
  list->head->next = list->tail;
  list->tail->prev = list->head;
  list->tail->next = NULL;
  list->size = 0;
}

4.插入节点

我们可以分别在链表头和尾部插入一个节点。这里以插入尾节点为例。


void insert(LinkedList *list, int data) {
  Node *node = (Node *)malloc(sizeof(Node));
  node->data = data;
  node->next = list->tail;
  node->prev = list->tail->prev;
  list->tail->prev->next = node;
  list->tail->prev = node;
  list->size++;
}

5.删除节点

删除节点时我们可以根据节点值在链表中查找该节点，并删除节点。


int erase(LinkedList *list, int data) {
  Node *p = list->head->next;
  while (p != list->tail) {
    if (p->data == data) {
      p->prev->next = p->next;
      p->next->prev = p->prev;
      free(p);
      list->size--;
      return 1;
    }
    p = p->next;
  }
  return 0;
}

使用C语言实现双向链表可以很方便地实现许多算法和数据结构。在实际编程中，我们需要注意双向链表的各项细节，比如链表中的节点顺序、指针的正确性等。如果使用不当可能导致程序错误。

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

下一篇: Java岗位大爆发再不拥抱Java就OUT了！

评论区

()

相似文章