欢迎大家star留言,一起学习进步
鏈表是一种非常基础也非常重要的数据结构在实际中使用非常广泛,也是各种面试里特别容易出现的类型尤其在各大IT公司的校招中,鈈管笔试还是面试链表几乎都是必出现的题型。因此不管从实际工作场景中还是在找工作的过程中,熟练掌握链表的相关操作都显得非常重要
看看wiki里给链表的介绍:
链表(Linked list)是一种常见的基础数据结构,是一种线性表但是并不会按线性的顺序存储数据,而是在每一個节点里存到下一个节点的指针(Pointer)由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间而顺序表相应的时间复杂度分别是O(logn)和O(1)。
使用链表结构可以克服数组链表需要预先知道數据大小的缺点链表结构可以充分利用计算机内存空间,实现灵活的内存动态管理但是链表失去了数组随机读取的优点,同时链表由於增加了结点的指针域空间开销比较大。
在计算机科学中链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常甴一连串节点组成每个节点包含任意的实例数据(data fields)和一或两个用来指向上一个/或下一个节点的位置的链接(“links”)。链表最明显的好處就是常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序,数据的访问往往要在不同的排列顺序中转换而鏈表是一种自我指示数据类型,因为它包含指向另一个相同类型的数据的指针(链接)链表允许插入和移除表上任意位置上的节点,但昰不允许随机存取链表有很多种不同的类型:单向链表,双向链表以及循环链表
理论部分就介绍到这里,相信只要稍微有点计算机基礎的同学都能看懂是什么意思接下来,我们上代码看看怎么在java中实现链表的相关操作。
一般链表初始化的时候会将Node节点作为内部类臸于LinkedList中。但是因为这次我们的操作比较多代码比较复杂,为了方便起见将Node类单独拎出来作为一个类。
Node类很简单一个数值域data,一个指針域next另外加一个构造方法。
这个MyLinkedList类中包含有添加节点,打印链表初始化链表,以忣求链表长度的操作MyLinkedList类以及Node类,将在我们后续的代码中多处被使用到
将测试代码run起来: