本文主要是介绍每周一数据结构之链表(Kotlin描述)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、链表的定义
链表是一种递归的数据结构，是一种线性结构，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)，简单来说链表并不像数组那样将数组存储在一个连续的内存地址空间里，它们可以不是连续的因为他们每个节点保存着下一个节点的引用（地址）
二、链表的类型
单链表
- 1、定义
单链表(又称单向链表)是链表中的一种，其特点是链表的链接方向是单向的，对链表的访问要从头部(head)开始，然后依次通过next指针读取下一个节点。
- 2、数据结构
单链表的数据结构可以分为两部分：数据域和指针域，数据域存储数据，指针域指向下一个存储节点的地址。注意: 单向链表只可向一个方向进行遍历
- 3、节点代码描述
//(Kotlin描述)
class LinkedNode(var value: Int) {var next: LinkedNode? = null //指向下一个存储节点的next指针
}
//(Java描述)
public class LinkedNode {int value;LinkedNode next; //指向下一个存储节点的next指针public LinkedNode(int value) {this.value = value;}
}
双链表
- 1、定义
双链表(又称双向链表)，是链表中一种，与单链表不同的是它的每个节点都有两个指针，分别指向直接后继节点和直接前驱节点；所以，从双链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
- 2、数据结构
双链表的数据结构可以分为三部分：prev指针域、数据域和next指针域，prev指针域指向上一个存储节点的地址(也即指向直接前驱节点),数据域存储数据，next指针域指向下一个存储节点的地址(也即指向直接后继节点)。注意: 单向链表可向两个方向进行遍历,分别为正序和逆序遍历
- 3、节点代码描述
//(Kotlin描述)
class LinkedNode(var value: Int) {var prev: LinkedNode? = null //指向上一个存储节点的prev指针var next: LinkedNode? = null //指向下一个存储节点的next指针
}
//(Java描述)
public class LinkedNode {int value;LinkedNode prev; //指向上一个存储节点的prev指针LinkedNode next; //指向下一个存储节点的next指针public LinkedNode(int value) {this.value = value;}
}
单向循环链表
- 1、定义
单向循环链表，只是在单链表的基础上，它的最后一个结点不再为null而是指向头结点，形成一个环。并且在节点结构上和单链表是一样的。因此，从单向循环链表中的任何一个结点出发都能找到任何其他结点。
- 2、数据结构
双向循环链表
- 1、定义
双向循环链表，只是在双链表的基础，它的头节点的prev指针不再为null，而是直接指向它的尾节点；它的尾节点的next指针不再为null，而是直接指向它的头节点。
- 2、数据结构
三、链表的特点
- 1、在内存中不是连续的内存地址空间，它只是一种逻辑上的线性连续结构。每个节点都含有指向下一个节点的next指针(可能指向下一个节点或null)
- 2、链表在节点的删除和增加有着很高效率，基本是O(1)常数级的时间效率，而顺序表实现删除和增加操作则是线性级O(n)的时间效率。所以一般用于用于元素节点频繁删除和增加
- 3、而对于链表的查找和获得第K个链表中节点，往往需要采用遍历的方式实现，所以一般需要O(n)的时间效率
- 4、链表长度是可变的，也就意味着在内存空间足够范围内，链表长度可以无限扩大。而顺序表则一般是固定的，当超出长度的时候则会进行扩容。
四、链表的基本操作
链表的构造
我们知道一个节点类型的变量就可以表示一条链表，只要保证对应的每个节点的next指针能够指向下一个节点即可或指向null(表示链表最后一个节点)
- 1、单链表的构造
//链表结构定义
class LinkedNode(var value: Int) {var next: LinkedNode? = null
}
//链表的构造
fun main(args: Array<String>) {val node1 = LinkedNode(value = 1)//创建节点1val node2 = LinkedNode(value = 2)//创建节点2val node3 = LinkedNode(value = 3)//创建节点3node1.next = node2//通过node1的next指针指向node2，把node1和node2连接起来node2.next = node3//通过node2的next指针指向node3，把node2和node3连接起来
}
- 2、双链表的构造
class LinkedNode(var value: Int) {var prev: LinkedNode? = nullvar next: LinkedNode? = null
}fun main(args: Array<String>) {val node1 = LinkedNode(value = 1)//创建节点1 此时的prev,next均为nullval node2 = LinkedNode(value = 2)//创建节点2 此时的prev,next均为nu这篇关于每周一数据结构之链表(Kotlin描述)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
