首页 安卓& Kotlin Books 数据结构&Kotlin的算法

3
链接名单 由Matei Suica,Kelvin Lau和Vincent Ngo撰写

链接名单 is a collection of values arranged in a linear, unidirectional sequence. A linked list has several theoretical advantages over contiguous storage options such as the Kotlin Array or ArrayList:

  • 恒定的时间插入和从列表前部移除。
  • 可靠的性能特征。

链接名单
链接名单

随图所示,链接列表是一系列 节点。节点有两项职责:

  1. 保持一个值。
  2. Hold a reference to the next node. The absence of a reference to the next node, null, marks the end of the list.

保持值12的节点
保持值12的节点

在本章中,您将实现链接列表并了解与其关联的公共操作。您还将了解每个操作的时间复杂性。为本章打开Starter项目,以便您可以潜入代码。

节点

创建一个新的kotlin文件 SRC. 并命名它 node.kt.。将以下内容添加到文件中:

data class Node<T>(var value: T, var next: Node<T>? = null) {
  override fun toString(): String {
    return if (next != null) {
      "$value -> ${next.toString()}"
    } else {
      "$value"
    }
  }
}

导航到 main.kt. file and add the following inside main():

fun main() {
  "creating and linking nodes" example {
    val node1 = Node(value = 1)
    val node2 = Node(value = 2)
    val node3 = Node(value = 3)

    node1.next = node2
    node2.next = node3

    println(node1)
  }
}

您刚刚创建了三个节点并连接了它们:

包含值1,2和3的链接列表
包含值1,2和3的链接列表

Once you run main.kt., you’ll see the following output in the console:

---Example of creating and linking nodes---
1 -> 2 -> 3

As far as practicality goes, this method of building lists is far from ideal. You can easily see that building long lists in this way is impractical. A common way to alleviate this problem is to build a linkedlist. that manages the 节点 objects. You’ll do just that!

linkedlist.

SRC.,创建一个新文件并命名它 linkedlist.kt.。将以下内容添加到文件中:

class LinkedList<T> {

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

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

  override fun toString(): String {
    if (isEmpty()) {
      return "Empty list"
    } else {
      return head.toString()
    }
  }
}

链接列表具有a的概念 尾巴,这分别是指列表的第一个和最后一个节点:

列表的头部和尾部
列表的头部和尾部

You’ll also keep track of the size of the linked list in the size property. This might not seem useful yet, but it will come in handy later.

将值添加到列表中

Next, you’re going to provide an interface to manage the 节点 objects. You’ll first take care of adding values. There are three ways to add values to a linked list, each having their own unique performance characteristics:

  1. push:在列表前面添加一个值。
  2. append:在列表末尾添加一个值。
  3. insert:在列表的特定节点后添加值。

您将依次实现这些中的每一个并分析它们的性能特征。

推动操作

Adding a value at the front of the list is known as a push operation. This is also known as 首先插入。这个代码非常简单。

Add the following method to linkedlist.:

fun push(value: T) {
  head = Node(value = value, next = head)
  if (tail == null) {
    tail = head
  }
  size++
}

在 the case in which you’re pushing into an empty list, the new node is both the 尾巴 of the list. Since the list now has a new node, you increment the value of size.

main.kt., add the following in main():

"push" example {
  val list = LinkedList<Int>()
  list.push(3)
  list.push(2)
  list.push(1)

  println(list)
}

您的控制台输出将显示:

---Example of push---
1 -> 2 -> 3

这很酷,但你可以做得更好。你会用这件事 流利的界面 pattern to chain multiple push calls. Go back to push() 和 add linkedlist.<T> as its return type. Then, add a return this line at the end to return the list that you’ve just pushed an element into.

该方法现在看起来像这样:

fun push(value: T): LinkedList<T> {
  head = Node(value = value, next = head)
  if (tail == null) {
    tail = head
  }
  size++
  return this
}

main(), you can now rewrite the previous example, making use of push()’s return value:

"流利的界面 push" example {
  val list = LinkedList<Int>()
  list.push(3).push(2).push(1)
  println(list)
}

这还差不多!现在,您可以轻松地将多个元素添加到列表的开始。

追加操作

The next operation you’ll look at is append. This adds a value at the end of the list, which is known as 尾端插入.

linkedlist.kt., add the following code just below push():

fun append(value: T) {
  // 1
  if (isEmpty()) {
    push(value)
    return
  }
  // 2
  tail?.next = Node(value = value)

  // 3
  tail = tail?.next
  size++
}

此代码相对简单:

  1. Like before, if the list is empty, you’ll need to update both 尾巴 to the new node. Since append on an empty list is functionally identical to push, you invoke push to do the work for you.
  2. 在所有其他情况下,您都会创建一个新节点 the current 尾巴 node. 尾巴 will never be null 这里 because you’ve already handled the case where the list is empty in the if statement.
  3. 由于这是尾端插入,因此您的新节点也是列表的尾部。

回到 main.kt. 和 write the following at the bottom of main():

"append" example {
  val list = LinkedList<Int>()
  list.append(1)
  list.append(2)
  list.append(3)

  println(list)
}

您将看到控制台中的以下输出:

---Example of append---
1 -> 2 -> 3

You can use the trick you learned for push() to get a fluid interface here too. It’s up to you if you’ve liked it or not but imagine how you could chain pushes and appends in a world of endless possibilities. Or just have some fun with it. :]

插入操作

The third and final operation for adding values is insert(afterNode: Node<T>). This operation inserts a value at a particular place in the list and requires two steps:

  1. 在列表中查找特定节点。
  2. 在该节点后插入新节点。

首先,您将实现代码以查找要插入值的节点。

linkedlist.kt., add the following code just below append:

fun nodeAt(index: Int): Node<T>? {
  // 1
  var currentNode = head
  var currentIndex = 0

  // 2
  while (currentNode != null && currentIndex < index) {
    currentNode = currentNode.next
    currentIndex++
  }

  return currentNode
}

nodeAt() 尝试根据给定索引检索列表中的节点。由于您只能从头节点访问列表的节点,因此您必须进行迭代遍历。这是游戏:

  1. You create a new reference to 和 keep track of the current number of traversals.

  2. Using a while loop, you move the reference down the list until you reach the desired index. Empty lists or out-of-bounds indexes will result in a null return value.

现在,您需要插入新节点。

Add the following method just below nodeAt():

fun insert(value: T, afterNode: Node<T>): Node<T> {
  // 1
  if (tail == afterNode) {
    append(value)
    return tail!!
  }
  // 2
  val newNode = Node(value = value, next = afterNode.next)
  // 3
  afterNode.next = newNode
  size++
  return newNode
}

这是你所做的:

  1. 在 the case where this method is called with the 尾巴 node, you call the functionally equivalent append method. This takes care of updating 尾巴.
  2. Otherwise, you create a new node and link its next property to the next node of the list.
  3. You reassign the next value of the specified node to link it to the new node that you just created.

要测试东西,回去 main.kt. 和 add the following to the bottom of main():

"inserting at a particular index" example {
  val list = LinkedList<Int>()
  list.push(3)
  list.push(2)
  list.push(1)

  println("Before inserting: $list")
  var middleNode = list.nodeAt(1)!!
  for (i in 1..3) {
    middleNode = list.insert(-1 * i, middleNode)
  }
  println("After inserting: $list")
}

您将看到以下输出:

---Example of inserting at a particular index---
Before inserting: 1 -> 2 -> 3
After inserting: 1 -> 2 -> -1 -> -2 -> -3 -> 3

绩效分析

哇!到目前为止你进步了。要回顾,您已实现将值添加到链接列表的三个操作以及在特定索引处找到节点的方法。

接下来,您将专注于相反的操作:删除操作。

从列表中删除值

删除节点有三个主要操作:

  1. 流行音乐:删除列表前面的值。
  2. 去掉Last:删除列表末尾的值。
  3. 去掉After:删除列表中的任何位置的值。

您将实现所有三个并分析其性能特征。

流行运营

删除列表前面的值通常被称为 流行音乐. This operation is almost as simple as push(), so dive right in.

Add the following method to linkedlist.:

fun pop(): T? {
  if (!isEmpty()) size--
  val result = head?.value
  head = head?.next
  if (isEmpty()) {
    tail = null
  }

  return result
}

