重学数据结构-链表

image-20200830093107764

What is a linked list？🤔

  • 不同于栈与队列及动态数组，它是真正意义上最简单的动态数据结构。

  • 优点：真正的动态，不需要处理固定容量的问题

  • 缺点：丧失了随机访问的能力

  • 数据存储在 “节点”（Node）中

    class Node(val e: E, val next: Node)
image-20200829211246140

学习链表我们可以获得哪些？

  • 加深引用的理解。(类似C语言的指针)
  • 链表内部也有递归结构的性质
  • 便于对其他数据结构的辅助

实现单向链表

如何实现一个单向链表呢？

很简单，链表不像数组那样，不需要我们主动扩容，我们只需要类似递归一样，一层套一层即可，即node1持有node2的引用，node2持有node3....，相应的每次插入我们只需要更改头结点即可，当node-x持有的下一个node引用为null时，我们也可以判定，此时为链表尾节点。

class LinkedList<E> {
    private var size = 0
    //头结点
    private var head: Node<E>? = null

    private class Node<E>(var e: E? = null, var next: Node<E>? = null) {
        override fun toString(): String {
            return e?.toString() ?: ""
        }
    }


    fun addFirst(e: E) {
//        val node = Node(e)
//        node.next = head
//        head = node
        //简化版添加首元素
        head = Node(e, head)
        ++size
    }
    

    /** 移除头节点元素 O(1) */
    fun removeFirst() {
        if (head == null) throw RuntimeException("nodeFirst != null!!")
        val node = head?.next
        head?.e = null
        head = node
        --size
    }

    /** 在链表指定位置添加元素 */
    fun addIndexed(index: Int, e: E) {
        if (index > size || index < 0) throw RuntimeException("指定位置长度不得超过现有链表长度")
        if (size == 0) {
            addFirst(e)
        } else {
            var node = head
            var sum = 0
            while (node != null) {
                if (sum++ == index - 1) {
                    node.next = Node(e, node.next)
                    ++size
                    return
                }
                node = node.next
            }
        }
    }

    /** 尾结点添加 */
    fun addLast(e: E) {
        addIndexed(size, e)
    }

    /** 返回链表是否为null  */
    private fun isEmpty(): Boolean {
        return size == 0
    }

    override fun toString(): String {
        val stringBuilder = StringBuilder("开始--- [")
        if (head?.e != null)
            stringBuilder.append("${head?.e},")
        var next = head?.next
        while (next != null) {
            stringBuilder.append("${next.e},")
            next = next.next
        }
        if (head?.e != null) {
            stringBuilder.deleteCharAt(stringBuilder.length - 1)
        }
        return stringBuilder.append("]--- 结束").toString()
    }
}

为链表增加增删改查

在上述的实现里，我们在添加节点时，每次都需要考虑链表为null的情况，对于这种状态下，我们可以考虑引入一个虚拟节点，这样我们每次遍历添加时就可以不用 index-1，即无需考虑前一个节点的情况，而且我们还可以考虑加入 删除，修改，和根据位置查找。

class LinkedList<E> {
    private var size = 0

    //虚拟头结点
    private var dummyHead: Node<E> = Node(null, null)

    private class Node<E>(var e: E? = null, var next: Node<E>? = null) {
        override fun toString(): String {
            return e?.toString() ?: ""
        }
    }
    
    /** 添加链表头元素 */
    fun addFirst(e: E) {
        addIndexed(0, e)
    }

    /** 移除链表头 O(1)*/
    fun removeFirst(): E? {
        return removeIndexed(0)
    }

    /** 移除链表尾 0(n) */
    fun removeLast(): E? {
        return removeIndexed(size - 1)
    }

    /** 删除指定位置下标元素 */
    fun removeIndexed(index: Int): E? {
        if (index > size || index < 0) throw RuntimeException("指定位置长度不得超过现有链表长度")
        var node = dummyHead
        //找到待删除节点之前的节点
        (0 until index).forEach { _ ->
            node.next?.let {
                node = it
            }
        }
        val retNode = node.next
        node.next = retNode?.next
        retNode?.next = null
        --size
        return retNode?.e
    }


    /** 在链表指定位置添加元素 */
    fun addIndexed(index: Int, e: E) {
        if (index > size || index < 0) throw RuntimeException("指定位置长度不得超过现有链表长度")
        var node = dummyHead
        (0 until index).forEach { _ ->
            node.next?.let {
                node = it
            }
        }
        node.next = Node(e, node.next)
        ++size
        return
    }

    /** 尾结点添加 */
    fun addLast(e: E) {
        addIndexed(size, e)
    }

    /** 返回链表是否为null  */
    fun isEmpty(): Boolean {
        return size == 0
    }
    
    /** 获取指定位置元素 */
    fun get(index: Int): E? {
        if (index > size || index < 0) throw RuntimeException("指定位置长度不得超过现有链表长度")
        var cur = dummyHead.next
        (0 until index).forEach { _ ->
            cur = cur?.next
        }
        return cur?.e
    }

