链表
链表简介
链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(log n)和O(1)。
使用链表结构可以克服数组链表需要预先知道数据大小的缺点,链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理。但是链表失去了数组随机读取的优点,同时链表由于增加了结点的指针域,空间开销比较大。链表最明显的好处就是,常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序,数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点,但是不允许随机存取。链表有很多种不同的类型:单向链表,双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言,如C,C++和Java依靠易变工具来生成链表。
中文名 | 英文名 | 分类 | 构成 |
---|---|---|---|
链表 | linked list | 计算机数据结构 | 一系列节点(包含元素和指针) |
链表分为两大块,分别是单链表和双链表,接下来给大家一一讲解。
单链表
单链表每个节点都只有一个元素和一个指针,每个节点的指针指向下一个节点。
STL
实现:
list(链表)
定义:
list <变量类型> 变量名称;
常用函数:
push_back(); 添加元素到list尾部。
push_back(); 添加元素到list头部。
pop_back(); 从list尾部删除元素。
pop_front(); 从list头部删除元素。
front(); 获得list头部元素。
back(); 获得list尾部元素。
merge(); 合并两个list(两个list必须事先有序)。
sort(); list排序,默认升序排序。
手写单链表
双向链表
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
唉?我好像重复发了
这个双链表代码没怎么看懂,能在详细的说一下吗(配图就更好了)
我有陪啊。。。。点连接
我看了你代码,就你链接里的那个双链表的代码,,代码实现插入和删除的过程不是很清楚
还有就是每一个步骤都是怎么实现的,代码没有具体的注释,有点不懂
因为这个算法基础课里有,所以没有写很清楚,你可以去找到那道题听一下
算法基础课里面的讲解很详细吗
Y总讲的挺好的
谢谢
这个双链表代码没怎么看懂,能在详细的说一下吗(配图就更好了)