流行音乐() 返回从列表中删除的值。此值是可选的,因为列表可能为空。

By moving the down a node, you’ve effectively removed the first node of the list. The garbage collector will remove the old node from memory once the method finishes since there will be no more references attached to it. If the list becomes empty, you set 尾巴 to null as well.

测试,去 main.kt. 和 add the following code at the bottom inside main():

"流行音乐" example {
  val list = LinkedList<Int>()
  list.push(3)
  list.push(2)
  list.push(1)

  println("Before popping list: $list")
  val poppedValue = list.pop()
  println("After popping list: $list")
  println("Popped value: $poppedValue")
}

您将看到以下输出:

---Example of pop---
Before popping list: 1 -> 2 -> 3
After popping list: 2 -> 3
Popped value: 1

去掉last操作

删除列表的最后一个节点有点不方便。

Although you have a reference to the 尾巴 node, you can’t chop it off without having a reference to the node before it. Thus, you need to traverse the whole list to find the node before the last.

Add the following code just below 流行音乐():

fun removeLast(): T? {
  // 1
  val head = head ?: return null
  // 2
  if (head.next == null) return pop()
  // 3
  size--

  // 4
  var prev = head
  var current = head

  var next = current.next
  while (next != null) {
    prev = current
    current = next
    next = current.next
  }
  // 5
  prev.next = null
  tail = prev
  return current.value
}

这是发生的事情:

  1. If is null, there’s nothing to remove, so you return null.
  2. If the list only consists of one node, 去掉Last is functionally equivalent to 流行音乐. Since 流行音乐 will handle updating the 尾巴 references, you can delegate this work to the 流行音乐 function.
  3. 此时,您知道您将删除一个节点,因此您可以更新列表的大小相应。
  4. You keep searching for the next node until current.next is null. This signifies that current is the last node of the list.
  5. Since current is the last node, you disconnect it using the prev.next reference. You also make sure to update the 尾巴 reference.

回到 main.kt., and in main(), add the following to the bottom:

"removing the last node" example {
  val list = LinkedList<Int>()
  list.push(3)
  list.push(2)
  list.push(1)

  println("Before removing last node: $list")
  val removedValue = list.removeLast()

  println("After removing last node: $list")
  println("Removed value: $removedValue")
}

您将在控制台底部看到以下内容:

---Example of removing the last node---
Before removing last node: 1 -> 2 -> 3
After removing last node: 1 -> 2
Removed value: 3

去掉Last() 要求您遍历列表。这是一个 O(n) 操作,相对昂贵。

删除操作

The final remove operation is removing a node at a particular point in the list. This is achieved much like insert(). You’ll first find the node immediately before the node you wish to remove and then unlink it.

删除中间节点
删除中间节点

导航回来 linkedlist.kt. 和 add the following method below 去掉Last():

fun removeAfter(node: Node<T>): T? {
  val result = node.next?.value

  if (node.next == tail) {
    tail = node
  }

  if (node.next != null) {
    size--
  }

  node.next = node.next?.next
  return result
}

Special care needs to be taken if the removed node is the tail node since the 尾巴 reference will need to be updated.

Now, add the following example to main() to test 去掉After(). You know the drill:

"removing a node after a particular node" example {
  val list = LinkedList<Int>()
  list.push(3)
  list.push(2)
  list.push(1)

  println("Before removing at particular index: $list")
  val index = 1
  val node = list.nodeAt(index - 1)!!
  val removedValue = list.removeAfter(node)

  println("After removing at index $index: $list")
  println("Removed value: $removedValue")
}

您将看到控制台中的以下输出:

---Example of removing a node after a particular node---
Before removing at particular index: 1 -> 2 -> 3
After removing at index 1: 1 -> 3
Removed value: 2

Try adding more elements and play around with the value of the index. Similar to insert(), the time complexity of this operation is O(1),但它要求您预先对特定节点引用。

绩效分析

你打了另一个检查点。要回顾,您已经实现了从链接列表中删除值的三个操作:

此时,您已经为链接列表定义了一个接口,即世界各地的大多数程序员都可以联系到。但是,有工作要做,以装饰Kotlin语义。在本章的未来一章中,您将专注于使界面更加贴近惯性Kotlin。

