怎么做付款链接网站,网站营销费用,成都网站建设单位,推广方案的内容有哪些链表基础知识 基础操作 链表基础操作链表基础知识插入节点删除节点查找节点 707. 设计链表实现#xff1a;单向链表#xff1a;实现#xff1a;双向链表 链表基础操作
链表基础知识
在数据结构的学习过程中#xff0c;我们知道线性表【一种数据组织、在内存中存储的形式】… 链表基础知识 基础操作 链表基础操作链表基础知识插入节点删除节点查找节点 707. 设计链表实现单向链表实现双向链表 链表基础操作
链表基础知识
在数据结构的学习过程中我们知道线性表【一种数据组织、在内存中存储的形式】是线性结构的其中线性表包括顺序表和链表。数组就是顺序表其各个元素在内存中是连续存储的。 链表则是由数据域和指针域组成的结构体构成的数据域是一个节点的数据指针域存储下一个节点的地址下一个节点依靠上一个节点的指针域寻址。给出整个链表的头节点地址指针head后就能依次访问链表的每个节点。 链表定义 链表是一种递归的数据结构它或者为空null或者是指向一个结点node的引用该节点还有一个元素和一个指向另一条链表的引用。 根据链表间节点的指向链表可以分为以下三种
单向链表指针域中只有指向下一个节点的地址只能单向遍历链表 双向链表指针域中有两个指针一个指向前一个节点一个指向下一个节点可以双向遍历链表 循环链表链表形成环最后一个节点的指针域不赋值为null而是指向头节点head
定义一个链表节点是单向的链表 //定义一个结构体ListNode表示链表节点struct ListNode {int val; //数据域这里用的int根据实际情况选择type比如char、float等ListNode *next; //指针域存下一个节点的地址所以是指针类型并且下一个节点也是该结构体所以是ListNode*//自定义构造函数给数据域和指针域赋值ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}};链表中头节点直接用head指针访问其他节点用currentNode-next的指针访问可见链表的头节点是特殊的。在插入、删除操作中针对头节点都需要做特殊的处理会较麻烦因此在头节点前增加一个虚拟头节点【也叫附加头节点、哨兵节点等】dummy_head虚拟头节点的指针域存head即dummy_head-next head数据域无效因为后续不会用到。给定dummy_head后其他节点都用当前节点的next指针访问即currentNode-next 接下来介绍对链表进行的一些操作【穿针引线法】
插入节点
在链表中的一个位置插入节点需要先断开插入位置前后两个节点的链接再和这两个节点建立新的链接先cur-next pre-next再pre-next cur 如果先pre-next cur就会丢失sur这个节点的地址。 上面是普通的情况那么针对头节点尾节点的特殊情况呢 末尾节点其实也没有什么特殊的只是suc是NULL也就是pre-next为NULL按照上述的两步操作也是ok的。问题是在头节点前插入
如果是普通链表头节点前什么都没有pre是NULL的。只进行①cur-next headhead cur【头节点是新插入的节点】如果前面有虚拟头节点那么pre就是dummy_head头节点和其他节点是一样的操作
删除节点
从链表中删除节点可以是删除指定位置的比如删除第三个节点也可以是根据节点值删除的比如删除值等于target的节点。删除节点时将被删除节点的前面节点和后面节点连接起来的同时断开被删除节点和其前面一个、后面一个节点的连接并且要释放掉被删除节点的空间pre-next cur-nextdelete cur。 针对头节点和尾节点的特殊情况呢 将尾节点看作是下一个节点是null的节点处理和其他节点一样。问题同样是头节点删除头节点的话
普通链表直接tmp head-nextdelete headhead tmp添加了虚拟头节点的链表删除头节点其pre dummy_headcur head直接按照正常节点删除即可。 从删除头节点和在头节点前插入节点的分析就可以知道添加了虚拟头节点dummy_head后对头节点的操作不需要单独讨论所有节点操作一致。
查找节点
比如按位置查找某个节点返回其节点值比如按值查找链表中是否存在值等于target的节点。因为链表是通过节点的指针域而将各个节点连接起来的它不能像数组一样直接按下标查找【数组各元素在内存空间是连续存储的通过下标就能够定位到内存空间】。要查找链表中某个节点需要遍历链表需要O(n)的时间复杂度。
707. 设计链表
题目链接707.设计链表 题目内容 理解题意实际上就是实现一个链表类可以单向也可以双向其中要涉及到插入节点在头部插入、在尾部插入、根据下标index在指定位置插入删除节点根据下标index获取节点值。
实现单向链表
以下代码实现的是有虚拟头节点的单向链表并且在类中定义一个_size变量存储链表中节点数量以便根据下标index删除、添加节点时判断下标是否合理。 另外在节点末尾处添加节点可认为是index _size时在index处插入节点
class MyLinkedList {
private://定义类的私有变量int _size; //链表中节点数量不包括虚拟头节点//定义链表节点结构体struct ListNode {int val; //数据域ListNode *next; //指针域//构造函数ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}};//链表附加头节点整个链表的开始ListNode* _dummyhead;
public: //自定义类的构造函数MyLinkedList() {_dummyhead new ListNode(0); //新建虚拟头节点_size 0; //初始化链表中有效节点数量为0}//根据下标返回节点valueint get(int index) {//下标无效if(index _size)return -1;ListNode* currNode _dummyhead; //从虚拟头节点开始访问//遍历到下标为index的节点for(int i 0; i index; i){currNode currNode-next;} return currNode-val; //返回value}//在头部添加节点void addAtHead(int val) {ListNode * newNode new ListNode(val); //先构造一个新节点newNode-next _dummyhead-next; //直接在虚拟头节点后插入_dummyhead-next newNode;_size; //插入节点后链表节点数量1}//在尾部添加节点 //实际上就是在index为_size的地方添加节点void addAtTail(int val) {addAtIndex(_size,val);}//在指定下标index位置处插入节点void addAtIndex(int index, int val) {if(index _size) return ; //下标不合理ListNode* newNode new ListNode(val); //构造一个新节点ListNode* prevNode _dummyhead;//找到需要插入的地方while(index) {prevNode prevNode-next;index--;} //插入节点 newNode-next prevNode-next;prevNode-next newNode;_size; //节点数量}//删除指定位置的节点void deleteAtIndex(int index) {if(index _size) return; //下标不合理ListNode* prevNode _dummyhead;//找到要删除的节点的前一个节点while(index){prevNode prevNode-next;index--;}//tmp为要删除的节点ListNode* tmp prevNode-next;//要删除节点前后两个节点建立新连接prevNode-next tmp-next;//删除tmp节点释放空间delete tmp;_size--; //链表中节点数量-1}
};实现双向链表
双向链表就是每个节点有两个指针一个指向前驱节点preNode一个指向后驱节点succNode插入、删除节点时需要对两个指针的指向都处理
插入一个节点时preNode-next newNode newNode-next succNode succNode-prior newNode newNode-prior preNode删除一个节点时preNode-next succNodesuccNode-prior preNode 这里需要注意的是succNode实际上是currNode-next如果是删除最后一个节点或者在最后一个节点后追加一个节点succNodeNULL为了和其他节点统一操作同样在末尾增加一个虚拟尾节点。 双向链表可以双向遍历在index位置插入、删除、查询节点值时可以先判断index是在链表前半段还是后半段确定是从前往后遍历更快还是从后往前遍历更快。 代码如下C
class MyLinkedList {
private:int _size; //链表中有效节点数量不包括虚拟头节点、虚拟尾节点struct ListNode { //定义链表节点结构体int val;ListNode *next, *prior; //双向链表需要有两个指针ListNode() : val(0), next(nullptr), prior(nullptr) {}ListNode(int x) : val(x), next(nullptr), prior(nullptr) {}ListNode(int x, ListNode *next, ListNode *prior) : val(x), next(next), prior(prior) {}};ListNode *_dummyhead, *_dummytail; //虚拟头节点和虚拟尾节点
public: MyLinkedList() {_dummyhead new ListNode(0); //虚拟头节点_dummytail new ListNode(0); //虚拟尾节点//建立虚拟头节点和虚拟尾节点之间的连接_dummyhead-next _dummytail; _dummytail-prior _dummyhead;_size 0; //链表中有效节点数量}int get(int index) {//下标无效if(index _size)return -1;ListNode *currNode;//判断index在前半段if(index _size/2){currNode _dummyhead;//从前往后遍历更快for(int i 0; i index; i){currNode currNode-next;} }else{ //index在后半段currNode _dummytail;//从后往前遍历更快for(int i _size-1; i index ;i--){currNode currNode-prior;}}return currNode-val;}//在头部添加节点即在虚拟头节点后插入void addAtHead(int val) {ListNode *newNode new ListNode(val);//建立四条新的连接_dummyhead-next-prior newNode;newNode-next _dummyhead-next;_dummyhead-next newNode;newNode-prior _dummyhead;_size;}//在尾部插入节点等于在index _size的位置插入节点void addAtTail(int val) {addAtIndex(_size,val);}//在指定index处插入void addAtIndex(int index, int val) {if(index _size) return ;ListNode* newNode new ListNode(val);ListNode *prevNode _dummyhead, *succNode _dummytail;if(index _size/2){ //从前往后更快定位到index前的节点for(int i 0; i index; i){prevNode prevNode-next;}succNode prevNode-next;}else{ //从后往前更快定位到index前的节点for(int i _size - 1; i index; i--){succNode succNode-prior;}prevNode succNode-prior;}//插入一个节点后新增四条连接succNode-prior newNode; newNode-next succNode;prevNode-next newNode;newNode-prior prevNode;_size;}//删除index处的节点void deleteAtIndex(int index) {if(index _size) return;ListNode *prevNode _dummyhead, *succNode _dummytail;//根据index和_size的关系决定从前往后遍历还是从后往前遍历if(index _size/2){for(int i 0; i index; i){prevNode prevNode-next;}succNode prevNode-next-next;}else{for(int i _size - 1; i index; i--){succNode succNode-prior;}prevNode succNode-prior-prior;}ListNode* tmp prevNode-next;//preNode和succNode之间建立双向连接prevNode-next succNode; succNode-prior prevNode;delete tmp;_size--;}
};
