C++和python实现单链表及其原理

实现单链表及其原理

基本概念

单链表（Singly Linked List）是一种链式存储结构，由一系列节点组成，每个节点包含数据域和一个指向下一个节点的指针域。相比于数组，单链表的插入、删除操作更加方便高效，但是单链表的查询操作效率较低。

C++实现

节点定义

在C++实现中，需要先定义节点(struct Node)，包含数据域(data)和指针域(next)。

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

创建操作

创建操作可以分为头插法和尾插法。在头插法中，新节点插入到链表的头部；在尾插法中，新节点插入到链表的尾部。

以头插法为例，具体步骤如下：

• 创建新节点(newNode)；
• 将newNode的指针域(next)指向原链表的头节点(head)；
• 将头指针(head)指向newNode。

void addNode(Node *&head, int data) {
  Node *newNode = new Node;
  newNode->data = data;
  newNode->next = head;
  head = newNode;
}

查找操作

查找操作可以分为按值查找和按索引查找。按值查找的思路是依次遍历链表的每个节点，直到找到值为目标值的节点。按索引查找的思路是从头节点开始，一直向后遍历指定的次数，直到达到目标节点。

以按值查找为例，具体步骤如下：

• 从头节点(head)开始遍历链表；
• 每次遍历时，判断当前节点是否为目标节点，如果是则返回该节点的指针，否则继续遍历；
• 如果遍历到链表尾部都未找到目标节点，则返回NULL。

Node* searchNode(Node *head, int data) {
  Node *current = head;
  while (current != NULL) {
    if (current->data == data) {
      return current;
    }
    current = current->next;
  }
  return NULL;
}

删除操作

删除操作可以分为按值删除和按索引删除。按值删除的思路是先查找到目标节点，然后将目标节点从链表中删除。按索引删除的思路是先遍历到目标节点的前一个节点，然后将目标节点从链表中删除。

以按值删除为例，具体步骤如下：

• 先查找到目标节点(targetNode)的前一个节点(preNode)；
• 将preNode的指针域(next)指向targetNode的下一个节点；
• 释放targetNode的内存。

void deleteNode(Node *&head, int data) {
  Node *preNode = NULL;
  Node *current = head;
  while (current != NULL) {
    if (current->data == data) {
      if (preNode == NULL) {
        head = current->next;
      } else {
        preNode->next = current->next;
      }
      delete current;
      return;
    }
    preNode = current;
    current = current->next;
  }
}

Python实现

节点定义

在Python实现中，需要先定义节点(class Node)，包含数据域(data)和指针域(next)。

class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

创建操作

创建操作可以分为头插法和尾插法。与C++实现类似，在头插法中，新节点插入到链表的头部；在尾插法中，新节点插入到链表的尾部。

以尾插法为例，具体步骤如下：

• 创建新节点(new_node)；
• 遍历链表，找到尾节点;
• 将尾节点的指针域(next)指向new_node。

def add_node(head, data):
  new_node = Node(data)
  if head is None:
    head = new_node
    return head
  current = head
  while current.next is not None:
    current = current.next
  current.next = new_node
  return head

查找操作

查找操作可以分为按值查找和按索引查找。与C++实现类似，按值查找的思路是依次遍历链表的每个节点，直到找到值为目标值的节点。按索引查找的思路与C++实现类似，不再赘述。

以按值查找为例，具体步骤如下：

• 从头节点(head)开始遍历链表；
• 每次遍历时，判断当前节点是否为目标节点，如果是则返回该节点，否则继续遍历；
• 如果遍历到链表尾部都未找到目标节点，则返回None。

def search_node(head, data):
  current = head
  while current is not None:
    if current.data == data:
      return current
    current = current.next
  return None

删除操作

删除操作可以分为按值删除和按索引删除。与C++实现类似，按值删除的思路是先查找到目标节点，然后将目标节点从链表中删除。按索引删除的思路与C++实现类似，不再赘述。

以按值删除为例，具体步骤如下：

• 先查找到目标节点(target_node)的前一个节点(pre_node)；
• 将pre_node的指针域(next)指向target_node的下一个节点；
• 释放target_node的内存。

def delete_node(head, data):
  if head is None:
    return None
  if head.data == data:
    head = head.next
    return head
  pre_node = head
  current = head.next
  while current is not None:
    if current.data == data:
      pre_node.next = current.next
      return head
    pre_node = current
    current = current.next
  return head

示例说明

示例1：C++单链表操作

#include <iostream>
using namespace std;

int main() {
  // 创建头节点
  Node *head = new Node;
  head->data = 1;
  head->next = NULL;

  // 进行添加操作
  addNode(head, 2);
  addNode(head, 3);

  // 进行查找操作
  Node *targetNode = searchNode(head, 2);
  if (targetNode != NULL) {
    cout << "Found the target node, data is " << targetNode->data << endl;
  } else {
    cout << "The target node is not found." << endl;
  }

  // 进行删除操作
  deleteNode(head, 2);

  // 遍历链表
  cout << "The nodes in the linked list: ";
  Node *current = head;
  while (current != NULL) {
    cout << current->data << " ";
    current = current->next;
  }
  cout << endl;

  // 释放内存
  current = head;
  while (current != NULL) {
    Node *temp = current;
    current = current->next;
    delete temp;
  }

  return 0;
}

输出结果为：

Found the target node, data is 2
The nodes in the linked list: 3 1 

示例2：Python单链表操作

# 创建头节点
head = Node(1)

# 进行添加操作
head = add_node(head, 2)
head = add_node(head, 3)

# 进行查找操作
target_node = search_node(head, 2)
if target_node is not None:
  print('Found the target node, data is', target_node.data)
else:
  print('The target node is not found.')

# 进行删除操作
head = delete_node(head, 2)

# 遍历链表
nodes = []
current = head
while current is not None:
  nodes.append(str(current.data))
  current = current.next
print('The nodes in the linked list: ' + ' -> '.join(nodes))

# 释放内存（Python自动管理内存，不需要手动释放）

输出结果为：

Found the target node, data is 2
The nodes in the linked list: 1 -> 3