kotlin.收集界面

Kotlin标准库具有一组接口,有助于定义特定类型的预期。这些接口中的每一个都提供了某些关于特性和性能的保证。在这些接口中,四个被称为 收集界面.

以下是每个接口所代表的一个小样本:

  • 1,迭代: An iterable type provides sequential access to its elements via an Iterator.

  • 2,收藏:集合类型是可迭代类型,提供其他功能,允许您检查集合是否包含特定元素或元素集合。

  • 第3层,可变的: Provides a MutableIterator, which allows items to be removed from the given collection.

  • 第4层,umablecollection: Unlike a simple Collection, a MutableCollection interface provides methods to alter the collection. For example, you can 添加去掉 元素,甚至 清除 整个系列。

这些中的每一个都有更多。当您需要遵守它们时,您将更多地了解它们中的每一个。

链接名单 can get to the tier 4 of the 收集界面. Since a linked list is a chain of nodes, adopting the Iterable interface makes sense. And because you’ve already implemented adding elements and removing them, it’s pretty clear we can go all the way to the MutableCollection interface.

成为一个kotlin可变的集合

在 this section, you’ll look into implementing the MutableCollection interface. A mutable collection type is a finite sequence and provides nondestructive sequential access but also allows you to modify the collection.

通过元素迭代

Reaching Tier 1 means implementing Iterable in the linkedlist.. To make things easier, first make reading the size available outside the class. Modify the size property in linkedlist.kt.,使财产本身是公开的,但其甲板仍然是私人:

var size = 0
  private set

Then, add the Iterable interface to the class definition. The definition will now look like:

class LinkedList<T> : Iterable<T> {
  ...
}

This means that you’re now required to add the following method to fulfill the Iterable interface:

override fun iterator(): Iterator<T> {
  return LinkedListIterator(this)
}

Right now, the compiler complains because it doesn’t know what a linkedlist.Iterator is. Create a class named linkedlist.Iterator 和 make it implement the Iterator interface:

class LinkedListIterator<T> : Iterator<T> {
  override fun next(): T {
    TODO("not implemented")
  }
  override fun hasNext(): Boolean {
    TODO("not implemented")
  }
}

要遍历链接列表,您需要参考列表。将此参数添加到构造函数:

class LinkedListIterator<T>(
  private val list: LinkedList<T>
) : Iterator<T> {
  ...
}

You can now start implementing the required methods, starting with the easier one, hasNext(). This method indicates whether your Iterable still has values to read. You’ll need to keep track of the position that the iterator has in the collection, so create an index field:

private var index = 0

然后,您可以轻松检查您处于的位置是否小于节点的总数:

override fun hasNext(): Boolean {
  return index < list.size
}

For next(), the one that reads the values of the nodes, you can use another property to help you out. You’ll want to keep track of the last node, so you can easily find the next one:

private var lastNode: Node<T>? = null

The next() function looks like:

override fun next(): T {
  // 1
  if (index >= list.size) throw IndexOutOfBoundsException()
  // 2
  lastNode = if (index == 0) {
    list.nodeAt(0)
  } else {
    lastNode?.next
  }
  // 3
  index++
  return lastNode!!.value
}

以下是此功能的关键位,逐步:

  1. You check that there are still elements to return. If there aren’t, you throw an exception. This should never be the case if clients use the Iterator correctly, always checking with hasNext() before trying to read a value from it with next().
  2. If this is the first iteration, there is no lastNode set, so you take the first node of the list. After the first iteration, you can get the next property of the last node to find the next one.
  3. Since the lastNode property was updated, you need to update the index too. You’ve now gone through one more iteration, so the index increments.

Now that you’ve implemented Iterator, you can do some really cool things. For example, you can iterate your linked list with a regular Kotlin for loop and print the double of each element in a list.

Add this to main():

"printing doubles" example {
  val list = LinkedList<Int>()
  list.push(3)
  list.push(2)
  list.push(1)
  println(list)

  for (item in list) {
    println("Double: ${item * 2}")
  }
}

你会得到的输出是:

---Example of printing doubles---
1 -> 2 -> 3
Double: 2
Double: 4
Double: 6

Cool, huh? A for loop helps you a lot but there are still things to implement if you want to have a fully featured MutableCollection.

