搜索菜单
当前位置: 首页 > Python > Python与C语言单链表实现详解：结构、操作与代码解析

Python与C语言单链表实现详解：结构、操作与代码解析

陆遥
陆遥
发布时间：2026-10-13 | 6人浏览过
原创

本文深入解析单链表的存储结构与核心操作，涵盖头插、尾插、指定位置插入、删除、查找及排序等常用功能。通过Python与C语言两种主流编程语言的完整代码示例，对比展示单链表的动态内存管理优势与时间复杂度特性，帮助开发者掌握线性表链式存储的实现细节与最佳实践。

链表基本概念与特性

一、链表

链表是一种在物理存储单元上非连续、非顺序的存储结构，其数据元素的逻辑顺序依赖于链表中的指针链接次序来实现。链表由一系列节点组成，每个节点在运行时可以动态生成。每个节点包含两个部分：一是存储数据元素的数据域，二是存储下一个节点地址的指针域。与线性表的顺序结构相比，链表的操作更为复杂。由于无需按顺序存储，链表在插入操作时可以达到O(1)的时间复杂度，远快于顺序表；然而，查找特定节点或访问特定编号节点则需要O(n)的时间复杂度，而线性表和顺序表对应操作的时间复杂度分别为O(logn)和O(1)。

使用链表结构可以有效克服数组需要预先确定数据大小的缺点，链表能够充分利用计算机内存空间，实现灵活的动态内存管理。但链表也失去了数组随机读取的优点，且由于增加了节点的指针域，空间开销较大。链表最显著的优势在于，常规数组排列关联项目的方式可能与数据在内存或磁盘上的实际顺序不同，数据的存取往往需要在不同的排列顺序中进行转换。链表允许在表上任意位置插入和移除节点，但不支持随机存取。链表有多种类型，包括单向链表、双向链表以及循环链表。

单链表结构详解

二、单链表介绍

单向链表（单链表）是链表的一种基本形式，其特点是链接方向单向，访问链表必须从头部开始顺序读取。单链表是一种链式存取的数据结构，使用一组地址任意的存储单元来存放线性表中的数据元素。链表中的数据以节点形式表示，每个节点由元素（数据元素的映像）和指针（指示后继元素存储位置）组成。元素是存储数据的单元，指针则连接每个节点的地址数据。每个节点包含两个域：信息域（元素域）和链接域。链接域指向链表中的下一个节点，而最后一个节点的链接域指向空值。

链式存储结构的线性表采用一组任意存储单元存放数据元素。由于无需按顺序存储，链表在插入和删除数据元素时比顺序存储更快，但在查找节点时比顺序存储慢。使用链式存储可以克服顺序线性表需预先知道数据大小的缺点，链表结构能充分利用内存空间，实现灵活的动态管理。然而，链式存储失去了数组随机存取的特点，并因增加节点指针域而带来较大的空间开销。

三、单链表结构

  • 表元素域elem用于存放具体数据。
  • 链接域next用于存放下一个节点的位置（在Python中表示为标识）。
  • 变量p指向链表的头节点（首节点）位置，通过p可以找到表中的任意节点。

单链表常用操作图解

四、单链表常用操作图解

1、头插

2、尾插

3、指定位置插入

4、删除

Python单链表实现与测试

五、单链表的Python代码实现


# 创建节点
class Node(object):
  def __init__(self,item):
    self.element = item
    self.next = None
