C++实现单链表的头插，尾插以及遍历

小王不头秃

发布于 2024-06-19 15:09:39

1790

发布于 2024-06-19 15:09:39

单链表

Node结构体：

struct Node{
int data;   //该节点代表的值
Node *next;   //指向下一个节点地址的指针
};

构建头结点

这里采用的是头节点的方式，使用头节点的好处是在对单链表进行操作时不需要进行特殊的处理

Node* create(){
   Node *first=new Node;
   first->next=NULL;
   return first;
}

头插法建立单链表

使用头插法插入节点之前

使用头插法插入节点之后

要实现头插，最关键的一步就是如何使头结点的next指向新插入的节点，并且新插入的节点要指向未插入前的第一个节点。实现代码：

void add(Node *node,Node *first){   //first是头结点    node是待插入的节点
    if(node==NULL||first==NULL){
        return;
    }
    //这两步不可以颠倒
    node->next=first->next;       
    first->next=node;
}

头插法建立单链表

尾插法最关键的是要有一个尾指针，指向最后一个节点，插入过程就相对简单一些，即首先修改最后一个节点的next为新插入的节点，然后将尾指针指向新插入的节点。代码：

//尾插
void addFromEnd(Node *node,Node *&E){
  E->next=node;
  E=node;
}

单链表的遍历

void forEach(Node *first){
    if(first==NULL){
        return;
    }
    Node *p;
    p=first->next;
    while(p!=NULL){
        cout<<"第"<<p->data<<"个节点:    "<<p->data<<endl;
        p=p->next;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-06-19，如有侵权请联系 cloudcommunity@tencent.com 删除

链表