成为一个集合

Being a Collection requires more than just being an Iterable class. Change the definition of your linkedlist. to implement Collection:

class LinkedList<T> : Iterable<T>, Collection<T>  {
  ...
}

Of course, you could now remove Iterable because a Collection is an Iterable anyway. You may also leave it there so that you can see the progress you’re making.

The compiler will start complaining about the methods you need to implement. Here are some quick wins: You already have isEmpty()size, so you can add the override keyword in front of them.

override var size = 0
  private set

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

您仍然需要实现另外两种方法,但好消息是您可以使用一个轻松实现其他方法:

override fun contains(element: T): Boolean {
  TODO("not implemented")
}

override fun containsAll(elements: Collection<T>): Boolean {
  TODO("not implemented")
}

Since you can now iterate through the list with for, the implementation of contains is straightforward:

override fun contains(element: T): Boolean {
  for (item in this) {
    if (item == element) return true
  }
  return false
}

如果需要,此方法通过列表的所有元素迭代,因此它具有复杂性 O(n)。

第二种方法类似;它只是适用于一系列元素。

override fun containsAll(elements: Collection<T>): Boolean {
  for (searched in elements) {
    if (!contains(searched)) return false
  }
  return true
}

正如你可能猜到的那样,这是一种效率低下的方法,它是 O(n^2)。 But if the Collection interface requires it, you need to provide it.

迭代时突变

To get to the 3rd tier, you need to make linkedlist. a MutableIterable. If you add this interface to the list that linkedlist. implements, you’ll see the compiler complain again because iterator() doesn’t return a MutableIterator. This time, start the other way around. Make linkedlist.Iterator implement the MutableIterator<T> interface:

class LinkedListIterator<T>(
  private val list: LinkedList<T>
) : Iterator<T>, MutableIterator<T> {
  ...
}

Again, MutableIterator is a broader interface than Iterator, so you can remove Iterator from the list of implemented interfaces.

You’ll need to add the 去掉() method to comply with the new interface you’ve added:

override fun remove() {
  // 1
  if (index == 1) {
    list.pop()
  } else {
    // 2
    val prevNode = list.nodeAt(index - 2) ?: return
    // 3
    list.removeAfter(prevNode)
    lastNode = prevNode
  }
  index--
}

Here’s a breakdown of how this code uses the methods linkedlist. already has:

  1. The simplest case is when you’re at the beginning of the list. Using 流行音乐() will do the trick.
  2. 如果迭代器位于列表中的某个位置,则需要查找上一个节点。这是从链接列表中删除项目的唯一方法。
  3. The iterator needs to step back so that next() returns the correct method the next time. This means reassigning the lastNode 和 decreasing the index.

现在,去 linkedlist.kt. 和 add MutableIterable to the class definition:

class LinkedList<T>: Iterable<T>, Collection<T>, MutableIterable<T>  {
  ...
}

Modify iterator() to return a MutableIterator, which linkedlist.Iterator implements:

override fun iterator(): MutableIterator<T> {
  return LinkedListIterator(this)
}

最后一步:可变集合

You’ve already completed the hardest steps, so this last step shouldn’t be too bad. First, add the MutableCollection interface to the definition of linkedlist.:

class LinkedList<T>: Iterable<T>, Collection<T>, MutableIterable<T>, MutableCollection<T>  {
  ...
}

这将使您添加六种方法:

override fun add(element: T): Boolean {
  TODO("not implemented")
}

override fun addAll(elements: Collection<T>): Boolean {
  TODO("not implemented")
}

override fun clear() {
  TODO("not implemented")
}

override fun remove(element: T): Boolean {
  TODO("not implemented")
}

override fun removeAll(elements: Collection<T>): Boolean {
  TODO("not implemented")
}

override fun retainAll(elements: Collection<T>): Boolean {
  TODO("not implemented")
}

Three of them are relatively simple to implement. 添加(), 添加All()清除() are almost one-liners:

override fun add(element: T): Boolean {
  append(element)
  return true
}

override fun addAll(elements: Collection<T>): Boolean {
  for (element in elements) {
    append(element)
  }
  return true
}

override fun clear() {
  head = null
  tail = null
  size = 0
}