# 创建单链表类
class SingleLinkList(object):
  def __init__(self):
    self.header = None
    self.length = 0
  # 1、判断是否为空
  def is_empty(self):
    if self.header == None:
      return True
    else:
      return False
  # 2、头部插入
  def add(self,node):
    if self.is_empty():
      self.header = node
    else:
      node.next = self.header
      self.header = node
      # currentNode = self.header
    self.length += 1
  # 3、尾部插入
  def appent(self,node):
    currentNode = self.header
    if self.is_empty():
      self.add(node)
    else:
      while (currentNode.next != None):
        currentNode = currentNode.next
      currentNode.next = node
      self.length += 1
  # 4、指定位置插入
  def insert(self,node,index):
    currentNode = self.header
    if index>self.length+1 or index<=0:
      print("你要插入的位置不对，请重现选择位置")
    if index == 1:
      self.add(node)
    elif index == 2:
      node.next = self.header.next
      self.header.next = node
      self.length += 1
    else:
      for i in range(1,index-1):
        currentNode = currentNode.next
      node.next = currentNode.next
      currentNode.next = node
      self.length += 1
  # 5、遍历
  def travel(self):
    currentNode = self.header
    if self.length == 0:
      print("你要遍历的链表没有数据\n")
    else:
      print("你要遍历的链表里面的元素有:",end=" ")
      for i in range(self.length):
        print("%s "%currentNode.element,end=" ")
        currentNode = currentNode.next
      print("\n")
  # 6、排序不用交换节点的位置，只需要交换节点上的数据值
  def list_sort(self):
    for i in range(0,self.length-1):
      currentNode = self.header
      for j in range(0,self.length-i-1):
        if currentNode.element > currentNode.next.element:
          temp = currentNode.element
          currentNode.element = currentNode.next.element
          currentNode.next.element = temp
        currentNode = currentNode.next
  # 7、按索引删除
  def remove(self,index):
    if index<=0 or index>self.length:
      print("你输入的下标不对，请重新输入")
      return
    else:
      if index == 1:
        self.header = self.header.next
        currentNode = self.header
      elif index == 2:
        currentNode = self.header
        currentNode.next = currentNode.next.next
      else:
        currentNode = self.header
        for i in range(1,index-1):
          currentNode = currentNode.next
        currentNode.next = currentNode.next.next
    self.length -= 1
  # 8、查找是否包含,并返回下标
  def isContain(self,num):
    contain = 0
    currentNode = self.header
    for i in range(self.length):
      if currentNode.element == num:
        print("%d在链表中%d处\n"%(num,i))
        contain = 1
      currentNode = currentNode.next
    if contain == 0:
      print("%d不在链表中\n"%num)
  # 9、根据下标找节点
  def searchNodeByIndex(self,index):
    currentNode = self.header
    if index<=0 or index>self.length:
      print("你输入的下标不对，请重新输入\n")
      return 0
    else:
      for i in range(index-1):
        currentNode = currentNode.next
      return currentNode
  # 10、根据下标修改节点的值
  def modifyByIndex(self,index,num):
    currentNode = self.header
    if index<=0 or index>self.length:
      print("你输入的下标不对，请重新输入\n")
    else:
      for i in range(index-1):
        currentNode = currentNode.next
      currentNode.element = num
def main():
  # 创建一个节点对象
  node1 = Node(1)
  # 创建一个单链表对象
  single_link_list = SingleLinkList()
  print("验证空链表的遍历")
  single_link_list.travel()
  print("验证头插")
  single_link_list.add(node1)
  single_link_list.travel()
  print("验证尾插")
  node2 = Node(2)
  single_link_list.appent(node2)
  single_link_list.travel()
  print("验证按位置插入")
  node3 = Node(3)
  single_link_list.insert(node3,1)
  single_link_list.travel()
  print("继续验证头插")
  node4 = Node(5)
  single_link_list.add(node4)
  single_link_list.travel()
  print("继续验证按位置插入")
  node5 = Node(4)
  single_link_list.insert(node5,4)
  single_link_list.travel()
  print("验证删除")
  single_link_list.remove(3)
  single_link_list.travel()
  print("验证查找一个节点是否在链表中")
  single_link_list.isContain(8)
  print("验证按下标查找节点")
  node = single_link_list.searchNodeByIndex(2)
  print("第二个节点的值为：%s"%node.element)
  print("\n验证排序")
  single_link_list.list_sort()
  single_link_list.travel()
  print("验证修改")
  single_link_list.modifyByIndex(2,10)
  single_link_list.travel()
if __name__ == '__main__':
  main()

运行结果为：

验证空链表的遍历 你要遍历的链表没有数据

验证头插 你要遍历的链表里面的元素有: 1

验证尾插 你要遍历的链表里面的元素有: 1 2

验证按位置插入 你要遍历的链表里面的元素有: 3 1 2

继续验证头插 你要遍历的链表里面的元素有: 5 3 1 2

继续验证按位置插入 你要遍历的链表里面的元素有: 5 3 1 4 2

验证删除 你要遍历的链表里面的元素有: 5 3 4 2

