链表

链表是数据结构之一,链表中的数据是呈线性排列的,链表中,数据的添加和删除的效率很高,时间复杂度为O(1),但是查询的效率就较慢,与数组正好相反.下一篇文章会介绍一下数组.

链表中每个数据都有一个指针,用来指向下一个数据的内存地址
在链表中,数据一般是分散存储在内存中的,无须连续存储在内存,所以想要访问数据的话需要从第一个数据开始访问,顺着指针的指向来进行一一访问,比如:


根据指针的方向来看,那么我们想要获取3这个数据的话,需要从1开始一一进行向下访问,所以链表的查询速度是比较慢的
但是如果想要添加数据,只需要改变添加位置的前后指针的方向即可,比如我们想在4之前加一个5:


将2的指针指向5,然后5的指针指向4,这样数据的添加就完成了,删除也是同理,比如我们想把4删掉:

咱们就可以直接让5这个数据指向4的指针更换到指向3即可,虽然4还存在于内存中,但是已经无法访问了,如果后期需要用到4这个数据的存储空间的时候,只需要直接覆盖就可以了.

另外,链表的尾部其实也是可以使用指针来指向其他存储空间的,比如我们把它指向头的位置,那么就会将链表变成一个环形.这就是变成了环形链表或者叫循环链表,循环链表是没有头和尾的概念的,想保存固定数量的最新数据的时候通常可以使用这种方式

另外指针还可以设置为2个,并且指向前后数据,那么就会变成双向链表,使用这种链表的时候,不止可以从前往后遍历,还可以从后往前遍历链表中的数据,但是有优点就有缺点,使用双向链表的时候,指针数的增加会导致存储空间需要的内存增加,添加和删除的时候也要更改更多的指针方向.

在本次学习数据结构中暂不介绍实现,只是一个简单的介绍每种数据结构的概念学习,后续会更新所有的数据结构及常用算法的实现代码.

个人学习记录,如有错误,欢迎大佬指出,谢谢