c++的链表-链表入门(C++)
2023-06-13 09:16:12 时间
从上的链表基础知识学习,进行总结如下:
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分钟
相关文章
- 使用C++ OpenCV实现椭圆区域检测与Aruco码的生成与检测并估计位姿
- c++语言截取字符串,详解C++ string常用截取字符串方法
- pip 安装 torch 报错Microsoft Visual C++ Redistributable is not installed
- PTA -7-51 两个有序链表序列的合并(C++)
- 刷LeetCode链表之前你需要掌握的设置结点技巧C++
- LeetCode 21. 合并两个有序链表 题解 C++
- LeetCode142. 环形链表 II(C++俩种解法)
- c++ auto类型_auto C++
- C++ docker_docker部署mysql
- C++基本概念_c语言 c++区别
- 2022蓝桥杯(c/c++ B组)-刷题统计
- pybind11 大大简化 Python 调用 C/C++
- C++ 不知树系列之认识二叉树(数组、链表存储的实现)
- C/C++ Qt QThread 线程组件应用
- 第十四届蓝桥杯集训——练习解题阶段(无序阶段)-ALGO-456 求链表各节点的平均值(C++解法)
- c++字符串
- 【C++】开散列哈希表封装实现unordered_map和unordered_set
- 关于C++使用指针堆和栈的区别分析
- 基于一致性hash算法C++语言的实现详解
- 探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)
- c++读写文件流实例程序讲解