验证查找一个节点是否在链表中 8不在链表中

验证按下标查找节点 第二个节点的值为：3

验证排序 你要遍历的链表里面的元素有: 2 3 4 5

验证修改 你要遍历的链表里面的元素有: 2 10 4 5

C语言单链表实现与测试

六、单链表的C语言代码实现


#include <stdio.h>
typedef struct N
{
  int element;
  struct N *next;
}Node;
// 1、创建节点
Node *createNode(int num)
{
  Node *node;
  node = (Node *)malloc(sizeof(Node));
  node->element = num;
  node->next = NULL;
  return node;
}
// 2、创建链表
Node *createSingleLinkList(Node *node)
{
  Node *head = node;
  return head;
}
// 3、获取链表长度
int getlength(Node *head)
{
  if (head == NULL)
  {
    return 0;
  }
  int count = 1;
  Node *current = head;
  while (current->next != NULL)
  {
    count++;
    current = current->next;
  }
  return count;
}
// 4、头部插入
Node * add(Node *head, Node *node)
{
  if(head == NULL)
  {
    head = node;
    return head;
  }
  else
  {
    node->next = head;
    head = node;
    return head;
  }
}
// 5、尾部插入
Node * append(Node *head,Node *node)
{
  Node *current = head;
  if (current->next == NULL)
  {
    add(head, node);
  }
  else
  {
    int len = getlength(head);
    for (int i = 0; i<len-1; i++)
    {
      current = current->next;
    }
    current->next = node;
  }
  return head;
}
// 6、按下标插入节点
Node * insert(Node *head,Node *node,int index)
{
  int len = getlength(head);
  if (index<=0||index>len+1)
  {
    printf("你要插入的位置不对，请重现选择位置");
  }
  Node *current = head;
  if (index == 1)
  {
    head = add(head, node);
  }
  else if (index == 2)
  {
    node->next = head->next;
    head->next = node;
  }
  else
  {
    for (int i = 1; i<index-1; i++)
    {
      current = current->next;
    }
    node->next = current->next;
    current->next = node;
  }
  return head;
}
// 7、遍历
void travel(Node *head)
{
  int len = getlength(head);
  printf("len = %d\n",len);
  Node *current = head;
  if (len == 0)
  {
    printf("你要遍历的链表没有数据\n");
  }
  else
  {
    printf("你要遍历的链表里面的元素有: ");
    for (int i = 0; i<len; i++)
    {
      printf("%d ",current->element);
      current = current->next;
    }
    printf("\n");
  }
}
// 8、根据索引删除
Node * delect(Node *head,int index)
{
  int len = getlength(head);
  if (index<=0||index>len)
  {
    printf("你输入的下标不对，请重新输入");
    return head;
  }
  else
  {
    if (index == 1)
    {
      head = head->next;
    }
    else if (index == 2)
    {
      head->next = head->next->next;
    }
    else
    {
      Node *current = head;
      for (int i = 1; i<index-1; i++)
      {
        current = current->next;
      }
      current->next = current->next->next;
    }
  }
  return head;
}
// 9、查找是否包含，并返回下标
void isContain(Node *head,int num)
{
  int contain = 0;
  Node *current = head;
  int len = getlength(head);
  for (int i = 0; i<len; i++)
  {
    if (current->element == num)
    {
      printf("%d在链表中的%d处\n",num,i+1);
      contain = 1;
    }
    current = current->next;
  }
  if (contain == 0)
  {
     printf("%d不在链表中\n",num);
  }
}
// 10、根据下标找节点
Node *searchByIndex(Node *head , int index)
{
  int len = getlength(head);
  Node *current = head;
  if (index<=0||index>len)
  {
    printf("你输入的下标不对，请重新输入");
    return head;
  }
  else
  {
    for (int i = 0; i<index-1; i++)
    {
      current = current->next;
    }
    return current;
  }
}
// 11、根据下标修改节点的值
void modifyByIndex(Node *head,int index,int num)
{
  int len = getlength(head);
  Node *current = head;
  if (index<=0||index>len)
  {
    printf("你输入的下标不对，请重新输入");
  }
  else
  {
    for (int i = 0; i<index-1; i++)
    {
      current = current->next;
    }
    current->element = num;
  }
}
int main(int argc, const char * argv[])
{
  printf("==========1、创建节点==========\n");
  Node * node1 = createNode(1);
  printf("==========2、创建单链表==========\n");
  Node * head = createSingleLinkList(node1);
  travel(head);
  printf("==========3、验证头插==========\n");
  Node *node2 = createNode(0);
  head = add(head, node2);
  travel(head);
  Node *node3 = createNode(2);
  head = add(head, node3);
  travel(head);
  printf("==========4、验证尾插==========\n");
  Node *node4 = createNode(4);
  head = append(head,node4);
  travel(head);
  Node *node5 = createNode(5);
  head = append(head,node5);
  travel(head);
  printf("==========5、验证按下标插入==========\n");
  Node *node6 = createNode(6);
  head = insert(head, node6, 1);
  travel(head);
  printf("==========6、验证按下标删除==========\n");
  head = delect(head, 2);
  travel(head);
  printf("==========7、验证是否包含==========\n");
  isContain(head, 8);
  printf("==========8、验证根据下标找节点==========\n");
  Node *n = searchByIndex(head, 1);
  printf("第一个节点是%d\n",n->element);
  printf("==========9、验证根据下标修改==========\n");
  modifyByIndex
(head, 3, 9);
    travel(head);
    return 0;
}

