本文总结了顺序表，单链表，双向链表的基本操作。

文章目录

一、线性表的定义与特点

线性表指的是具有相同数据类型的n(n>=0)个数的有限序列。
假设a1是第一个数据元素，称为表头元素；an是最后一个数据元素，称为表尾元素；ai（1<i<n）是第i个数据元素：
则a1有且只有一个后继；an有且只有一个前驱；ai有且只有一个前驱和一个后继。

线性表是一种逻辑结构，定义了一组元素之间“一个接一个”的前后关系。

根据这个结构在计算机内存中的存储方式：我们分为顺序存储结构和链式存储结构。

二、线性表的顺序表示与实现（顺序表）

用一组连续的内存单元依次存储线性表的各个元素，也就是用数组的方式存储，逻辑上相邻的元素，实际的物理存储空间也是连续的

静态顺序表

存储结构
#define MAXSIZE = 100
typedef int ElemType;
//给int类型起别名，方便以后修改int成float/struct等类型
typedef struct{
    ElemType data [MAXSIZE];//默认初始化
    int length;//当前顺序表的长度
}SeqList;
初始化
void initList(SeqList *L){
    L->length=0;//当前顺序表是一个空表
}

动态顺序表

存储结构
typedef struct{
    ElemType *data;
    int length;
}SeqList;
初始化
SeqList *initList(){
    SeqList *L=(SeqList*)malloc(sizeof(SeqList));
    L->data=(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
    L->length=0;
    return L;
}

功能实现

1.在尾部添加元素
int appendElem(SeqList *L,ElemType e){
    if(L->length>=MAXSIZE){
        printf("顺序表已满\n");
        return 0;
    }
    L->data[L->length]=e;
    L->length++;
    return 1;
}
2.遍历
void listElem(SeqList *L){
    for(int i=0;i<L->length;i++){
        printf("%d",L->data[i])；
    }
    printf("\n");
}
3.插入元素

在pos位置插入数据（即在数组下标为pos-1的位置插入数据）

所以需要把下标为pos-1直到length-1的元素，均向后移一位

通过length自增，插入元素

int insertElem(SeqList *L,int pos,ElemType e){
    if(L->length>=MAXSIZE){
        printf("表已经满了\n");
        return 0;
    }
    if(pos<1||pos>L->length){
        printf("插入位置错误\n");
        return 0;
    }
    if(pos<=L->length){
        for(int i=L->length-1;i>=pos-1;i--){
            L->data[i+1]=L->data[i]；
        }
        L->data[pos-1]=e;//要插入数据的位置pos是从1开始数的
        L->length++;
    }
    return 1;
}

顺序表插入数据的时间复杂度：最好O(1);最坏O(n)

4.删除元素

删除pos位置的数据(即删除下标为pos-1的元素），用e保存删除的元素

同理，把下标为pos到length-1的元素，均向前移一位

通过length自减，删除元素

int deleteElem(SeqList *L,int pos,ElemType *e){
    if(L->length==0){
        printf("空表\n");
        return 0;
    }
    if(pos<1||pos>L->length){
        printf("删除数据位置有误\n");
        return 0;
    }
    *e=L->data[pos-1];
    if(pos<L->length){
        for(int i=pos;i<L->length;i++){
            L->data[i-1]=L->data[i];
        }
    }
    L->length--;
    return 1;
}
5.查找

想实现的功能：传入一个元素，返回这个元素第一次出现在该顺序表的位置

int findElem(SeqList *L,ElemType e){
    if(L->length==0){
        printf("空列表\n");
        return 0;
    }
    for(int i=0;i<L->length;i++){
        if(L->data[i]==e){
            return i+1;
        }
    }
    return 0;
}

检验功能实现

静态顺序表
int main(){
    SeqList list;
    initList(&list);
    appendElem(&list,88);
    appendElem(&list,45);
    appendElem(&list,43);
    appendElem(&list,17);
    listElem(&list);
    insertElem(&list,2,18);
    listElem(&list);
    ElemType delData;
    deleteElem(&list,2,&delData);
    printf("被删除的数据为：%d\n",delData);
    listElem(&list);
    printf("%d\n",findElem(&list,40));
    return 0;
}
动态顺序表
int main(){
    SeqList *list=initList();
    initList(list);
    appendElem(list,88);
    appendElem(list,45);
    appendElem(list,43);
    appendElem(list,17);
    listElem(list);
    insertElem(list,2,18);
    listElem(list);
    ElemType delData;
    deleteElem(list,2,&delData);
    printf("被删除的数据为：%d\n",delData);
    listElem(list);
    printf("%d\n",findElem(list,40));
    return 0;
}

三、线性表的链式表示与实现（链表）

用一组任意的存储单元存储线性表的数据元素（这组存储单元可以连续，也可以不连续），用指针将分散的内存块链接起来

  • 节点

为表示每个数据元素 a i a_i ai​与其直接后继 a i + 1 a_{i+1} ai+1​之间的逻辑关系，对数据元素 a i a_i ai​来说，除了其本身的信息外，还需存储一个指示其直接后继的信息（直接后继的存储位置）。这两部分信息组成数据元素 a i a_i ai​的存储映像，称为节点

  • 数据域与指针域

节点包括两个域

数据域：存储数据元素信息

指针域：存储直接后继存储位置（存储的信息称为指针或链）

  • 链表

n个节点[ a i a_i ai​(1≤i≤n)的存储映像]链接成一个链表，即为线性表（ a 1 a_1 a1​, a 2 a_2 a2​,…… a n a_n an​)

单链表

每个节点包含数据和指向下一个节点的指针

1.存储结构

typedef int ElemType;
typedef struct node{
    ElemType data;
    struct node *next;//next里面存储下一个节点的地址
}Node;
//用一个结构体表示一个节点

2.初始化

定义一个头节点，头节点是真正存储数据的节点前的一个节点

1.为指向头节点的指针分配内存

2.将头节点数据域赋值为0，指针域赋值为空

3.返回该头节点

image-20251030101410676

Node* initList(){
    Node *head=(Node*)malloc(sizeof(Node));
    //头节点：第一个真正存储数据的节点之前的一个节点
    
    head->data=0;
    head->next=NULL;
    return head;
}

3.头插法

每一次插入数据都是在头节点后面插入数据

参数是指向头节点的指针，和要插入的数据

1.创建一个新的节点（开辟一个大小为sizeof(Node)的内存，返回该内存的起始地址，该地址用指针p接收）

2.该新节点的数据域赋值为要插入的数据

3.由于单链表的特性是能找到后面的元素，所以先把头节点的next赋值给新节点的next

4.头节点的next指向新节点

image-20251030101337364

int insertHead(Node* L,ElemType e){
    Node *p=(Node*)malloc(sizeof(Node));
    p->data=e;
    p->next=L->next;//注意顺序，弄明白为什么
    L->next=p;
}

4.遍历

让一个指针从链表的第一个节点开始行走，直到指向空

1.让该指针指向第一个节点（即头节点的next）

2.只要指针不指向空，就不断指向next

void ListNode(Node*L){
    Node*p=L->next;
    while(p!=NULL){
        printf("%d\n",p->data);
        p=p->next;
    }
    printf("\n");
}

问题：头插法的插入顺序和输出后的排列顺序正好是反的

5.尾插法

  • 先获取尾节点（遍历），只有尾节点的next是指向空值的
Node*get_tall(Node*L){
    Node*p=L;
    while(p->next!=NULL){
        p=p->next;
    }
    return p;
}
  • 再在尾部插入元素

参数是尾节点，和要插入的元素

1.创建一个新节点（尾节点的下一个节点）

2.新节点的数据域赋值为要插入的元素

3.让原来尾节点的next指向新节点

4.将新节点的next赋为空

5.返回新节点（即新的尾节点）

Node*insertTail(Node*tail,ElemType e){//参数是尾节点和要插入的数据
    Node*p=(Node*)malloc(sizeof(Node));//创建一个新的节点（尾节点的下一个节点）
    p->data=e;
    tail->next=p;
    p->next=NULL;
    return p;//返回最新的尾节点
}

6.在指定位置插入数据

image-20251030105052496

若想在70和80之间插入new元素，需要先找到70，让new指向80，再让70指向new

参数是头节点，插入的位置，插入的元素

1.定义一个指针p，从头节点开始移动，直至插入位置的前一个位置

2.创建一个新节点（即插入数据的节点）

3.新节点的数据域赋值为插入数据

4.将p的next赋值给新节点的next

5.p的next指向新节点

int insertNode(Node*L,int pos,ElemTpye e){
    Node*p=L;//用来保存插入位置的前驱节点
    int i=0;
    while(i<pos-1){//遍历链表找到插入位置的前驱节点
        p=p->next;
        i++;
        if(p==NULL){
            return 0;
        }
    }
    Node*q=(Node*)malloc(sizeof(Node));//要插入的新节点
    q->data=e;
    q->next=p->next;
    p->next=q;
    return 1;
}

7.删除节点

原理：假设要删除节点q，我们需要让q前面节点的next指向q后面的节点，再释放q

参数是头节点和要删除节点的位置

1.找到要删除的前置节点p

2.用指针q记录要删除的节点

3.通过改变p的后继节点来实现删除：将去q的next赋给p的next

4.释放删除节点的空间

int deleteNode(Node*L,int pos){
    Node*p=L;
    int i=0;
    while(i<pos-1){
        p=p->next;
        i++;
        if(p==NULL){
            return 0;
        }
    }
    if(p->next==NULL){
        printf("要删除的位置错误\n");
        return 0;
    }
    Node*q=p->next;
    p->next=q->next;
    free(q);
    return 1;
}

8.删除链表中间节点

重点在于如何运用双指针法找到中间节点

原理：快慢指针，每次快指针比慢指针多走一步（快指针的总步数是慢指针总步数的的二倍：慢指针走一步，快指针走两步；慢指针走两步，快指针走四步），当快指针走到头，慢指针所指向的位置就是中点。

模拟一下：

慢	快(起始均在1的位置)
2	3
3	5
4	7
5	9

但由于单链表无法找到前一个元素，所以我们必须让慢指针最后指向要删除的前驱节点，所以慢指针从0开始移动（即头节点）

int delMiddleNode(Node*head){
    Node*fast=head->next;
    Node*slow=head;
    while(fast!=NULL&&faast->next!=NULL){
        fast=fast->next->next;
        slow=slow->next;
    }
    Node*q=slow->next;
    slow->next=q->next;
    free(q);
    return 1;
}

扩展：可以找到中点，就可以找到三分之一节点，就可以找到n分之一节点，就是要让快指针多走2步，n-1步。

9.获取链表长度

原理：遍历+长度计数

int listLength(Node*L){
    Node*p=L;
    int len=0;
    while(p！=NULL){
        p=p->next;
        len++;
    }
    return len;//包括头节点的长度
}

10.释放链表

原理：如果用指针遍历指向链表的每一个元素，去释放他们的内存，会出现释放完了当前节点，但找不到下一个节点，所以需要用两个指针p和q，一个指向要释放内存的节点，一个指向它的后继节点，循环释放，最后别忘了把头节点的next赋为空

1.p指向头节点后的第一个节点

2.判断指针p是否指向空节点

3.若不为空，用指针q记录指针p的后继节点

4.释放指针p所指向的节点

5.指针p和q指向同一个节点，循环上面的操作

void freeList(Node*L){
    Node*p=L->next;
    Node*q;
    while(p!=NULL){
        q=p->next;
        free(p);
        p=q;
    }
    L->next=NULL;
}

11.反转链表

原理：把原链表的每个箭头反过来，和前面一样为保证能找到下一个节点，我们需要一个指针来保存它

1.定义三个指针，first，second，third分别指向头节点，头节点的下一个，头节点的下一个的下一个

2.second的next指向first

3.这三个指针均向后移一位，直到second为空

Node*reverseList(Node* head){
    Node*first=NULL;
    Node*second=head->next;
    Node*third;
    while(second!=NULL){
        third=second->next;
        second->next=first;
        first=second;
        second=third;
    }
    Node*hd=initList();
    hd->next=first;
    return hd;
}

单链表的应用

应用1：

image-20251030115312222

查找倒数第3个节点：双指针（快慢指针）

快指针先走3步，再快慢指针一起走

int findNode(Node*L,int k){
    Node*fast=L->next;
    Node*slow=L->next;
    for(int i=0;i<k;i++){
        fast=fast->next;
    }
    while(fast!=NULL){
        fast=fast->next;
        slow=slow->next;
    }
    printf("倒数第%d个节点值为：%d\n",k,slow->data);
    return 1;
}

应用2：

image-20251030141305315

双指针法

  1. 分别求出链表的长度m，n

  2. fast指针指向较长的链表，先走|m-n|步

  3. 同步移动指针，判断他们是否指向同一个点

Node*findIntersectionNode(Node*headA,Node*headB){
    if(headA==NULL||headB==NULL){
        return NULL;
    }
    Node*p=headA;
    int lenA=0;
    int lenB=0;
    while(p!=NULL){
        p=p->next;
        lenA++;
    }
    p=headB;
    while(p!=NULL){
        p=p->next;
        lenB++;
    }
    Node*m;//快指针
    Node*n;//慢指针
    int step;//两个单词数量的差值
    if(lenA>lenB){
        step=lenB-lenA;
        m=headB;
        n=headA;
    }
    else{
        step=lenB-lenA;
        m=headB;
        n=headA;
    }
    for(int i=0;i<step;i++){
        m=m->next;
        n=n->next;
    }
    return m;
}

应用3：

image-20251030141334334

拿空间换时间

void removeNode(Node*L,int n){
    Node*p=L;
    int index;
    int*q=(int*)malloc(sizeof(int)*(n+1));
    for(int i=0;i<n+1;i++){
        *(q+i)=0;
    }
    while(p->next!=NULL){
        index=abs(p->next->data);
        if(*(q+index)==0){
            *(q+index)=1;
            p=p->next;
        }
        else{
            Node*temp=p->next;
            p->next=temp->next;
            free(temp);
        }
    }
    free(q);
}

双向链表

每个节点包含数据、指向前驱节点和指向后继节点的指针

1.存储结构

image-20251110181246479

双向链表的节点中有两个指针域，一个指向直接后继，另一个指向直接前驱

typedef int type;
typedef struct node{
    type data;
    struct node*prev,*next;
}

2.初始化

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

3.头插法

image-20251114131203856

步骤：

  1. 创建新节点p
  2. 将p的next指向当前链表的第一个节点（即L->next）
  3. 将p的prev指向头节点L
  4. 如果当前链表第一个节点存在（即非空），则让第一个节点的prev指向p
  5. 将头节点的next指向p
void insertHead(Node*L,type e){
    Node*p=(Node*)malloc(sizeof(Node));
    
    p->data=e;
    p->next=L->next;
    p->prev=L;
    if(L->next!=NULL){
        L->next->prev=p;
    }
    L->next=p;
}

注意事项：

  1. 指针操作顺序：先设置新节点的指针，再修改原有节点的指针

​ 确保修改指针时不会丢失对现有节点的引用

  1. 不要访问空指针

4.尾插法

步骤：

  1. 获取尾部节点p
  2. 创建新节点q
  3. 将q的prev指向尾节点的p
  4. 将q的next指向空
  5. 将尾节点p的next指向q
void insertTail(Node* L, type e) {
	Node* p = L;
	while (p->next != NULL) {
		p = p->next;
	}
	Node* q = (Node*)malloc(sizeof(Node));
	q->data = e;
	q->prev = p;
	q->next = NULL;
	p->next = q;
}

注意事项：

  1. 依旧是先设置新节点的指针，再修改原有节点的指针

5.在指定位置插入数据

和头插法原理相同

单链表时，我们要找前驱节点，双向链表我们找前驱或后继都可以，为了方便记忆（和单链表相似）这里我们找前驱节点

步骤：

  1. 获取指定插入位置的前驱节点p
  2. 创建新节点q
  3. 将q的next指向前驱节点p的next
  4. 将q的prev指向前驱节点p
  5. 让后继节点（p->next）的prev指向q
  6. 让前驱节点的next指向q
void insertNode(Node* L,int pos, type e) {
	Node* p = L;
	for (int i = 0; i < pos-1; i++) {
		p = p->next;
	}
	Node* q = (Node*)malloc(sizeof(Node));
	q->data = e;
    q->next = p->next;
	q->prev = p;
	p->next->prev = q;
	p->next = q;
}

6.删除节点

和指定位置插入数据一样，我们找删除位置的前驱/后继都可以，这里还是找前驱节点

思路：

  1. 找到要删除节点的前置节点p
  2. 用指针q记录要删除的节点
  3. 通过改变p的后继节点及要删除节点的下一个节点的前驱实现删除
  4. 释放删除节点的空间
void deleteNode(Node* L, int pos) {
	Node* p = L;
	for (int i = 0; i < pos - 1; i++) {
		p = p->next;
	}
	Node* q = p->next;
	p->next = q->next;
	q->next->prev = p;
	free(q);
}

四、总结

  • 顺序表适合查询多、修改少的场景。
  • 链表适合频繁插入删除、动态性强的场景。
  • 双向链表在需要双向遍历时更具优势。
    节点p
  1. 创建新节点q
  2. 将q的next指向前驱节点p的next
  3. 将q的prev指向前驱节点p
  4. 让后继节点（p->next）的prev指向q
  5. 让前驱节点的next指向q
void insertNode(Node* L,int pos, type e) {
	Node* p = L;
	for (int i = 0; i < pos-1; i++) {
		p = p->next;
	}
	Node* q = (Node*)malloc(sizeof(Node));
	q->data = e;
    q->next = p->next;
	q->prev = p;
	p->next->prev = q;
	p->next = q;
}

6.删除节点

和指定位置插入数据一样，我们找删除位置的前驱/后继都可以，这里还是找前驱节点

思路：

  1. 找到要删除节点的前置节点p
  2. 用指针q记录要删除的节点
  3. 通过改变p的后继节点及要删除节点的下一个节点的前驱实现删除
  4. 释放删除节点的空间
void deleteNode(Node* L, int pos) {
	Node* p = L;
	for (int i = 0; i < pos - 1; i++) {
		p = p->next;
	}
	Node* q = p->next;
	p->next = q->next;
	q->next->prev = p;
	free(q);
}

四、总结

  • 顺序表适合查询多、修改少的场景。
  • 链表适合频繁插入删除、动态性强的场景。
  • 双向链表在需要双向遍历时更具优势。
# 数据结构 # 链表 # 算法 # c语言 # leetcode
Logo
2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

cover

出海企业如何依托拓氪科技AIGEO布局AI采购流量入口？

avatar 2048 AI社区
cover

2026年AI写作辅助平台推荐：9款实用AI工具终极合辑

avatar 2048 AI社区
cover

【无标题】AI引用逻辑变了：从匹配关键词到理解语义，行业内容策略需要重新设计

avatar 2048 AI社区