    /** 获取首元素 */
    fun getFirst(): E {
        return get(0)
    }

    /** 获取尾元素 */
    fun getLast(): E {
        return get(size - 1)
    }

    /** 更新指定位置e */
    fun set(index: Int, e: E) {
        if (index > size || index < 0) throw RuntimeException("指定位置长度不得超过现有链表长度")
        var node = dummyHead.next
        (0 until index).forEach { _ ->
            node = node?.next
        }
        node?.e = e
    }

    /** 判断是否存在指定元素 */
    fun contains(e: E): Boolean {
        var node = dummyHead.next
        while (node != null) {
            if (node.e === e)
                return true
            node = node.next
        }
        return false
    }

    override fun toString(): String {
        val stringBuilder = StringBuilder("开始--- [")
        var next = dummyHead.next
        while (next != null) {
            stringBuilder.append("${next.e},")
            next = next.next
        }
        if (size > 0) {
            stringBuilder.deleteCharAt(stringBuilder.length - 1)
        }
        return stringBuilder.append("]--- 结束").toString()
    }
}

链表复杂度分析

  • 增 O(n)
  • 删 O(n)
  • 改 O(n)
  • 查 O(n)

上述如果都是对于链表头进行操作，那么相应的效率都为O(1)

使用链表实现栈

使用链表实现栈非常简单，因为栈是先进后出，所以我们直接可以利用链表实现，而且相应的效率都为O(1) ,此时指的只是移除栈底，添加表头元素。

interface Stack<E> {
    fun getSize(): Int
    fun isEmpty(): Boolean
    fun pop(): E?
    fun peek(): E?
    fun push(e: E)
}

class LinkedListStack<E> : Stack<E> {

    private val linkedList by lazy {
        LinkedList<E>()
    }

    override fun getSize(): Int {
        return linkedList.getSize()
    }

    override fun isEmpty(): Boolean {
        return linkedList.isEmpty()
    }

    override fun pop(): E? {
        return linkedList.removeFirst()
    }

    override fun peek(): E {
        return linkedList.getFirst()
    }

    override fun toString(): String {
        val res = StringBuilder()
        res.append("Stack:Pop-")
        res.append(linkedList)
        return res.toString()

    }

    override fun push(e: E) {
        linkedList.addFirst(e)
    }
}

使用链表实现队列(带有尾指针的链表)

对于链表来说，因为我们有head这样的头指针，所以对于表头的插入和删除都是非常容易，如果我们要使用链表实现队列，那么我们就需要再增加一个tail尾指针(可以理解为一个标记)即可。

image-20200829211503994

边界考虑

  • 当tail 为null,那么就证明链表此时为null,所以此时我们需要初始化tail节点，并相应的重置head指针
  • 当我们移除元素时，如果head为null,则链表此时为null,同样需要更新tail指针
interface Queue<E> {
    fun enqueue(e: E)
    fun dequeue(): E?
    fun getFront(): E?
    fun getSize(): Int
    fun isEmpty(): Boolean
}

class LinkedListQueue<E> : Queue<E> {

    private var size = 0
    private var head: Node<E>? = null
    private var tail: Node<E>? = null

    private class Node<E>(var e: E? = null, var next: Node<E>? = null) {
        override fun toString(): String {
            return e?.toString() ?: ""
        }
    }

    override fun enqueue(e: E) {
        tail?.let {
            tail?.next = Node(e)
            tail = tail?.next
        } ?: tailNull(e)
        ++size
    }

    private fun tailNull(e: E) {
        tail = Node(e)
        head = tail
    }

    override fun dequeue(): E? {
        if (head == null) throw NullPointerException("head !=null!!")
        val node = head
        head = head?.next
        node?.next = null
        --size
        if (head == null) tail = null
        return node?.e
    }

    override fun getFront(): E? {
        if (head == null) throw NullPointerException("head !=null!!")
        return head?.e
    }

    override fun getSize(): Int {
        return size
    }

    override fun isEmpty(): Boolean {
        return size == 0
    }

    override fun toString(): String {
        val stringBuilder = StringBuilder("开始--- [")
        var next = head
        while (next != null) {
            stringBuilder.append("${next.e},")
            next = next.next
        }
        if (size > 0) {
            stringBuilder.deleteCharAt(stringBuilder.length - 1)
        }
        return stringBuilder.append("]--- 结束").toString()
    }
}

参考视频：慕课网liuyubobobo

我是 Petterp ,如果你觉得我的文章对你有所帮助，欢迎点赞👏 ，如果有任何想法和问题，随时欢迎评论区一起讨论。👨‍💻‍

©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 212,657评论 6赞 492
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,662评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 158,143评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,732评论 1赞 284
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,837评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,036评论 1赞 291
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,126评论 3赞 410
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,868评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,315评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,641评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,773评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,470评论 4赞 333
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,126评论 3赞 317
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,859评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,095评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,584评论 2赞 362
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,676评论 2赞 351