单链表基础操作详解与C语言实现
单链表是线性表的链式存储结构，通过指针将分散的节点串联起来。本文以带头结点的单链表为例，介绍其核心操作。
节点结构与类型定义
每个节点包含数据域和指针域，指针域存储后继节点的地址。
typedef int DataType;
typedef struct Node {
DataType data;
struct Node* next;
} Node, *List;初始化链表
创建头结点并将其next置空，头结点不存储实际数据，仅作为操作入口。
bool createList(List& head)
{
head = (Node*)malloc(sizeof(Node));
if (head == NULL) return false;
head->next = NULL;
return true;
}获取链表长度
从首元节点开始遍历，累计有效节点数量。
int getLength(List head)
{
int count = 0;
Node* cur = head->next;
while (cur != NULL)
{
count++;
cur = cur->next;
}
return count;
}按位序查找节点
返回第i个节点的指针，若位序非法则返回NULL。
Node* findByIndex(List head, int i)
{
if (i < 1) return NULL;
Node* cur = head->next;
int idx = 1;
while (cur != NULL && idx < i)
{
cur = cur->next;
idx++;
}
return cur;
}按值查找节点
遍历比对数据域，首个匹配项的指针即为所求。
Node* findByValue(List head, DataType val)
{
Node* cur = head->next;
while (cur != NULL && cur->data != val)
{
cur = cur->next;
}
return cur;
}插入节点
在第i个位置插入新元素，需先定位到第i-1个节点，再修改指针关系。注意：必须先链接后继，再链接前驱，否则会导致断链。
bool insertNode(List head, int i, DataType val)
{
Node* pre = head;
int idx = 0;
while (pre != NULL && idx < i - 1)
{
pre = pre->next;
idx++;
}
if (pre == NULL) return false;
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = val;
newNode->next = pre->next;
pre->next = newNode;
return true;
}删除节点
删除第i个节点并通过引用参数返回其数据值，释放内存前务必保存前驱与后继的链接关系。
bool removeNode(List head, int i, DataType& val)
{
Node* pre = head;
int idx = 0;
while (pre->next != NULL && idx < i - 1)
{
pre = pre->next;
idx++;
}
if (pre->next == NULL) return false;
Node* temp = pre->next;
val = temp->data;
pre->next = temp->next;
free(temp);
return true;
}遍历输出
void displayList(List head)
{
Node* cur = head->next;
while (cur != NULL)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}完整测试程序
#include <stdio.h>
#include <stdlib.h>
typedef int DataType;
typedef struct Node {
DataType data;
struct Node* next;
} Node, *List;
bool createList(List& head)
{
head = (Node*)malloc(sizeof(Node));
if (head == NULL) return false;
head->next = NULL;
return true;
}
int getLength(List head)
{
int count = 0;
Node* cur = head->next;
while (cur != NULL)
{
count++;
cur = cur->next;
}
return count;
}
Node* findByIndex(List head, int i)
{
if (i < 1) return NULL;
Node* cur = head->next;
int idx = 1;
while (cur != NULL && idx < i)
{
cur = cur->next;
idx++;
}
return cur;
}
Node* findByValue(List head, DataType val)
{
Node* cur = head->next;
while (cur != NULL && cur->data != val)
{
cur = cur->next;
}
return cur;
}
bool insertNode(List head, int i, DataType val)
{
Node* pre = head;
int idx = 0;
while (pre != NULL && idx < i - 1)
{
pre = pre->next;
idx++;
}
if (pre == NULL) return false;
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = val;
newNode->next = pre->next;
pre->next = newNode;
return true;
}
bool removeNode(List head, int i, DataType& val)
{
Node* pre = head;
int idx = 0;
while (pre->next != NULL && idx < i - 1)
{
pre = pre->next;
idx++;
}
if (pre->next == NULL) return false;
Node* temp = pre->next;
val = temp->data;
pre->next = temp->next;
free(temp);
return true;
}
void displayList(List head)
{
Node* cur = head->next;
while (cur != NULL)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
int main()
{
List myList;
DataType removed;
if (!createList(myList))
{
printf("内存分配失败\n");
return 0;
}
printf("初始长度: %d\n", getLength(myList));
insertNode(myList, 1, 56);
insertNode(myList, 2, 8);
insertNode(myList, 3, 3);
insertNode(myList, 4, 2);
printf("当前链表: ");
displayList(myList);
Node* found = findByValue(myList, 8);
if (found) printf("查找到值 8\n");
else printf("未找到值 8\n");
Node* indexed = findByIndex(myList, 2);
if (indexed) printf("第2位元素为: %d\n", indexed->data);
if (removeNode(myList, 2, removed))
printf("删除成功, 值为: %d\n", removed);
printf("最终链表: ");
displayList(myList);
return 0;
}