单链表基础操作

abstract

单链表是一种简单的动态数据结构，它由一系列结点组成，每个结点包含一个数据域和一个指向下一个结点的指针。

带头结点的单链表的头结点不存储数据，仅用于指向第一个真正存储数据的结点。

以下是C语言中单链表的一些常用操作：(默认带有头结点)

定义结点结构

另见:链表@单链表相关概念和代码表述-CSDN博客

typedef struct Node
{int data;struct Node *next;
} Node;
typedef Node *LinkList;
//为了提高可读性,利用typedef和Node类型定义一个LinkList类型,效果:ListList L;等价于Node *L;// typedef *Node LinkList;//这种定义是错误的

初始化链表

Node* initList() {Node* head = (Node*)malloc(sizeof(Node));head->next = NULL;return head;
}

遍历链表

遍历链表并打印每个结点的数据：

void printList(Node* head) {Node* p = head->next; // 从首元开始while (p != NULL) {printf("%d -> ", p->data);p = p->next;}printf("NULL\n");
}

求表长

int Length(Node* L){int len=0;//记录链表长度Node *p=L;//p初始化为头指针while(p->next!=NULL){p=p->next;//正式更新p,最后一趟(p->next是尾元,p是倒数第二个结点)p会被此语句更新为尾元len++;//刷新此时p所指结点的位序}//退出循环时,p是尾结点,其后继为NULLreturn len;
}

或者

int Length(Node* L){int len=0;//记录链表长度Node *p=L->next;//p初始化为首元(可能为空)while(p){//最有一次进入循环是p为尾元的情况len++;//刷新此时p所指结点的位序p=p->next;}//离开是p==NULLreturn len;
}

查找结点

分两两种类型:按序号查找和安值查找

根据序号查找结点

Node *getElem(Node*L,int i){Node *p=L;//辅助指针初始化为头指针(头结点指针);int j=0;//指示p指向第几个结点(头结点是第0个结点),从而判断p是否为目标结点可以通用判断j==i来实现while(p!=NULL && j<i){//这种判断条件允许参数i=0;这会返回头结点(而非首元)p=p->next; //p->next从首元开始j++; }//最后一次进入循环是p为尾元或者j=i-1;离开循环时p是尾元的后继NULL,即p==NULL或j==i;如果是NULL说明找不到想要的结点(越界)return p;
}
//这里用不着p指向尾元,所以while条件中用了p!=NULL

根据值查找结点

Node* LocateElem(Node* head, int e) {Node* p = head->next; // 从首元开始while(p!=NULL && p->data!=e){p=p->next;}return p;}

Node* LocateElem(Node* head, int e) {Node* p = head->next; // 从首元开始//判断条件分开写也可以while (p != NULL) {if (p->data == e) return p;p = p->next;}return NULL;
}

插入结点

在带头结点的单链表中，我们可以在任意位置插入一个新结点。

首尾位置插入

// 头插法
void insertAtHead(Node* head, int data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = head->next;head->next = newNode;
}// 尾插法
void insertAtTail(Node* head, int data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;//通过遍历找到最后一个结点,链接新结点Node* p = head;//辅助指针遍历while (p->next != NULL) {p = p->next;}//退出时说明p指向尾结点(非空)//链接尾部新结点p->next = newNode;
}

一般位置插入(通用插入)

找到要插入位置的前驱结点,然后执行插入

#define bool int
#define true 1
#define false 0bool ListInsert(Node*L,int i,ElemType e){Node*p=L;int j=0;//指示当前p所指的结点位序//找到要插入的位置结点的前驱(第i-1)个结点while(p!=NULL && j<i-1){p=p->next;j++;}//离开循环时,若干长度足够,那么是由于j==i-1,否则p==NULL发生越界//检查j的合法性(越界)if(p==NULL){return false;}//新建结点Node *s=(Node*)malloc(sizeof(Node));s->data=e;//插入结点s->next=p->next;p->next=s;return true;
}

找到尾元素|尾指针相关操作

读者可能会考虑以下写法来遍历整个链表

Node* p = head->next;//首元
while (p) {p = p->next;
}//离开循环时p已经是NULL而不是尾结点了,这往往不是我们想要的,尤其是要后续访问或删除尾结点的操作将无法直接利用p进行

因此该写法不利于后续灵活处理,通常把循环语句中的判断语句写成(p->next!=NULL)

或者配合break语句也可以找出最后一个非空结点的指针p

Node* p = head->next;//首元
while (p) {//也可以是while(1)if(p->next==NULL){break;}p = p->next;//可以保证这个赋值内容是非空的
}//退出时说明p指向尾结点(非空)

这种写法虽然也可以,但是简洁和紧凑程度不如下面的做法

 while (p->next != NULL) {p = p->next;
}

删除结点

删除指定位置的结点，可以是根据位置删除或者根据值删除：

若根据位序删除(位序范围$1\sim n$,其中$n$为链表长度)

根据值删除结点

// 根据值删除结点
void deleteByValue(Node* head, int value) {Node* p = head;while (p->next != NULL && p->next->data != value) {p = p->next;}if (p->next != NULL) {Node* toDelete = p->next;p->next = toDelete->next;free(toDelete);}
}

找到目标结点的前驱,然后执行删除

#define bool int
#define true 1
#define false 0
bool ListDelete(Node *L, int i, ElemType *e)
{Node *p = L;int j = 0;// 找到第i个结点的前驱(第i-1个结点)while (p && j < i - 1){p = p->next;j++;}// 如果此时p是尾结点(后继结点为空,不用删除)或者空指针(没有后继),两种情况都说明i不合法if (p == NULL || p->next == NULL){return false;}Node *q = p->next;*e = q->data; // 返回被删除的值p->next = q->next;//更新后继(断开q结点)free(q);//释放q的内存空间return true;
}