前言

数据结构还是得来一手。

一.关于链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。链表通过指针域能把多个元素串联起来。
一般的链表中每个元素只有一个指向下一个元素的指针域，而我们的双向链表却有两个指针域，其中一个指针域指向下一个元素，另一个指针域指向这个元素的上一个元素。
接下来看程序设计:

//单个节点结构体
typedef struct Node
{
    struct Node *prior;
    int data;
    struct Node *next;
}Node;

//链表结构体
typedef struct List
{
    Node *first;
    Node *last;
    int size;
}List;

其中Node是为链表的每一个元素，有数据域data，prior是指向前继的指针域，next是指向后继的指针域。List便是我们的双向链表的实现。其中first的next指针指向头节点，last的next指向尾节点，这两个指针能帮助我们找到链表的头节点和尾节点。size便是我们链表中拥有的元素个数。

二.链表的基本操作实现

1.初始化一个链表

初始化一个双向链表的代码如下:

//初始化一个节点的链表
void Initlist(List *list,int x)
{
    list->first=(Node*)malloc(sizeof(Node));
    list->last=(Node*)malloc(sizeof(Node));
    Node *p=(Node*)malloc(sizeof(Node));
    if(p==NULL)
    {
        cout<<"No space"<<endl;
        exit(0);
    }
    p->data=x;
    p->prior=NULL;
    p->next=NULL;
    list->first->next=p;
    list->last->next=p;
    list->size=1;
}

这里初始化的是带有一个节点的链表，这个节点的数据域就是输入的参数x。因为只有一个节点，所以头尾节点都是它，链表的头尾指针都指向它。这个节点的前继后继都是NULL(空),链表元素个数为1。

2.链表的插入

咱们先来看看头插

//头插
void push_front(List *list,int value)
{
    Node *p=list->first->next;
    Node *s=(Node*)malloc(sizeof(Node));
    if(s==NULL)
    {
        cout<<"No space"<<endl;
        exit(0);
    }
    s->data=value;
    s->next=p;
    p->prior=s;  
    s->prior=NULL;
    list->first->next=s;
    list->size++;
}

头插也是非常简单，也就是申请一个新节点，让这个节点变成新的头节点，那么为了让这个节点和链表串联起来，需要把这个节点的后继变成原来链表的头节点，这样这个节点的下个节点就是原来的头节点，这个节点的下下个节点就是原来链表的第二个节点了，这样就把新节点和原来的链表串联起来了，但是还没有完，我们还需要让这个新节点变成头节点。
咱们再来看看尾插：

//尾插
void push_last(List *list,int value)
{
    Node *p=list->last->next;
    Node *q=(Node*)malloc(sizeof(Node));
    if(q==NULL)
    {
        cout<<"No space"<<endl;
        exit(0);
    }
    
    q->data=value; 
    p->next=q;
    q->prior=p;
    q->next=NULL; 
    list->last->next=q;  
    list->size++;
}

尾插也很简单，就是申请一个新节点，让这个节点串在链表上并且让它成为新的尾节点。因此需要将原来尾节点的后继变成这个新节点。

再来看一看按位置插入：

//按位置插入,位置还是从0开始，插入的节点直接代替那个节点
int insert_loc(List *list,int loc,int value)
{
    Node *p=list->first;
    //待插入的节点
    Node *q=(Node*)malloc(sizeof(Node));
    if(q==NULL)
    {
        cout<<"No space"<<endl;
        exit(0);
    }
    q->data=value;
    if(loc==0)
    {
    //直接头插的情况
        push_front(list,value);
        return 0;
    }
    //直接尾插的情况
    if(loc>=(list->size-1))
    {
        push_last(list,value);
        return 0;
    }
    
    else
    {
        //找到loc位置,把链表分为前后半区，位置在前半区从表头开始找，在后半区从表尾开始找
        int m_node=int(list->size/2)-1;
        //前半区
        if(loc<=m_node)
        {
            //找到loc位置的前继节点
            for(int i=0;i<loc;i++)
            {
                p=p->next;
            }
            //插入
            p->next->prior=q;
            q->next=p->next;
            p->next=q;
            q->prior=p;
        }
        //后半区插入
        else
        {
            p=list->last->next;
            //算出从尾节点开始需要插入位置的从尾节点开始数的序号(从0开始)
            int loc3=list->size-loc-1;
            //找到要插入位置的节点
            for(int i=0;i<loc3;i++)
            {
                p=p->prior;
            }
            Node *d=p->prior;
            q->next=p;
            d->next=q;
            p->prior=q;
            q->prior=d;
        }
    }
        list->size++;
    return 0;
}