Since the linkedlist. doesn’t have a fixed size, 添加()添加All() are always successful and need to return true. For the removal of elements, you’ll use a different approach for iterating through your MutableIterable linked list. This way, you can benefit from your MutableIterator:

override fun remove(element: T): Boolean {
  // 1
  val iterator = iterator()
  // 2
  while (iterator.hasNext()) {
    val item = iterator.next()
    // 3
    if (item == element) {
      iterator.remove()
      return true
    }
  }
  // 4
  return false
}

这种方法是一个小复合体,所以这是一步一步的演练:

  1. 获取一个迭代器,可以帮助您迭代集合。
  2. 创建一个循环检查是否有剩余的任何元素,并获取下一个元素。
  3. 检查当前元素是否是您要查找的元素,如果是,请删除它。
  4. 如果已删除元素,则返回一个发信号的布尔值。

With 去掉All(), you can make use of 去掉():

override fun removeAll(elements: Collection<T>): Boolean {
  var result = false
  for (item in elements) {
    result = remove(item) || result
  }
  return result
}

The return value of 去掉All is true if any elements were removed.

The last method to implement is retainAll(), which should remove any elements in the list besides the ones passed in as the parameter. You’ll need to approach this the other way around. Iterate through your list once and remove any element that is not in the parameter. Luckily, the parameter of retainAll is also a collection, so you can use all of the methods you implemented yourself, like contains:

override fun retainAll(elements: Collection<T>): Boolean {
  var result = false
  val iterator = this.iterator()
  while (iterator.hasNext()) {
    val item = iterator.next()
    if (!elements.contains(item)) {
      iterator.remove()
      result = true
    }
  }
  return result
}

恭喜!你完成了实现,所以现在是一些测试的时候了。回到里面 main.kt. 和 add these at the end of main():

"removing elements" example {
  val list: MutableCollection<Int> = LinkedList()
  list.add(3)
  list.add(2)
  list.add(1)

  println(list)
  list.remove(1)
  println(list)
}

"retaining elements" example {
  val list: MutableCollection<Int> = LinkedList()
  list.add(3)
  list.add(2)
  list.add(1)
  list.add(4)
  list.add(5)

  println(list)
  list.retainAll(listOf(3, 4, 5))
  println(list)
}

"去掉 all elements" example {
  val list: MutableCollection<Int> = LinkedList()
  list.add(3)
  list.add(2)
  list.add(1)
  list.add(4)
  list.add(5)

  println(list)
  list.removeAll(listOf(3, 4, 5))
  println(list)
}

正如您将暂时看到的,本章中的第一个挑战是检查每个示例的输出,以确保它是正确的。快速摘要后,您还将看到其余的挑战。

挑战

在这些挑战中,您将通过包含链接列表的五种常见场景。与大多数挑战相比,这些问题相对容易,并且他们将用于巩固您对数据结构的知识。您将在本章末尾找到对挑战的解决方案。

挑战1:反转链接列表

创建一个扩展函数,以相反的顺序打印出链接列表的元素。给定链接列表,以相反的顺序打印节点。例如:

1 -> 2 -> 3

// should print out the following:
3
2
1

解决方案1

A straightforward way to solve this problem is to use recursion. Since recursion allows you to build a call stack, you need to call the print statements as the call stack unwinds.

Your first task is to define an extension function for linkedlist.. Add the following helper function to your solution file:

fun <T> LinkedList<T>.printInReverse() {
  this.nodeAt(0)?.printInReverse()
}

This function forwards the call to the recursive function that traverses the list, node by node. To traverse the list, add this extension function for 节点:

fun <T> Node<T>.printInReverse() {
  this.next?.printInReverse()
}

As you’d expect, this function calls itself on the next node. The terminating condition is somewhat hidden in the null-safety operator. If the value of next is null, the function stops because there’s no next node on which to call printInReverse(). You’re almost done; the next step is printing the nodes.

印刷

Where you add the print statement will determine whether you print the list in reverse order or not. Update the function to the following:

fun <T> Node<T>.printInReverse() {
  this.next?.printInReverse()
  // 1
  if (this.next != null) {
    print(" -> ")
  }
  // 2
  print(this.value.toString())
}

