每周一数据结构之链表(Kotlin描述)

2019-04-15 本文已影响1人熊喵先森

一、链表的定义

链表是一种递归的数据结构，是一种线性结构，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)，简单来说链表并不像数组那样将数组存储在一个连续的内存地址空间里，它们可以不是连续的因为他们每个节点保存着下一个节点的引用（地址）

二、链表的类型

单链表

1、定义

单链表(又称单向链表)是链表中的一种，其特点是链表的链接方向是单向的，对链表的访问要从头部(head)开始，然后依次通过next指针读取下一个节点。

2、数据结构

单链表的数据结构可以分为两部分：数据域和指针域，数据域存储数据，指针域指向下一个存储节点的地址。注意: 单向链表只可向一个方向进行遍历

image

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指针域指向下一个存储节点的地址(也即指向直接后继节点)。注意: 单向链表可向两个方向进行遍历,分别为正序和逆序遍历

image

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、数据结构

image

双向循环链表

1、定义

双向循环链表，只是在双链表的基础，它的头节点的prev指针不再为null，而是直接指向它的尾节点；它的尾节点的next指针不再为null，而是直接指向它的头节点。

2、数据结构

image

三、链表的特点

1、在内存中不是连续的内存地址空间，它只是一种逻辑上的线性连续结构。每个节点都含有指向下一个节点的next指针(可能指向下一个节点或null)
2、链表在节点的删除和增加有着很高效率，基本是O(1)常数级的时间效率，而顺序表实现删除和增加操作则是线性级O(n)的时间效率。所以一般用于用于元素节点频繁删除和增加
3、而对于链表的查找和获得第K个链表中节点，往往需要采用遍历的方式实现，所以一般需要O(n)的时间效率
4、链表长度是可变的，也就意味着在内存空间足够范围内，链表长度可以无限扩大。而顺序表则一般是固定的，当超出长度的时候则会进行扩容。

四、链表的基本操作

链表的构造

我们知道一个节点类型的变量就可以表示一条链表，只要保证对应的每个节点的next指针能够指向下一个节点即可或指向null(表示链表最后一个节点)

1、单链表的构造

image

//链表结构定义
class LinkedNode(var value: Int) {
    var next: LinkedNode? = null
}
//链表的构造
fun main(args: Array<String>) {
    val node1 = LinkedNode(value = 1)//创建节点1
    val node2 = LinkedNode(value = 2)//创建节点2
    val node3 = LinkedNode(value = 3)//创建节点3
    node1.next = node2//通过node1的next指针指向node2，把node1和node2连接起来
    node2.next = node3//通过node2的next指针指向node3，把node2和node3连接起来
}

2、双链表的构造

image

class LinkedNode(var value: Int) {
    var prev: LinkedNode? = null
    var next: LinkedNode? = null
}

fun main(args: Array<String>) {
    val node1 = LinkedNode(value = 1)//创建节点1 此时的prev,next均为null
    val node2 = LinkedNode(value = 2)//创建节点2 此时的prev,next均为null
    val node3 = LinkedNode(value = 3)//创建节点3 此时的prev,next均为null
    
    node1.next = node2 //node1的next指针指向直接后继节点node2
    node2.prev = node1 //node2的prev指针指向直接前驱节点node1
    
    node2.next = node3 //node2的next指针指向直接后继节点node3
    node3.prev = node2 //node3的prev指针指向直接前驱节点node2
}

链表表头插入节点

在链表表头插入一个节点是最简单的一种操作，一般处理方式，先创建一个oldFirst指向第一个节点，然后重新创建一个新的节点,将新节点的next指向oldFirst指向的节点，first指向新插入的节点。

1、单链表表头插入节点

image

fun insertToHead(head: LinkedNode): LinkedNode {
    var first: LinkedNode = head
    val oldFirst: LinkedNode = head
    first = LinkedNode(value = 6)
    first.next = oldFirst
    return first
}

2、双链表表头插入节点

image

fun insertToHead(head: LinkedNode): LinkedNode {
    var first: LinkedNode = head
    val oldFirst: LinkedNode = head
    first = LinkedNode(value = 6)
    oldFirst.prev = first
    first.next = oldFirst
    return first
}

在表头删除节点

1、单链表表头删除节点

image

fun deleteToHead(head: LinkedNode): LinkedNode? {
    var first: LinkedNode? = head
    first = first?.next
    return first
}

2、双链表表头删除节点

image

fun deleteToHead(head: LinkedNode): LinkedNode? {
    var first: LinkedNode? = head
    first = first?.next
    first?.prev = null
    return first
}

在表尾插入节点

1、单链表尾部插入节点

image

fun insertToTail(head: LinkedNode): LinkedNode? {
    var last = getTailNode(head) //通过遍历得到尾部节点
    val oldLast = last
    last = LinkedNode(value = 4)
    oldLast?.next = last
    return head
}

2、双链表尾部插入节点

image

fun insertToTail(head: LinkedNode): LinkedNode? {
    var last = getTailNode(head) //通过遍历得到尾部节点
    val oldLast = last
    last = LinkedNode(value = 4)
    oldLast?.next = last
    last.prev = oldLast
    return head
}

在其他位置插入节点

1、单链表其他位置插入节点

image

fun insertToOther(head: LinkedNode): LinkedNode? {
    val current = getInsertPrevNode(head) //拿到需要的插入位置的上一个节点
    val newNode = LinkedNode(value = 6)
    newNode.next = current?.next// 新插入的节点next指向插入位置的上一个节点的next
    current?.next = newNode//然后断开插入位置的上一个节点的next，并把指向新插入的节点
    return head
}