我们首先处理的是头插和尾插的情况。然后在除了这两种情况的插入的时候，我们把整个链表分为了前半区和后半区，要插入的位置在前半区就从表头开始遍历寻找要插入的位置的前继，在后半区的话就从尾节点开始遍历寻找这个要插入位置的节点。

3.链表的遍历

首先看代码：

//头部遍历
void show_list(List *list)
{
    cout<<"list size:"<<list->size<<"//";
    Node *p=list->first->next;
    while(p->next!=NULL)
    {
        cout<<p->data<<"->";
        p=p->next;
    }
    cout<<p->data<<"->NULL"<<endl;
}

//尾部遍历
void show_list_last(List *list)
{
    cout<<"list size:"<<list->size<<"//";
    Node *p=list->last->next;
    while(p->prior!=NULL)
    {
        cout<<p->data<<"->";
        p=p->prior;
    }
    cout<<p->data<<"->NULL"<<endl;
}

关于链表的遍历笔者写了两种，分别是从头节点从前往后和尾节点从后往前开始遍历。前者是不断去节点的后继，而后者则是不断取节点的前继。

4. 链表的删除

首先看头删：

//头删
int pop_front(List *list)
{
    Node *p=list->first->next;
    //第二个元素前驱置空
    p->next->prior=NULL;
    //更新头节点
    list->first->next=p->next;
    //原来的第一个元素后继置空
    p->next=NULL;
    //删除
    free(p);
    list->size--;
    return 0;
}

头删也就是让原链表的第二个节点变成头节点，把第一个节点从链表上拿下来。

再看看尾删:

//尾删
int pop_last(List *list)
{
    Node *p=list->last->next;
    Node *q=list->last->next;
    // list->last->next=p->prior;
    //倒数第二个元素后继置空
    p=p->prior;
    p->next->prior=NULL;
    // //更新尾节点
    list->last->next=p;
      
    // //原来最后一个元素前继为空
    p->next=NULL;
    //删除
    free(q);
    list->size--;
    
    return 0;
}

尾删也就是从链表上拿下尾节点，让原来的倒数第二个节点变成尾节点。

再来看看按位置删除：

//按位置删除
int delete_loc(List *list,int loc)
{
    Node *p=list->first;
    Node *q=(Node*)malloc(sizeof(Node));
    if(q==NULL)
    {
        cout<<"No space"<<endl;
        exit(0);
    }
    if(loc==0)
    {
        //头删
        pop_front(list);
        return 0;
    }
    else if(loc>=(list->size-1))
    {
        //尾删
        pop_last(list);
        return 0;
    }
    else
    {
        //中间位置,分成两个半区
        int m_node=int(list->size/2)-1;
        if(m_node<0)
        {
            m_node=0;
        }
        //前半区,那就是从头节点开始
        if(loc<=m_node)
        {
            //找到loc位置的前继节点
            for(int i=0;i<loc;i++)
            {
                p=p->next;
            }
            q=p->next;
            p->next=q->next;
            q->next->prior=p;
            free(q);
        }
        else
        {
            //在后半区，从尾节点开始找
            p=list->last->next;
            int loc3=list->size-loc-1;
            for(int i=0;i<loc3;i++)
            {
                p=p->prior;
            }
            q=p->prior;
            q->next=p->next;
            p->next->prior=q;
            free(p);
        }
    }
    list->size--;
    return 0;
}