仅在递归调用之后仅在基本情况触发之后调用之后的任何代码(即,在递归函数击中列表末尾之后)。

  1. 首先,您检查您是否已到达列表的末尾。这是反向打印的开始,并且您将不会在那里添加箭头。箭头从反向输出的第二个元素开始。这只是为了漂亮格式。

  2. 作为递归语句解开,节点数据被打印。

测试它!

在底部写下以下 main():

"print in reverse" example {
  val list = LinkedList<Int>()
  list.add(3)
  list.add(2)
  list.add(1)
  list.add(4)
  list.add(5)

  println(list)
  list.printInReverse()
}

您将看到以下输出:

---Example of print in reverse---
3 -> 2 -> 1 -> 4 -> 5
5 -> 4 -> 1 -> 2 -> 3

该算法的时间复杂性是 O(n) 由于您必须遍历列表的每个节点。

挑战2:中间的物品

给定链接列表,找到列表的中间节点。例如:

1 -> 2 -> 3 -> 4
// middle is 3

1 -> 2 -> 3
// middle is 2

解决方案2

一个解决方案是有两个引用遍历列表的节点,其中一个是另一个是另一个的两倍。一旦更快的参考到达结束,较慢的参考将在中间。写下以下功能:

fun <T> LinkedList<T>.getMiddle(): Node<T>? {
  var slow = this.nodeAt(0)
  var fast = this.nodeAt(0)

  while (fast != null) {
    fast = fast.next
    if (fast != null) {
      fast = fast.next
      slow = slow?.next
    }
  }

  return slow
}

在 the while declaration, you bind the next node to fast. If there’s a next node, you update fast to the next node of fast, effectively traversing down the list twice. slow is updated only once. This is also known as the 跑步技术.

试试看!

在底部写下以下 main.kt.:

"print middle" example {
  val list = LinkedList<Int>()
  list.add(3)
  list.add(2)
  list.add(1)
  list.add(4)
  list.add(5)

  println(list)
  println(list.getMiddle()?.value)
}

您将看到以下输出:

---Example of print middle---
3 -> 2 -> 1 -> 4 -> 5
1

该算法的时间复杂性是 O(n) 由于您在一次通过中遍历列表。这 跑步技术 有助于解决与链接列表相关的各种问题。

挑战3:反转链接列表

要反转列表是操纵节点,以便列表的节点以相反的方向链接。例如:

// before
1 -> 2 -> 3

// after
3 -> 2 -> 1

解决方案3.

To reverse a linked list, you need to visit each node and update the next reference to point in the other direction. This can be a tricky task since you’ll need to manage multiple references to multiple nodes. To do this, you would also need access to the 尾巴 of your liked list. Since you’re implementing an extension function, you won’t have access to these variables. Luckily, there’s a simpler solution that has a small drawback discussed later.

您可以使用进入列表末尾的递归函数轻松反转列表,然后在新的链接列表中开始复制节点。这是这个功能的样子:

private fun <T> addInReverse(list: LinkedList<T>, node: Node<T>) {
  // 1
  val next = node.next
  if (next != null) {
    // 2
    addInReverse(list, next)
  }
  // 3
  list.append(node.value)
}

以下介绍了该功能如何工作:

  1. 获取列表的下一个节点,从您作为参数收到的那个开始。

  2. 如果有以下节点,则递归调用相同的功能;但是,现在起始节点是当前节点之后的一个。

  3. 到达结束时,开始以相反的顺序添加节点。

O(n) 时间复杂性,短而甜蜜!唯一的缺点是您需要一个新列表,这意味着空间复杂性也是如此 O(n).

To use this helper function conveniently on a linkedlist., add this extension function:

fun <T> LinkedList<T>.reversed(): LinkedList<T> {
  val result = LinkedList<T>()
  val head = this.nodeAt(0)
  if (head != null) {
    addInReverse(result, head)
  }
  return result
}

This extension creates a new linkedlist. 和 fills it with nodes by calling 添加InReverse(), passing in the first node of the current list.

试试看!

Test reversed() by writing the following at the bottom of main():

"reverse list" example {
  val list = LinkedList<Int>()
  list.add(3)
  list.add(2)
  list.add(1)
  list.add(4)
  list.add(5)

  println("Original: $list")
  println("Reversed: ${list.reversed()}")
}

