新乡手机网站建设官网,杭州网站制作方法,网站规划与设计课程设计,汉中市住建局建设厅网站官网链表的概念
链表是一种物理存储结构上非连续存储结构#xff0c;数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
链表是一种通过指针串联在一起的线性结构#xff0c;每一个节点由两部分组成#xff0c;一个是数据域一个是指针域#xff08;存放指向下一个节点的…链表的概念
链表是一种物理存储结构上非连续存储结构数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
链表是一种通过指针串联在一起的线性结构每一个节点由两部分组成一个是数据域一个是指针域存放指向下一个节点的指针最后一个节点的指针域指向null空指针的意思。
链表的一个结点示意图 : 在c/c语言中链表一般使用结构体来定义实现 ;
struct Node{int data;Node*next;
};
链表的类型
单链表 : 链表的入口节点称为链表的头结点也就是head。
双链表
在单链表中的指针域只能指向节点的下一个节点。
双链表每一个节点有两个指针域一个指向下一个节点一个指向上一个节点。
双链表 既可以向前查询也可以向后查询。 循环链表
循环链表顾名思义就是链表首尾相连。 链表的存储方式
数组是在内存中是连续分布的但是链表在内存中可不是连续分布的。
链表是通过指针域的指针链接在内存中各个节点。
所以链表中的节点在内存中不是连续分布的 而是散乱分布在内存中的某地址上分配机制取决于操作系统的内存管理。
如图所示 : 这个链表起始节点为2 终止节点为7 各个节点分布在内存的不同地址空间上通过指针串联在一起。
链表的定义
这里我给出C/C的定义链表节点方式如下所示
// 单链表
struct ListNode {int val; // 节点上存储的元素ListNode *next; // 指向下一个节点的指针ListNode(int x) : val(x), next(NULL) {} // 节点的构造函数
};链表的操作
删除结点
比如删除下图中的D结点 : 要做的是将c的尾结点指向E结点然后再将d结点手动释放一下就行了 ;
添加结点
如图所示 可以看出链表的增添和删除都是O(1)操作也不会影响到其他节点。
但是要注意要是删除第五个节点需要从头节点查找到第四个节点通过next指针进行删除操作查找的时间复杂度是O(n)。
性能分析 数组在定义的时候长度就是固定的如果想改动数组的长度就需要重新定义一个新的数组。
链表的长度可以是不固定的并且可以动态增删 适合数据量不固定频繁增删较少查询的场景。
参考 :
https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#%E9%93%BE%E8%A1%A8%E7%9A%84%E6%93%8D%E4%BD%9C