按位置删除的代码和插入的思路差不多。

5.修改节点数据

来看看修改某一位置节点数据的实现：

//按位置更改数据，序号从0开始
int change_loc(List *list,int loc,int x)
{
    Node *p=list->first->next;
    if(loc==0)
    {
        //头删
        list->first->next->data=x;
        return 0;
    }
    else if(loc>=(list->size-1))
    {
        //尾删
        list->last->next->data=x;
        return 0;
    }
    else
    {
        //中间位置,分成两个半区
        int m_node=int(list->size/2)-1;
        //前半区,那就是从头节点开始
        if(loc<=m_node)
        {
            //找到loc位置的前继节点
            for(int i=0;i<loc;i++)
            {
                p=p->next;
            }
            p->data=x;
        }
        else
        {
            //在后半区，从尾节点开始找
            p=list->last->next;
            //算出从尾节点开始需要插入位置的从尾节点开始数的序号(从0开始)
            int loc3=list->size-loc-1;
            //找到要插入位置的节点
            for(int i=0;i<loc3;i++)
            {
                p=p->prior;
            }
            p->data=x;
        }
    }
    return 0;
}

再来看看修改某个值第一次出现位置的数据的代码：

//按值更改数据,x需要修改的数据,x_change 修改后的数据
int change_value(List *list,int x,int x_change)
{
    if(x==x_change)
    {
        cout<<"value error"<<endl;
        return 0;
    }
    Node *p=list->first->next;
    while(p->data!=x&&p->next!=NULL)
    {
        p=p->next;
    }
    if(p->next==NULL)
    {
        //到了尾节点
        if(p->data==x)
        {
            p->data=x_change;
            return 0;
        }
        cout<<"No this value"<<endl;
        return 0;
    }
    p->data=x_change;
    return 0;
}

代码实现也很简单，这里就 不多写了。

6.查找

查找某个位置的值：

int find_loc(List *list,int loc)
{
    if(loc>(list->size-1))
    {
        cout<<"no this loc"<<endl;
        return -1;
    }
    Node *p=list->first;
    for(int i=0;i<=loc;i++)
    {
        p=p->next;
    }
    return p->data;
}

查找某个值第一次出现在链表中的位置：

//返回某个值第一次出现在链表的位置
int find_value(List *list,int value)
{
    Node *p=list->first->next;
    int i=0;
    while(p->data!=value&&p->next!=NULL)
    {
        p=p->next;
        i++;
    }
    if(p->next==NULL)
    {
        if(p->data==value)
        {
            return i;
        }
        else
        {
            cout<<"value error:No this value"<<endl;
            return -1;
        }
    }
    return i;
}

清除链表

再来看看将一个链表变成初始化样子的代码，也就是只有一个节点的样子：

//清除链表中的节点，变成初始化的样子
void clear(List *list,int x)
{
    if(list->size==1)
    {
        cout<<"list had be clear"<<endl;
        return;
    }
    Node *p=list->first->next;
    Node *q=(Node*)malloc(sizeof(Node));
    if(q==NULL)
    {
        cout<<"No space"<<endl;
        exit(0);
    }
    while(p->next!=NULL)
    {
        q=p;
        p=p->next;
        q->next=NULL;
        q->prior=NULL;
        free(q);
    }
    list->first->next=list->last->next=p;
    p->next=NULL;
    p->prior=NULL;
    p->data=x;
    list->size=1;
}

其中参数x就是这个节点的值。

三.总结

总结的代码如下：
新建一个list.h文件：

#ifndef LIST_H
#define LIST_H
#include<iostream>
#include<malloc.h>
using namespace std;

//单个节点结构体
typedef struct Node
{
    struct Node *prior;
    int data;
    struct Node *next;
}Node;

//链表结构体
typedef struct List
{
    Node *first;
    Node *last;
    int size;
}List;

//初始化一个节点地链表
void Initlist(List *list,int x);
//头部遍历
void show_list(List *list);
//尾部遍历
void show_list_last(List *list);
//头插
void push_front(List *list,int value);
//尾插
void push_last(List *list,int value);
//按位置插入
int insert_loc(List *list,int loc,int value);
//头删
int pop_front(List *list);
//尾删
int pop_last(List *list);
//按位置删除
int delete_loc(List *list,int loc);
//按位置修改data
int change_loc(List *list,int loc,int x);
//按值修改数据
int change_value(List *list,int x,int x_change);
//返回某个位置上的data
int find_loc(List *list,int loc);
//返回某个值第一次出现在链表的位置
int find_value(List *list,int value);
//清除链表中的节点，变成初始化的样子
void clear(List *list,int x);


#endif

新建一个list.cpp文件，代码如下:

#include"list.h"

//初始化一个节点的链表
void Initlist(List *list,int x)
{
    list->first=(Node*)malloc(sizeof(Node));
    list->last=(Node*)malloc(sizeof(Node));
    Node *p=(Node*)malloc(sizeof(Node));
    if(p==NULL)
    {
        cout<<"No space"<<endl;
        exit(0);
    }
    p->data=x;
    p->prior=NULL;
    p->next=NULL;
    list->first->next=p;
    list->last->next=p;
    list->size=1;
}

//头部遍历
void show_list(List *list)
{
    cout<<"list size:"<<list->size<<"//";
    Node *p=list->first->next;
    while(p->next!=NULL)
    {
        cout<<p->data<<"->";
        p=p->next;
    }
    cout<<p->data<<"->NULL"<<endl;
}

//尾部遍历
void show_list_last(List *list)
{
    cout<<"list size:"<<list->size<<"//";
    Node *p=list->last->next;
    while(p->prior!=NULL)
    {
        cout<<p->data<<"->";
        p=p->prior;
    }
    cout<<p->data<<"->NULL"<<endl;
}
//头插
void push_front(List *list,int value)
{
    Node *p=list->first->next;
    Node *s=(Node*)malloc(sizeof(Node));
    if(s==NULL)
    {
        cout<<"No space"<<endl;
        exit(0);
    }
    s->data=value;
    s->next=p;
    p->prior=s;  
    s->prior=NULL;
    list->first->next=s;
    list->size++;
}

//尾插
void push_last(List *list,int value)
{
    Node *p=list->last->next;
    Node *q=(Node*)malloc(sizeof(Node));
    if(q==NULL)
    {
        cout<<"No space"<<endl;
        exit(0);
    }
    
    q->data=value; 
    p->next=q;
    q->prior=p;
    q->next=NULL; 
    list->last->next=q;  
    list->size++;
}

//按位置插入,位置还是从0开始，插入的节点直接代替那个节点
int insert_loc(List *list,int loc,int value)
{
    Node *p=list->first;
    //待插入的节点
    Node *q=(Node*)malloc(sizeof(Node));
    if(q==NULL)
    {
        cout<<"No space"<<endl;
        exit(0);
    }
    q->data=value;
    if(loc==0)
    {
        push_front(list,value);
        return 0;
    }
    //直接尾插的情况
    if(loc>=(list->size-1))
    {
        push_last(list,value);
        return 0;
    }
    
    else
    {
        //找到loc位置,把链表分为前后半区，位置在前半区从表头开始找，在后半区从表尾开始找
        int m_node=int(list->size/2)-1;
        //前半区
        if(loc<=m_node)
        {
            //找到loc位置的前继节点
            for(int i=0;i<loc;i++)
            {
                p=p->next;
            }
            //插入
            p->next->prior=q;
            q->next=p->next;
            p->next=q;
            q->prior=p;
        }
        //后半区插入
        else
        {
            p=list->last->next;
            //算出从尾节点开始需要插入位置的从尾节点开始数的序号(从0开始)
            int loc3=list->size-loc-1;
            //找到要插入位置的节点
            for(int i=0;i<loc3;i++)
            {
                p=p->prior;
            }
            Node *d=p->prior;
            q->next=p;
            d->next=q;
            p->prior=q;
            q->prior=d;
        }
    }
        list->size++;
    return 0;
}

//头删
int pop_front(List *list)
{
    Node *p=list->first->next;
    //第二个元素前驱置空
    p->next->prior=NULL;
    //更新头节点
    list->first->next=p->next;
    //原来的第一个元素后继置空
    p->next=NULL;
    //删除
    free(p);
    list->size--;
    return 0;
}

//尾删
int pop_last(List *list)
{
    Node *p=list->last->next;
    Node *q=list->last->next;
    // list->last->next=p->prior;
    //倒数第二个元素后继置空
    p=p->prior;
    p->next->prior=NULL;
    // //更新尾节点
    list->last->next=p;
      
    // //原来最后一个元素前继为空
    p->next=NULL;
    //删除
    free(q);
    list->size--;
    
    return 0;
}

//按位置删除
int delete_loc(List *list,int loc)
{
    Node *p=list->first;
    Node *q=(Node*)malloc(sizeof(Node));
    if(q==NULL)
    {
        cout<<"No space"<<endl;
        exit(0);
    }
    if(loc==0)
    {
        //头删
        pop_front(list);
        return 0;
    }
    else if(loc>=(list->size-1))
    {
        //尾删
        pop_last(list);
        return 0;
    }
    else
    {
        //中间位置,分成两个半区
        int m_node=int(list->size/2)-1;
        if(m_node<0)
        {
            m_node=0;
        }
        //前半区,那就是从头节点开始
        if(loc<=m_node)
        {
            //找到loc位置的前继节点
            for(int i=0;i<loc;i++)
            {
                p=p->next;
            }
            q=p->next;
            p->next=q->next;
            q->next->prior=p;
            free(q);
        }
        else
        {
            //在后半区，从尾节点开始找
            p=list->last->next;
            int loc3=list->size-loc-1;
            for(int i=0;i<loc3;i++)
            {
                p=p->prior;
            }
            q=p->prior;
            q->next=p->next;
            p->next->prior=q;
            free(p);
        }
    }
    list->size--;
    return 0;
}

//按位置更改数据，序号从0开始
int change_loc(List *list,int loc,int x)
{
    Node *p=list->first->next;
    if(loc==0)
    {
        //头删
        list->first->next->data=x;
        return 0;
    }
    else if(loc>=(list->size-1))
    {
        //尾删
        list->last->next->data=x;
        return 0;
    }
    else
    {
        //中间位置,分成两个半区
        int m_node=int(list->size/2)-1;
        //前半区,那就是从头节点开始
        if(loc<=m_node)
        {
            //找到loc位置的前继节点
            for(int i=0;i<loc;i++)
            {
                p=p->next;
            }
            p->data=x;
        }
        else
        {
            //在后半区，从尾节点开始找
            p=list->last->next;
            int loc3=list->size-loc-1;
            for(int i=0;i<loc3;i++)
            {
                p=p->prior;
            }
            p->data=x;
        }
    }
    return 0;
}

//按值更改数据,x需要修改的数据,x_change 修改后的数据
int change_value(List *list,int x,int x_change)
{
    if(x==x_change)
    {
        cout<<"value error"<<endl;
        return 0;
    }
    Node *p=list->first->next;
    while(p->data!=x&&p->next!=NULL)
    {
        p=p->next;
    }
    if(p->next==NULL)
    {
        //到了尾节点
        if(p->data==x)
        {
            p->data=x_change;
            return 0;
        }
        cout<<"No this value"<<endl;
        return 0;
    }
    p->data=x_change;
    return 0;
}

