网络异常，图片无法展示
|
What is a linked list？🤔
class Node(val e: E, val next: Node)
学习链表我们可以获得哪些？
- 加深引用的理解。(类似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尾指针(可以理解为一个标记)即可。
边界考虑
- 当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() } }