您将看到以下输出:

---Example of reverse list---
Original: 3 -> 2 -> 1 -> 4 -> 5
Reversed: 5 -> 4 -> 1 -> 2 -> 3

挑战4:合并两个链接的清单

创建一个函数,需要两个排序链接的列表,并将它们合并到单个排序的链表中

您的目标是返回一个新的链接列表,其中包含两个列表中的节点以排序顺序。您可以假设它们都按升序排序。例如:

// list1
1 -> 4 -> 10 -> 11

// list2
-1 -> 2 -> 3 -> 6

// merged list
-1 -> 1 -> 2 -> 3 -> 4 -> 6 -> 10 -> 11

解决方案4.

The solution to this problem is to continuously pluck nodes from the two sorted lists and add them to a new list. Since the two lists are sorted, you can compare the next node of both lists to see which one should be the next one to add to the new list.

配置

You’ll begin by checking the cases where one or both of the lists are empty. Create the following mergeSorted extension function:

fun <T : Comparable<T>> LinkedList<T>.mergeSorted(
  otherList: LinkedList<T>
): LinkedList<T> {
  if (this.isEmpty()) return otherList
  if (otherList.isEmpty()) return this

  val result = LinkedList<T>()

  return result
}

If one is empty, you return the other. You also introduce a new reference to hold a new linkedlist.. The strategy is to merge the nodes in thisotherList into result in sorted order.

接下来,您需要编写一个辅助函数,将当前节点添加到结果列表并返回下一个节点。您将多次在算法中使用此功能,因此它提取它很有用:

private fun <T : Comparable<T>> append(
  result: LinkedList<T>,
  node: Node<T>
): Node<T>? {
  result.append(node.value)
  return node.next
}

合并

Add the following to mergeSorted immediately below the declaration for result 和 right above return result:

// 1
var left = nodeAt(0)
var right = otherList.nodeAt(0)
// 2
while (left != null && right != null) {
  // 3
  if (left.value < right.value) {
    left = append(result, left)
  } else {
    right = append(result, right)
  }
}

这是它的工作原理:

  1. 您从每个列表的第一个节点开始。
  2. The while loop continues until one of the lists reaches its end.
  3. You compare the first nodes leftright to append to the result.

Since this loop depends on both leftright, it will terminate even if there are nodes left in either list.

Finally, add the following below the newly added code, and above return result, to handle the remaining nodes:

while (left != null) {
  left = append(result, left)
}

while (right != null) {
  right = append(result, right)
}

试试看!

在底部写下以下 main():

"merge lists" example {
  val list = LinkedList<Int>()
  list.add(1)
  list.add(2)
  list.add(3)
  list.add(4)
  list.add(5)

  val other = LinkedList<Int>()
  other.add(-1)
  other.add(0)
  other.add(2)
  other.add(2)
  other.add(7)

  println("Left: $list")
  println("Right: $other")
  println("Merged: ${list.mergeSorted(other)}")
}

您将看到以下输出:

---Example of merge lists---
Left: 1 -> 2 -> 3 -> 4 -> 5
Right: -1 -> 0 -> 2 -> 2 -> 7
Merged: -1 -> 0 -> 1 -> 2 -> 2 -> 2 -> 3 -> 4 -> 5 -> 7

该算法的时间复杂程度 O(m + n), 在哪里 m 是第一个列表中的节点# n 是第二列表中的节点#。

关键点

  • 链接列表是线性和单向的。一旦您将一个节点移动到另一个节点的引用,就无法返回。
  • 链接列表有一个 O(1)针对首先插入的时间复杂性。阵列有 O(n)针对首先插入的时间复杂性。
  • Conforming to Kotlin Collection接口, such as IterableCollection, offers a host of helpful methods for a reasonably small amount of requirements.

有一个技术问题?想报告一个错误吗? 您可以向官方书籍论坛中的书籍作者提出问题和报告错误 这里.

有反馈分享在线阅读体验吗? 如果您有关于UI,UX,突出显示或我们在线阅读器的其他功能的反馈,您可以将其发送到设计团队,其中表格如下所示:

© 2021 Razeware LLC