笔记·指针单双链表

userId_undefined
AAA_Cheer_EndBet
时间刺客空间掌握者时空双修者出道萌新快乐小狗秩序白银

2026-06-29 18:40:39

发布于：云南

0阅读
0回复
0点赞

指针单双链表

一、什么是指针链表

链表是一种线性数据结构，由一系列节点组成。每个节点包含数据域和指针域，指针域指向下一个节点（或上一个节点）。链表的优点是插入删除操作快，不需要移动元素，缺点是查找需要遍历，不能随机访问。

指针链表的特点：

  • 节点动态分配内存
  • 通过指针连接节点
  • 插入删除时间复杂度O(1)
  • 查找时间复杂度O(n)

二、单链表

单链表：每个节点只包含指向下一个节点的指针，只能从前往后遍历。

节点结构

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

基本操作

1. 创建链表

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* next;
};
Node* head,* tail;
int n;
int main() {
    scanf("%d",&n);
    head=NULL;
    tail=NULL;
    for(int i=1;i<=n;i++) {
        int x;
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->next=NULL;
        if(head==NULL) {
            head=p;
            tail=p;
        } else {
            tail->next=p;
            tail=p;
        }
    }
    for(Node* p=head;p!=NULL;p=p->next) {
        printf("%d ",p->data);
    }
    printf("\n");
    return 0;
}

2. 在头部插入

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* next;
};
Node* head;
int main() {
    head=NULL;
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->next=head;
        head=p;
    }
    for(Node* p=head;p!=NULL;p=p->next) {
        printf("%d ",p->data);
    }
    printf("\n");
    return 0;
}

3. 在指定位置插入

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* next;
};
Node* head;
int main() {
    head=NULL;
    int n,pos,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->next=head;
        head=p;
    }
    scanf("%d %d",&pos,&x);
    if(pos==1) {
        Node* p=new Node();
        p->data=x;
        p->next=head;
        head=p;
    } else {
        Node* cur=head;
        for(int i=1;i<pos-1;i++) {
            if(cur==NULL) return 0;
            cur=cur->next;
        }
        if(cur==NULL) return 0;
        Node* p=new Node();
        p->data=x;
        p->next=cur->next;
        cur->next=p;
    }
    for(Node* p=head;p!=NULL;p=p->next) {
        printf("%d ",p->data);
    }
    printf("\n");
    return 0;
}

4. 删除指定元素

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* next;
};
Node* head;
int main() {
    head=NULL;
    int n,x,del;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->next=head;
        head=p;
    }
    scanf("%d",&del);
    while(head!=NULL&&head->data==del) {
        Node* tmp=head;
        head=head->next;
        delete tmp;
    }
    if(head==NULL) return 0;
    Node* cur=head;
    while(cur->next!=NULL) {
        if(cur->next->data==del) {
            Node* tmp=cur->next;
            cur->next=tmp->next;
            delete tmp;
        } else {
            cur=cur->next;
        }
    }
    for(Node* p=head;p!=NULL;p=p->next) {
        printf("%d ",p->data);
    }
    printf("\n");
    return 0;
}

5. 查找元素

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* next;
};
Node* head;
int main() {
    head=NULL;
    int n,x,target,pos=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->next=head;
        head=p;
    }
    scanf("%d",&target);
    Node* cur=head;
    while(cur!=NULL) {
        pos++;
        if(cur->data==target) {
            printf("%d\n",pos);
            return 0;
        }
        cur=cur->next;
    }
    printf("-1\n");
    return 0;
}

6. 反转链表

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* next;
};
Node* head;
int main() {
    head=NULL;
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->next=head;
        head=p;
    }
    Node* pre=NULL;
    Node* cur=head;
    Node* nxt=NULL;
    while(cur!=NULL) {
        nxt=cur->next;
        cur->next=pre;
        pre=cur;
        cur=nxt;
    }
    head=pre;
    for(Node* p=head;p!=NULL;p=p->next) {
        printf("%d ",p->data);
    }
    printf("\n");
    return 0;
}

三、双链表

双链表：每个节点包含指向前一个节点和后一个节点的指针，可以从前往后遍历，也可以从后往前遍历。

节点结构

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

基本操作