2、双链表其他位置插入节点

image

fun insertToOther(head: LinkedNode): LinkedNode? {
    val current = getInsertPrevNode(head) //拿到需要的插入位置的上一个节点
    val newNode = LinkedNode(value = 6)
    newNode.next = current?.next// 新插入的节点next指向插入位置的上一个节点的next
    newNode.prev = current //新插入的节点prev指向插入位置的上一个节点
    current?.next = newNode//然后断开插入位置的上一个节点的next，并把它指向新插入的节点
    current?.next?.prev = newNode //然后断开插入位置的上一个节点的prev,并把它指向新插入的节点
    return head
}

在其他位置删除节点

1、单链表其他位置删除节点

image

fun deleteToOther(head: LinkedNode): LinkedNode? {
    val current = getInsertPrevNode(head) //拿到需要的删除节点的上一个节点
    current?.next = current?.next?.next
    return head
}

2、双链表其他位置删除节点

image

fun deleteToOther(head: LinkedNode): LinkedNode? {
    val current = getDeletePrevNode(head) //拿到需要的删除节点的上一个节点
    current?.next = current?.next?.next
    current?.next?.prev = current
    return head
}

链表的遍历

fun traverseLinkedList(head: LinkedNode?) {
    var current = head
    while (current != null){
        println(current.value)
        current = current.next
    }
}

获取链表的大小

fun getLength(head: LinkedNode?): Int {
    var len = 0
    var current = head
    while (current != null){
        len++
        current = current.next
    }
    
    return len
}

五、链表实现栈和队列数据结构

1、链表实现栈结构

由于栈是一个表，因此任何实现表的方法都能实现栈。显然，Java中常用的ArrayList和LinkedList集合都是支持栈操作的。

实现思路

单链表也是能实现栈的，通过在表的顶端插入实现栈的push压栈操作，通过删除表的顶端元素实现pop入栈操作。top操作只需要返回顶部的元素的值即可。

实现代码

class LinkedStack {
    private var first: Node? = null
    private var len: Int = 0

    fun push(value: Int) {//相当于链表从表头插入新的元素
        val oldFirst = first
        first = Node(value)
        first?.next = oldFirst
        len++
    }

    fun pop(): Int {//相当于链表从表头删除新的元素
        val value = first?.value
        first = first?.next
        return value ?: -1
    }

    fun top(): Int {
        return first?.value ?: -1
    }

    fun isEmpty(): Boolean {
        return first == null
    }

    fun size(): Int {
        return len
    }

    inner class Node(var value: Int) {
        var next: Node? = null
    }
}

2、链表实现队列结构

class LinkedQueue {
    private var first: Node? = null
    private var last: Node? = null
    private var len: Int = 0

    fun enqueue(value: Int) {//相当于链表从尾部插入新的节点
        val oldLast = last
        last = Node(value)
        last?.next = null
        if (isEmpty()) {
            first = last
        } else {
            oldLast?.next = last
        }
        len++
    }

    fun dequeue(): Int {//相当于链表从尾部删除最后节点
        val value = first?.value ?: -1
        first = first?.next
        if (isEmpty()) {
            last = null
        }
        return value
    }

    fun isEmpty(): Boolean {
        return first == null
    }

    fun size(): Int {
        return len
    }

    inner class Node(var value: Int) {
        var next: Node? = null
    }
}

六、链表反转问题

1、定义

链表反转(也称链表的逆序)是链表中一种比较经典的操作，在一些数据结构的题目链表的反转也是常考点，链表的反转也会做为一部分融入题目，比如回文链表问题等

2、实现过程

image
3、代码描述

fun reverseLinkedList(head: LinkedNode?): LinkedNode? {
    var prev: LinkedNode? = null
    var current: LinkedNode? = head
    var next: LinkedNode? = head

    while (current != null) {
        next = current.next
        current.next = prev
        prev = current
        current = next
    }
    
    return prev
}

七、链表中经典快慢指针问题

快慢指针追赶问题在链表中是非常经典的，快慢指针问题一般用于解决链表中间节点问题和链表是否含有环以及链表中环的入口位置等问题。

如果使用快慢指针是判断链表是否含有环的问题，我们更希望fast和slow指针的相对路程是正好是环的长度，(也就是slow指针刚进入环，而fast指针刚绕环一圈，此时两指针正好相遇)这样两个指针就相遇了。这样取每步的速度差能够被环长度整除的数字。但是我们并不知道环的具体长度，所以只能取每步的速度差能够被环长度整除的数字为1(1能被所有的数整除),所以我们取fast指针每次走2步，slow指针每次走1步，实际上只要保证两者速度差为1就可以了，你甚至可以fast每次走3步，slow指针每次走2步都是可以的，这样一来只要它们在环里面就一定能相遇。

1、快慢指针与链表环问题

    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) return false;
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;//慢指针每次走1步
            fast = fast.next.next;//快指针每次走2步
            if(slow == fast){//如果链表存在环，那么slow和fast指针会相遇
                return true;
            }
        }
        
        return false;
    }

2、快慢指针找中间节点问题

由快慢指针追赶的原理可知，如果fast指针和slow指针同时从链表(链表不含环)的头结点出发开始遍历，如果fast指针的每次遍历步数是slow指针的两倍，那么可得到如果fast遍历到链表的尾部，那么此时的slow指针应该处于链表的中间节点位置(具体题目可参考：LeetCode第876题)。

    public ListNode middleNode(ListNode head) {
        if(head == null) return null;
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        
        return slow;
    }