运行结果为：

==========1、创建节点========== ==========2、创建单链表========== len = 1 你要遍历的链表里面的元素有: 1 ==========3、验证头插========== len = 2 你要遍历的链表里面的元素有: 0 1 len = 3 你要遍历的链表里面的元素有: 2 0 1 ==========4、验证尾插========== len = 4 你要遍历的链表里面的元素有: 2 0 1 4 len = 5 你要遍历的链表里面的元素有: 2 0 1 4 5 ==========5、验证按下标插入========== len = 6 你要遍历的链表里面的元素有: 6 2 0 1 4 5 ==========6、验证按下标删除========== len = 5 你要遍历的链表里面的元素有: 6 0 1 4 5 ==========7、验证是否包含========== 8不在链表中 ==========8、验证根据下标找节点========== 第一个节点是6 ==========9、验证根据下标修改========== len = 5 你要遍历的链表里面的元素有: 6 0 9 4 5

总结

总结

以上所述是小编给大家介绍的python算法与数据结构之单链表的实现代码 ,希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对本站网站的支持！ 如果你觉得本文对你有帮助，欢迎转载，烦请注明出处，谢谢！

相关文章

相关标签: Python 单链表 C语言

本站声明

本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。

作者最新文章

全部内容

Python 相关产品和应用

全部下载
Python Selenium
Selenium

Selenium

4.51.0 · Windows

用于浏览器自动化和 Web 测试的 Python 工具。
Python 机器学习
scikit-learn

scikit-learn

1.9.1 · Windows

常用 Python 机器学习算法与模型评估工具库。
Python 代码质量
Black

Black

26.10.1 · Windows

强调一致性的 Python 自动代码格式化工具。
Python 代码质量
Ruff

Ruff

0.17.1 · macOS

由 Rust 编写的高速 Python 代码检查和格式化工具。
Python pytest
pytest

pytest

9.1.1 · Windows

简洁而强大的 Python 自动化测试框架。
Python FastAPI API
FastAPI

FastAPI

0.146.0 · Windows

高性能 Python API 框架，支持类型提示和自动接口文档。
Python Flask Web开发
Flask

Flask

3.1.3 · Windows

轻量灵活的 Python Web 应用框架。
Python Django Web开发
Django

Django

6.1.2 · Windows

成熟的 Python Web 框架，适合构建内容站点和业务系统。
Python Spyder
Spyder

Spyder

6.1.7 · Windows

面向科学计算与数据分析的 Python 集成开发环境。
Python SciPy
SciPy

SciPy

1.18.1 · Windows

面向科学、工程和技术计算的 Python 算法库。
Python Pandas 数据分析
pandas

pandas

3.0.6 · Windows

Python 数据分析库，提供 DataFrame 与丰富的数据处理能力。
Python NumPy
NumPy

NumPy

2.5.4 · Windows

Python 科学计算基础库，提供高性能多维数组与数值运算。

文章分类

专题列表

ipython.cn 学习网
人工智能 Java AI行业服务