链表数据结构的定义和类型、操作……Kotlin语言示例

2019年5月11日06:03:46 发表评论 28 views

一、链表的定义

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

二、链表的类型

单链表

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

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

链表数据结构的定义和类型、操作......Kotlin语言示例
classLinkedNode(var value: Int) {
    var next: LinkedNode? = null
}
复制代码
publicclassLinkedNode{
    int value;
    LinkedNode next; publicLinkedNode(int value){
        this.value = value;
    }
}
复制代码

双链表

双链表(又称双向链表),是链表中一种,与单链表不同的是它的每个节点都有两个指针,分别指向直接后继节点直接前驱节点;所以,从双链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。

双链表的数据结构可以分为三部分:prev指针域、数据域和next指针域,prev指针域指向上一个存储节点的地址(也即指向直接前驱节点),数据域存储数据,next指针域指向下一个存储节点的地址(也即指向直接后继节点)。注意: 单向链表可向两个方向进行遍历,分别为正序和逆序遍历

链表数据结构的定义和类型、操作......Kotlin语言示例
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而是指向头结点,形成一个环。并且在节点结构上和单链表是一样的。因此,从单向循环链表中的任何一个结点出发都能找到任何其他结点。

链表数据结构的定义和类型、操作......Kotlin语言示例

双向循环链表

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

链表数据结构的定义和类型、操作......Kotlin语言示例

三、链表的特点

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

四、链表的基本操作

链表的构造

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

链表数据结构的定义和类型、操作......Kotlin语言示例
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
}
复制代码
链表数据结构的定义和类型、操作......Kotlin语言示例
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指向新插入的节点。

链表数据结构的定义和类型、操作......Kotlin语言示例
funinsertToHead(head: LinkedNode): LinkedNode {
    var first: LinkedNode = head
    val oldFirst: LinkedNode = head
    first = LinkedNode(value = 6)
    first.next = oldFirst
    return first
}
复制代码
链表数据结构的定义和类型、操作......Kotlin语言示例
funinsertToHead(head: LinkedNode): LinkedNode {
    var first: LinkedNode = head
    val oldFirst: LinkedNode = head
    first = LinkedNode(value = 6)
    oldFirst.prev = first
    first.next = oldFirst
    return first
}
复制代码

在表头删除节点

链表数据结构的定义和类型、操作......Kotlin语言示例
fundeleteToHead(head: LinkedNode): LinkedNode? {
    var first: LinkedNode? = head
    first = first?.next
    return first
}
复制代码
链表数据结构的定义和类型、操作......Kotlin语言示例
fundeleteToHead(head: LinkedNode): LinkedNode? {
    var first: LinkedNode? = head
    first = first?.next
    first?.prev = nullreturn first
}
复制代码

在表尾插入节点

链表数据结构的定义和类型、操作......Kotlin语言示例
funinsertToTail(head: LinkedNode): LinkedNode? {
    var last = getTailNode(head) val oldLast = last
    last = LinkedNode(value = 4)
    oldLast?.next = last
    return head
}
复制代码
链表数据结构的定义和类型、操作......Kotlin语言示例
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
}
复制代码
链表数据结构的定义和类型、操作......Kotlin语言示例
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
}
复制代码

在其他位置删除节点

链表数据结构的定义和类型、操作......Kotlin语言示例
fundeleteToOther(head: LinkedNode): LinkedNode? {
    val current = getInsertPrevNode(head) 
    current?.next = current?.next?.next
    return head
}
复制代码
链表数据结构的定义和类型、操作......Kotlin语言示例
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、实现过程
    链表数据结构的定义和类型、操作......Kotlin语言示例
  • 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;
    }

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: