数据结构与算法-单链表

发表于 更新于 分类于 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 5 分钟

链表是线性结构中的一种，采用的数据存储方式是链式存储，链式存储是一种逻辑结构，不像数组一样使用连续的存储空间，而是通过结构体和指针将每个元素连接在一起，所以是自适应内存大小的，理论上来说无论多大的数据都能保存下来，前提是不超过机器的上限

单链表

单链表的结构就像下图（本文图片均由本灵魂画手使用 OneNote 作画）一样，利用结构体，存储数据的同时额外开辟一份空间用来保存指针，而这个指针则是用于指向下一个节点

存储方式大概就像下图一样，通过指针将数据像烤串一样串起来

初始化

结构体代码如下

1
2
3
4
5
// 节点
struct Node {
  ElemType val;  // 节点值
  struct Node* next;  // 下一个节点
};

像任何数据类型一样，链表也可以初始化，但首先要创建一个初始化方法，首先要为链表开辟内存，并判断是否创建失败，如果失败就返回 NULL

1
2
3
4
5
6
7
8
9
10
11
12
13
// 初始化链表
Node* Init(){
  Node* head = (Node*)malloc(sizeof(Node));  // 创建头节点
  // 判断头节点是否创建成功
  if(head == NULL){
    printf("malloc failure\n");
    return NULL;
  }
  printf("Init success\n");
  // 头节点的下一个节点为NULL
  head->next = NULL;
  return head;
}

基本操作

插入元素

初始化完成以后就可以得到一个空的链表了大概长这样

头部插入

头部插入法，顾名思义，就是从头部插入元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 头部插入节点
Node* InsertHead(Node* head, ElemType val){
  // 创建新节点
  Node* p = (Node*)malloc(sizeof(Node));
  if(p == NULL){
    printf("malloc failure\n");
    return head;
  }
  // 设置新节点的值
  p->val = val;
  // 新节点的下一个指向头节点的下一个节点
  p->next = head->next;
  // 新节点成为头节点的下一个节点
  head->next = p;
  printf("InsertHead success\n");
  return head;
}

尾部插入

尾部插入跟头部插入一样，只不过是将新元素放到表尾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 尾部插入节点
Node* InsertTail(Node* head, ElemType val){
  // 创建新节点
  Node* p = (Node*)malloc(sizeof(Node));
  if(p == NULL){
    printf("malloc failure\n");
    return head;
  }
  p->val = val;
  // 新节点的下一个指向NULL
  p->next = NULL;
  // 判断头节点是否为空
  if(head->next == NULL){
    // 头节点的下一个节点为新节点
    head->next = p;
  } else{
    // 循环遍历链表
    Node* q = head->next;
    while(q->next != NULL){
      // 下一个节点不为空，则继续循环
      q = q->next;
    }
    // 尾节点的下一个节点为新节点
    q->next = p;
  }
  printf("InsertTail success\n");
  return head;
}

中间插入

找出要插入的位置，然后将指针指向新元素，并把新元素的指针指向旧元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 中间插入节点
Node * InsertMiddle (Node * head, ElemType val, int position) {
  // 查找插入位置
  Node * temp = head;
  for (int i = 0; i < position; i++) {
    temp = temp->next;
    if (temp == NULL) {
      // 插入位置不存在
      printf ("insert position error\n");
      return head;
    }
  }
  // 创建新节点
  Node * p = (Node *) malloc (sizeof (Node));
  if (p == NULL) {
    printf ("malloc failure\n");
    return head;
  }
  p->val = val;
  // 新节点的下一个指向temp的下一个节点
  p->next = temp->next;
  // temp的下一个节点指向新节点
  temp->next = p;
  printf ("InsertMiddle success\n");
  return head;
}

删除元素

跟插入元素一样，进行反向操作即可

头部删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 头部删除节点
Node * DeleteHead (Node * head) {
  // 判断头节点是否为空
  if (head->next == NULL) {
    printf ("head is empty\n");
    return head;
  }
  // 删除头节点
  Node * p = head->next;
  head->next = p->next;
  free (p); // 释放内存
  printf ("DeleteHead success\n");
  return head;
}

尾部删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 尾部删除节点
Node * DeleteTail (Node * head) {
  // 判断头节点是否为空
  if (head->next == NULL) {
    printf ("head is empty\n");
    return head;
  }
  // 循环遍历链表
  Node * p = head->next, * q; // p代表当前节点，q代表前驱节点
  while (p->next != NULL) {
    q = p; // p成为后继节点的前驱节点
    p = p->next; // p指向后继节点
  }
  // 将q的后继指向NULL
  q->next = NULL;
  free (p); // 释放内存
  printf ("DeleteTail success\n");
  return head;
}

中间删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// 中间删除节点
Node * DeleteMiddle (Node * head, int position) {
  Node * p = head, * q; // p代表当前节点，q代表前驱节点
  // 查找删除位置
  for (int i = 0; i < position; i++) {
    q = p; // p成为后继节点的前驱节点
    p = p->next;
    if (p == NULL) {
      // 删除位置不存在
      printf ("delete position error\n");
      return head;
    }
  }
  q->next = p->next; // 前驱节点的后继指向p的后继
  free (p); // 释放内存
  printf ("DeleteMiddle success\n");
  return head;
}

修改元素

修改元素跟中间插入差不多，只是不用新增节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 修改节点的值
Node* Modify (Node * head, ElemType val, int position) {
  Node * p = head;
  // 查找修改位置
  for (int i = 0; i < position; i++) {
    p = p->next;
    if (p == NULL) {
      // 修改位置不存在
      printf ("modify position error\n");
      return head;
    }
  }
  p->val = val;
  printf ("Modify success\n");
  return head;
}

遍历链表

为了方便修改，我并没有明确元素值的数据类型，所以输出语句就使用 C++ ，这样就可以输出任意类型了，C 我不知道怎么做到

1
2
3
4
5
6
7
8
9
void Display (Node * h) {
  Node * p;
  p = h->next;
  while (p != NULL) {
    std::cout << p->val;
    p = p->next;
  }
  std::cout << std::endl;
}

销毁链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 销毁链表
void Destroy (Node * head) {
  Node * p;
  // 释放链表中的节点
  while (head->next != NULL) {
    p = head->next;
    head->next = p->next;
    free (p);
  }

  if (p == NULL) {
    printf ("Destroy success\n");
  }
}

测试代码

写完以上代码后，就可以编写 main() 方法对他们进行测试了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
int main (int argc, char * argv []) {

  // 初始化链表
  struct Node * head = Init ();

  // 头部插入节点
  InsertHead (head, 'a');
  InsertHead (head, 'b');
  Display (head);

  // 尾部插入节点
  InsertTail (head, 'c');
  InsertTail (head, 'd');
  Display (head);

  // 中间插入节点
  InsertMiddle (head, 'e', 2);
  Display (head);

  // 头部删除节点
  DeleteHead (head);
  Display (head);

  // 尾部删除节点
  DeleteTail (head);
  Display (head);

  // 中间删除节点
  DeleteMiddle (head, 2);
  Display (head);

  // 修改节点
  Modify (head, 'f', 2);
  Display (head);

  // 销毁链表
  Destroy (head);

  return 0;
}

仓库地址：https://github.com/jesspig/data-structures-and-algorithms/tree/main/linked-list