链表数据结构的定义和类型、操作......Kotlin语言示例
一、链表的定义
链表是一种递归的数据结构，是一种线性结构，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)，简单来说链表并不像数组那样将数组存储在一个连续的内存地址空间里，它们可以不是连续的因为他们每个节点保存着下一个节点的引用（地址）
二、链表的类型
单链表
单链表(又称单向链表)是链表中的一种，其特点是链表的链接方向是单向的，对链表的访问要从头部(head)开始，然后依次通过next指针读取下一个节点。
单链表的数据结构可以分为两部分：数据域和指针域，数据域存储数据，指针域指向下一个存储节点的地址。注意: 单向链表只可向一个方向进行遍历
classLinkedNode(var value: Int) {
var next: LinkedNode? = null
}
复制代码publicclassLinkedNode{
int value;
LinkedNode next; publicLinkedNode(int value){
this.value = value;
}
}
复制代码双链表
双链表(又称双向链表)，是链表中一种，与单链表不同的是它的每个节点都有两个指针，分别指向直接后继节点和直接前驱节点；所以，从双链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
双链表的数据结构可以分为三部分：prev指针域、数据域和next指针域，prev指针域指向上一个存储节点的地址(也即指向直接前驱节点),数据域存储数据，next指针域指向下一个存储节点的地址(也即指向直接后继节点)。注意: 单向链表可向两个方向进行遍历,分别为正序和逆序遍历
classLinkedNode(var value: Int) {
var prev: LinkedNode? = nullvar next: LinkedNode? = null
}
复制代码publicclassLinkedNode{
int value;
LinkedNode prev;
LinkedNode next; publicLinkedNode(int value){
this.value = value;
}
}
复制代码单向循环链表
单向循环链表，只是在单链表的基础上，它的最后一个结点不再为null而是指向头结点，形成一个环。并且在节点结构上和单链表是一样的。因此，从单向循环链表中的任何一个结点出发都能找到任何其他结点。
双向循环链表
双向循环链表，只是在双链表的基础，它的头节点的prev指针不再为null，而是直接指向它的尾节点；它的尾节点的next指针不再为null，而是直接指向它的头节点。
三、链表的特点
- 1、在内存中不是连续的内存地址空间，它只是一种逻辑上的线性连续结构。每个节点都含有指向下一个节点的next指针(可能指向下一个节点或null)
- 2、链表在节点的删除和增加有着很高效率，基本是O(1)常数级的时间效率，而顺序表实现删除和增加操作则是线性级O(n)的时间效率。所以一般用于用于元素节点频繁删除和增加
- 3、而对于链表的查找和获得第K个链表中节点，往往需要采用遍历的方式实现，所以一般需要O(n)的时间效率
- 4、链表长度是可变的，也就意味着在内存空间足够范围内，链表长度可以无限扩大。而顺序表则一般是固定的，当超出长度的时候则会进行扩容。
四、链表的基本操作
链表的构造
我们知道一个节点类型的变量就可以表示一条链表，只要保证对应的每个节点的next指针能够指向下一个节点即可或指向null(表示链表最后一个节点)
classLinkedNode(var value: Int) {
var next: LinkedNode? = null
}
funmain(args: Array<String>) {
val node1 = LinkedNode(value = 1)val node2 = LinkedNode(value = 2)val node3 = LinkedNode(value = 3)
node1.next = node2
node2.next = node3
}
复制代码
classLinkedNode(var value: Int) {
var prev: LinkedNode? = nullvar next: LinkedNode? = null
}
funmain(args: Array<String>) {
val node1 = LinkedNode(value = 1)val node2 = LinkedNode(value = 2)val node3 = LinkedNode(value = 3)
node1.next = node2
node2.prev = node1
node2.next = node3
node3.prev = node2
}
复制代码链表表头插入节点
在链表表头插入一个节点是最简单的一种操作，一般处理方式，先创建一个oldFirst指向第一个节点，然后重新创建一个新的节点,将新节点的next指向oldFirst指向的节点，first指向新插入的节点。
funinsertToHead(head: LinkedNode): LinkedNode {
var first: LinkedNode = head
val oldFirst: LinkedNode = head
first = LinkedNode(value = 6)
first.next = oldFirst
return first
}
复制代码
funinsertToHead(head: LinkedNode): LinkedNode {
var first: LinkedNode = head
val oldFirst: LinkedNode = head
first = LinkedNode(value = 6)
oldFirst.prev = first
first.next = oldFirst
return first
}
复制代码在表头删除节点
fundeleteToHead(head: LinkedNode): LinkedNode? {
var first: LinkedNode? = head
first = first?.next
return first
}
复制代码
fundeleteToHead(head: LinkedNode): LinkedNode? {
var first: LinkedNode? = head
first = first?.next
first?.prev = nullreturn first
}
复制代码在表尾插入节点
funinsertToTail(head: LinkedNode): LinkedNode? {
var last = getTailNode(head) val oldLast = last
last = LinkedNode(value = 4)
oldLast?.next = last
return head
}
复制代码
funinsertToTail(head: LinkedNode): LinkedNode? {
var last = getTailNode(head) val oldLast = last
last = LinkedNode(value = 4)
oldLast?.next = last
last.prev = oldLast
return head
}
复制代码在其他位置插入节点
funinsertToOther(head: LinkedNode): LinkedNode? {
val current = getInsertPrevNode(head) val newNode = LinkedNode(value = 6)
newNode.next = current?.next
current?.next = newNodereturn head
}
复制代码
funinsertToOther(head: LinkedNode): LinkedNode? {
val current = getInsertPrevNode(head) val newNode = LinkedNode(value = 6)
newNode.next = current?.next
newNode.prev = current
current?.next = newNode
current?.next?.prev = newNode return head
}
复制代码在其他位置删除节点
fundeleteToOther(head: LinkedNode): LinkedNode? {
val current = getInsertPrevNode(head)
current?.next = current?.next?.next
return head
}
复制代码
fundeleteToOther(head: LinkedNode): LinkedNode? {
val current = getDeletePrevNode(head)
current?.next = current?.next?.next
current?.next?.prev = current
return head
}
复制代码链表的遍历
funtraverseLinkedList(head: LinkedNode?) {
var current = head
while (current != null){
println()
current =
}
}
复制代码获取链表的大小
fungetLength(head: LinkedNode?): Int {
var len = 0var current = head
while (current != null){
len++
current =
}
return len
}
复制代码五、链表实现栈和队列数据结构
1、链表实现栈结构
由于栈是一个表，因此任何实现表的方法都能实现栈。显然，Java中常用的ArrayList和LinkedList集合都是支持栈操作的。
单链表也是能实现栈的，通过在表的顶端插入实现栈的push压栈操作，通过删除表的顶端元素实现pop入栈操作。top操作只需要返回顶部的元素的值即可。
classLinkedStack{
privatevar first: Node? = nullprivatevar len: Int = 0funpush(value: Int) {val oldFirst = first
first = Node(value)
first?.next = oldFirst
len++
}
funpop(): Int {val value = first?.value
first = first?.next
return value ?: -1
}
funtop(): Int {
return first?.value ?: -1
}
funisEmpty(): Boolean {
return first == null
}
funsize(): Int {
return len
}
inner classNode(var value: Int) {
var next: Node? = null
}
}
复制代码2、链表实现队列结构
classLinkedQueue{
privatevar first: Node? = nullprivatevar last: Node? = nullprivatevar len: Int = 0funenqueue(value: Int) {val oldLast = last
last = Node(value)
last?.next = nullif (isEmpty()) {
first = last
} else {
oldLast?.next = last
}
len++
}
fundequeue(): Int {val value = first?.value ?: -1
first = first?.next
if (isEmpty()) {
last = null
}
return value
}
funisEmpty(): Boolean {
return first == null
}
funsize(): Int {
return len
}
inner classNode(var value: Int) {
var next: Node? = null
}
}
复制代码六、链表反转问题
链表反转(也称链表的逆序)是链表中一种比较经典的操作，在一些数据结构的题目链表的反转也是常考点，链表的反转也会做为一部分融入题目，比如回文链表问题等
- 2、实现过程
- 3、代码描述
funreverseLinkedList(head: LinkedNode?): LinkedNode? {
var prev: LinkedNode? = nullvar current: LinkedNode? = head
var next: LinkedNode? = head
while (current != null) {
next =
= prev
prev = current
current = next
}
return prev
}
复制代码七、链表中经典快慢指针问题
快慢指针追赶问题在链表中是非常经典的，快慢指针问题一般用于解决链表中间节点问题和链表是否含有环以及链表中环的入口位置等问题。
如果使用快慢指针是判断链表是否含有环的问题，我们更希望fast和slow指针的相对路程是正好是环的长度，(也就是slow指针刚进入环，而fast指针刚绕环一圈，此时两指针正好相遇)这样两个指针就相遇了。这样取每步的速度差能够被环长度整除的数字。但是我们并不知道环的具体长度，所以只能取每步的速度差能够被环长度整除的数字为1(1能被所有的数整除),所以我们取fast指针每次走2步，slow指针每次走1步，实际上只要保证两者速度差为1就可以了，你甚至可以fast每次走3步，slow指针每次走2步都是可以的，这样一来只要它们在环里面就一定能相遇。
1、快慢指针与链表环问题
publicbooleanhasCycle(ListNode head){
if(head == null || head.next == null) returnfalse;
ListNode slow = head;
ListNode fast = head;
while(fast != null && != null){
slow = slow.next;
fast = .next;if(slow == fast){returntrue;
}
}
returnfalse;
}
复制代码2、快慢指针找中间节点问题
由快慢指针追赶的原理可知，如果fast指针和slow指针同时从链表(链表不含环)的头结点出发开始遍历，如果fast指针的每次遍历步数是slow指针的两倍，那么可得到如果fast遍历到链表的尾部，那么此时的slow指针应该处于链表的中间节点位置(具体题目可参考：LeetCode第876题)。
public ListNode middleNode(ListNode head){
if(head == null) returnnull;
ListNode slow = head;
ListNode fast = head;
while(fast != null && != null){
slow = slow.next;
fast = .next;
}
return slow;
}
