c++的链表-链表入门(C++)
2023-02-18 16:41:07 时间
从上的链表基础知识学习,进行总结如下:
1.单链表介绍
单链表与数组不同,数组中只存储元素的值,而单链表中除了数据的值外还包括了指向下一个节点的引用字段通常以next来表示。如下图表示,通过这个引用,单链表将所有节点按照顺序组织起来。
通常单链表如下定义:
// Definition for singly-linked list.
struct SinglyListNode {
int val;
SinglyListNode *next;
SinglyListNode(int x) : val(x), next(NULL) {}
与数组区别,我们无法随机访问链表中的元素,但如果我们想要获得第i个元素就需要从头指针开始遍历。平均时间复杂度为O(N)。
2.链表添加
链表添加又分为在中间添加、在头部添加以及在尾部添加,首先是头部添加:
头结点是整个链表的代表因此在头部进行添加节点时最重要的是添加后更新head:
初始化一个cur;将该结点连接到head上;将cur指定为head.
中间位置添加:
首先初始化cur
将cur->next连接到pred的下一个节点即pred->next
最后将断掉的pred->next 再连接到cur上。
这样与数组进行对比我们只需要O(1)的时间复杂度就可以将元素插入进链表。
3.删除操作
如果我们想要删除一个节点cur,那我们需要两步:
找到cur的上一个节点以及下一个节点;
连接上一个节点pred到cur下一个节点.
因为cur节点的下一个节点就是cur->nextc++的链表,但是上一个节点需要遍历才可以找到c++的链表,因此删除节点的时间复杂度为O(N)。
如果要删除第一个节点我们只需要把下一个节点赋予head即可。
4.设计链表
class MyLinkedList {
public:
struct node{
int val;
node *next;
node(int x): val(x),next(NULL){};
};
/** Initialize your data structure here. */
MyLinkedList() {
head = new node(0);
size = 0;
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
int get(int index) {
if(index(size-1)) return -1;
node *cur = head->next; //辅助指针指向第一个节点
while(index--) cur = cur->next;
return cur->val;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
void addAtHead(int val) {
node *cur = new node(val);
cur->next = head->next;
head->next = cur;
size++;
}
/** Append a node of value val to the last element of the linked list. */
void addAtTail(int val) {
node *cur = head;
while(cur->next)
{
cur = cur->next;
}
node *newnode = new node(val);
newnode->next = cur->next; //把结尾最后一个节点信息保存下来
cur->next = newnode; //将新节点连接在cur之后
size++;
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
void addAtIndex(int index, int val) {
if(index==0) addAtHead(val);
else if(index == size) addAtTail(val);
else if(index > size) return;
else{
node *pred = head; //是在indexth之前插入 之后可以head->next
node *ans = new node(val);
//node *cur = new node(0);
while(index>0)
{
pred = pred->next;
index--;
}
ans->next = pred->next;
pred->next = ans;
size++;
}
}
/** Delete the index-th node in the linked list, if the index is valid. */
void deleteAtIndex(int index) {
if(index < 0 || index >=size)
return;
node *cur = head;
while(index>0)
{
cur = cur->next;
index--;
}
cur->next = cur->next->next;
size--;
}
private:
int size;
node *head;
};
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList* obj = new MyLinkedList();
* int param_1 = obj->get(index);
* obj->addAtHead(val);
* obj->addAtTail(val);
* obj->addAtIndex(index,val);
* obj->deleteAtIndex(index);
本文共 482 个字数,平均阅读时长 ≈ 2分钟
相关文章
- Go语言微服务开发框架:Go chassis
- Django框架:11、from组件校验用户数据、渲染标签、展示报错信息、校验参数补充、源码刨析、modelform组件、django中间件
- Django框架:10、Ajax补充说明、多对多三种创建方法、Django内置序列化组件、批量操作数据方法、分页器思路
- Django框架:9、Ajax简介、基本语法、数据编码格式、携带文件数据
- Django框架:8、聚合查询、分组查询、F与Q查询、ORM查询优化、ORM事务操作、ORM常用字段类型、ORM常用字段参数
- Django框架:7、模型层之ORM执行SQL语句、双下划线查询、ORM外键字段的创建、ORM跨表查询
- Django框架:6、模型层之ORM查询关键字、SQL语句转换
- Djiango框架:5、pycharm虚拟环境,视图层之三板斧、JsonResponse对象、request对象、FBV与CBV,模板层之模板语法、模板传值、模板过滤器
- Django框架:4、视图层之路由匹配、转换器、正则匹配、路由反向解析、路由分发、名称空间
- Django框架:3、Django请求生命周期(重要)
- Django框架:2、静态文件配置、form表单、request对象、pycharm链接数据库、django链接数据库、ORM框架
- Django框架:1、手撸web框架、Django框架简介、安装与使用和小白必会三板斧
- 记录在linux上单机elasticsearch8和kibana8
- 《痞子衡嵌入式半月刊》 第 69 期
- 痞子衡嵌入式:对比恩智浦全系列MCU(包含Kinetis/LPC/i.MXRT/MCX)的GPIO电平中断设计差异
- 痞子衡嵌入式:我被邀请做科锐国际旗下数科同道主办的技术沙龙嘉宾
- 痞子衡嵌入式:低功耗&高性能边缘人工智能应用的新答案 - MCXN947
- 《痞子衡嵌入式半月刊》 第 68 期
- 痞子衡嵌入式:我为2021 TencentOS Tiny AIoT应用创新大赛做了场直播培训
- 痞子衡嵌入式:我被邀请做贸泽电子&与非网联合推出的《对话工程师》节目嘉宾