1. 创建双链表

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* prev;
    Node* next;
};
Node* head,* tail;
int main() {
    head=NULL;
    tail=NULL;
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->prev=NULL;
        p->next=NULL;
        if(head==NULL) {
            head=p;
            tail=p;
        } else {
            tail->next=p;
            p->prev=tail;
            tail=p;
        }
    }
    printf("从头到尾：");
    for(Node* p=head;p!=NULL;p=p->next) {
        printf("%d ",p->data);
    }
    printf("\n");
    printf("从尾到头：");
    for(Node* p=tail;p!=NULL;p=p->prev) {
        printf("%d ",p->data);
    }
    printf("\n");
    return 0;
}

2. 在头部插入

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* prev;
    Node* next;
};
Node* head;
int main() {
    head=NULL;
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->prev=NULL;
        p->next=head;
        if(head!=NULL) {
            head->prev=p;
        }
        head=p;
    }
    for(Node* p=head;p!=NULL;p=p->next) {
        printf("%d ",p->data);
    }
    printf("\n");
    return 0;
}

3. 在指定位置插入

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* prev;
    Node* next;
};
Node* head;
int main() {
    head=NULL;
    int n,pos,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->prev=NULL;
        p->next=head;
        if(head!=NULL) {
            head->prev=p;
        }
        head=p;
    }
    scanf("%d %d",&pos,&x);
    if(pos==1) {
        Node* p=new Node();
        p->data=x;
        p->prev=NULL;
        p->next=head;
        if(head!=NULL) {
            head->prev=p;
        }
        head=p;
    } else {
        Node* cur=head;
        for(int i=1;i<pos-1;i++) {
            if(cur==NULL) return 0;
            cur=cur->next;
        }
        if(cur==NULL) return 0;
        Node* p=new Node();
        p->data=x;
        p->prev=cur;
        p->next=cur->next;
        if(cur->next!=NULL) {
            cur->next->prev=p;
        }
        cur->next=p;
    }
    for(Node* p=head;p!=NULL;p=p->next) {
        printf("%d ",p->data);
    }
    printf("\n");
    return 0;
}

4. 删除指定元素

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* prev;
    Node* next;
};
Node* head;
int main() {
    head=NULL;
    int n,x,del;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->prev=NULL;
        p->next=head;
        if(head!=NULL) {
            head->prev=p;
        }
        head=p;
    }
    scanf("%d",&del);
    while(head!=NULL&&head->data==del) {
        Node* tmp=head;
        head=head->next;
        if(head!=NULL) {
            head->prev=NULL;
        }
        delete tmp;
    }
    if(head==NULL) return 0;
    Node* cur=head;
    while(cur!=NULL) {
        if(cur->data==del) {
            Node* tmp=cur;
            if(cur->prev!=NULL) {
                cur->prev->next=cur->next;
            }
            if(cur->next!=NULL) {
                cur->next->prev=cur->prev;
            }
            cur=cur->next;
            delete tmp;
        } else {
            cur=cur->next;
        }
    }
    for(Node* p=head;p!=NULL;p=p->next) {
        printf("%d ",p->data);
    }
    printf("\n");
    return 0;
}

5. 双向遍历

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node* prev;
    Node* next;
};
Node* head,* tail;
int main() {
    head=NULL;
    tail=NULL;
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%d",&x);
        Node* p=new Node();
        p->data=x;
        p->prev=NULL;
        p->next=NULL;
        if(head==NULL) {
            head=p;
            tail=p;
        } else {
            tail->next=p;
            p->prev=tail;
            tail=p;
        }
    }
    printf("正向遍历：");
    for(Node* p=head;p!=NULL;p=p->next) {
        printf("%d ",p->data);
    }
    printf("\n");
    printf("反向遍历：");
    for(Node* p=tail;p!=NULL;p=p->prev) {
        printf("%d ",p->data);
    }
    printf("\n");
    return 0;
}

四、单链表 vs 双链表对比

特性 单链表 双链表
存储空间 每个节点1个指针 每个节点2个指针
遍历方向 只能向前 可以向前向后
插入操作 O(1)（已知前驱） O(1)（已知前驱或后继）
删除操作 需要知道前驱节点 直接删除（已知自身）
反向遍历 不支持 支持
应用场景 简单的线性结构 需要双向访问的场景

注意事项：

  1. 指针链表每次插入都要new新节点，删除时要delete释放内存
  2. 操作时要防止空指针访问（检查NULL）
  3. 双链表比单链表多维护一个prev指针，操作时要注意同时维护前后关系
  4. 链表适合频繁插入删除的场景，不适合频繁查找的场景
userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论