//返回某个位置上的data
int find_loc(List *list,int loc)
{
    if(loc>(list->size-1))
    {
        cout<<"no this loc"<<endl;
        return -1;
    }
    Node *p=list->first;
    for(int i=0;i<=loc;i++)
    {
        p=p->next;
    }
    return p->data;
}

//返回某个值第一次出现在链表的位置
int find_value(List *list,int value)
{
    Node *p=list->first->next;
    int i=0;
    while(p->data!=value&&p->next!=NULL)
    {
        p=p->next;
        i++;
    }
    if(p->next==NULL)
    {
        if(p->data==value)
        {
            return i;
        }
        else
        {
            cout<<"value error:No this value"<<endl;
            return -1;
        }
    }
    return i;
}

//清除链表中的节点，变成初始化的样子
void clear(List *list,int x)
{
    if(list->size==1)
    {
        cout<<"list had be clear"<<endl;
        return;
    }
    Node *p=list->first->next;
    Node *q=(Node*)malloc(sizeof(Node));
    if(q==NULL)
    {
        cout<<"No space"<<endl;
        exit(0);
    }
    while(p->next!=NULL)
    {
        q=p;
        p=p->next;
        q->next=NULL;
        q->prior=NULL;
        free(q);
    }
    list->first->next=list->last->next=p;
    p->next=NULL;
    p->prior=NULL;
    p->data=x;
    list->size=1;
}

然后是一个简单的运行程序，main.cpp:

#include"list.h"
#include<malloc.h>
#include<iostream>
using namespace std;


int main()
{
    int loc=0,x=2;
    List *L=(List*)malloc(sizeof(List));
    Initlist(L,1);
    push_last(L,2);
    push_front(L,3);
    push_last(L,7);
    insert_loc(L,9,4);
    push_last(L,6);
    show_list(L);
    show_list_last(L);
    return 0;
}

这里一定要注意(List*)malloc(sizeof(List))是必要的，不然我们的链表就没有内存空间就会运行不了。

# 链表 # c++ # c语言
Logo
腾讯云开发者社区

腾讯云面向开发者汇聚海量精品云计算使用和开发经验，营造开放的云计算技术生态圈。

更多推荐

Elasticsearch复杂数据类型终极指南：从入门到精通

Elasticsearch作为功能强大的搜索引擎，支持多种复杂数据类型，让开发者能够灵活处理各种结构化和非结构化数据。本文将带你全面了解Elasticsearch中的复杂数据类型，从基础概念到实际应用，助你轻松掌握数据建模的核心技巧。## 内部对象：构建层级化数据结构在Elasticsearch中，对象类型（Object）是最基础的复杂数据类型之一，用于表示具有嵌套关系的数据。例如，我们可

avatar 腾讯云开发者社区

终极指南：Flink SQL连接器版本管理从混乱到有序的升级之路

Apache Flink作为流处理领域的佼佼者，其SQL连接器的版本管理一直是开发者面临的核心挑战。本文将系统讲解Flink SQL连接器版本管理的最佳实践，帮助你轻松应对版本兼容性问题，实现从混乱到有序的升级之旅。## 连接器版本管理的常见痛点 😫在Flink应用开发中，连接器版本管理常常让开发者头疼不已。不同版本的连接器可能导致各种兼容性问题，例如API变更、功能差异甚至运行时错误。

avatar 腾讯云开发者社区

如何快速搭建Neon无服务器PostgreSQL：面向初学者的完整指南

Neon是一款革命性的无服务器PostgreSQL解决方案，它通过分离存储和计算层，实现了自动扩缩容、类代码式数据库分支以及零级扩展能力。本指南将帮助你从零开始搭建Neon开发环境，体验这款创新数据库的强大功能。## 准备工作：环境要求与依赖项在开始搭建Neon环境前，请确保你的系统满足以下要求：- Linux操作系统（推荐Ubuntu 20.04+或Debian 11+）- Git

avatar 腾讯云开发者社区