在本教程中，我们将使用Swift讨论和实现链接列表数据结构。

什么是LinkedList？

LinkedList是一种数据结构，可以线性/顺序保存数据。

通常，我们将LinkedList的每个元素称为节点。

因此，每个节点都由值和对下一个元素的引用组成。

下图说明了一个节点。

LinkedList只是节点列表，每个节点其中存储下一个节点的引用。

第一节点通常称为HEAD。
当最后一个节点的NEXT为Nil时，LinkedList完成。

双链表会存储其上一个节点和下一个节点的引用。

在以下部分中，我们将创建Node结构并在LinkedList上执行各种操作，例如：

• 追加新元素
• 链表的大小
• 在某个位置插入元素
• 删除元素
• 向前和向后打印LinkedList
• 从特定位置检索节点

打开您的Xcode Playground，让Swift来吧！

创建一个Swift LinkedList节点

我们可以创建一个通用类型的节点，如下所示：

public class SNode<T> {
  var value: T
  var next: SNode<T>?
  
  init(value: T) {
      self.value = value
  }
}

SNode代表LinkedList的Node的实例。

让我们创建一个类" SingleLinkedList <T>"，其中创建并修改我们的LinkedList

class SingleLinkedList<T> {
  
  var head: SNode<T>? //head is nil when list is empty
  
  public var isEmpty: Bool {
      return head == nil
  }
  
  public var first: SNode<T>? {
      return head
  }

isEmpty是一个属性，用于检查LinkedList是否为空。
如果头为零，则LinkedList将为空。

在Swift LinkedList中追加元素

在上面的类中添加以下append函数。

public func append(value: T) {
      let newNode = SNode(value: value)
      if var h = head {
          while h.next != nil {
              h = h.next!
          }
          h.next = newNode
          
      } else {
          head = newNode
      }
  }

append函数将一个新的Node添加到列表的末尾。
为此，我们使用名为h的标头的临时Node引用遍历LinkedList的末尾。

当h的下一个引用为nil时，表示我们位于LinkedList的末尾。
我们在这里通过将最后一个节点的下一个设置为newNode。

在某个位置插入元素

要在某个位置插入元素，我们需要：将先前的Node NEXT引用设置为新元素。
将新元素的NEXT设置为当时存在的当前元素。

将以下函数插入添加到上面的LinkedList类中。

func insert(data : T, at position : Int) {
      let newNode = SNode(value: data)
      
      if (position == 0) {
          newNode.next = head
          head = newNode
      }
      else {
          var previous = head
          var current = head
          for _ in 0..<position {
              previous = current
              current = current?.next
          }
          
          newNode.next = previous?.next
          previous?.next = newNode
      }
  }

从Swift LinkedList删除节点

要删除一个节点，我们需要将前一个节点的引用设置为要删除的节点的NEXT。

在上面的类中添加以下函数。

func deleteNode(at position: Int)
  {
      if head == nil{
      return
      }
      var temp = head
      
      if (position == 0)
      {
          head = temp?.next;   //Change head
          return
      }
  
      for _ in 0..<position-1 where temp != nil {
          temp = temp?.next;
      }

      if temp == nil || temp?.next == nil{
         return
      }

      let nextToNextNode = temp?.next?.next
      
      temp?.next = nextToNextNode
  }

打印元素

要打印元素，我们需要遍历LinkedList直到到达最后一个元素并一路打印这些元素。

要以相反的顺序打印元素，我们使用递归函数！

func printList() {
      var current: SNode? = head
      //assign the next instance
      while (current != nil) {
          print("LL item is: \(current?.value as? Int ?? 0)")
          current = current?.next
      }
  }
  
  
  func printReverseRecursive(node: SNode<T>?) {
  if node == nil{
  return
  }
  printReverseRecursive(node: node?.next)
  print("LL item is: \(node?.value as? Int ?? 0)")
  }
  
  func printReverse() {
      printReverseRecursive(node: first)
      
  }

将以上所有操作汇总到我们的类中将使我们的类看起来像这样：

class SingleLinkedList<T> {
  
  var head: SNode<T>? //head is nil when list is empty
  
  public var isEmpty: Bool {
      return head == nil
  }
  
  public var first: SNode<T>? {
      return head
  }
  
  public func append(value: T) {
      let newNode = SNode(value: value)
      if var h = head {
          while h.next != nil {
              h = h.next!
          }
          h.next = newNode
          
      } else {
          head = newNode
      }
  }
  
  func insert(data : T, at position : Int) {
      let newNode = SNode(value: data)
      
      if (position == 0) {
          newNode.next = head
          head = newNode
      }
      else {
          var previous = head
          var current = head
          for _ in 0..<position {
              previous = current
              current = current?.next
          }
          
          newNode.next = previous?.next
          previous?.next = newNode
      }
  }
  
  func deleteNode(at position: Int)
  {
      if head == nil{
      return
      }
      var temp = head
      
      if (position == 0)
      {
          head = temp?.next
          return
      }
  
      for _ in 0..<position-1 where temp != nil {
          temp = temp?.next
      }

      if temp == nil || temp?.next == nil{
         return
      }

      let nextToNextNode = temp?.next?.next
      
      temp?.next = nextToNextNode
  }
  
  func printList() {
      var current: SNode? = head
      //assign the next instance
      while (current != nil) {
          print("LL item is: \(current?.value as? Int ?? 0)")
          current = current?.next
      }
  }
  
  
  func printReverseRecursive(node: SNode<T>?) {
  if node == nil{
  return
  }
  printReverseRecursive(node: node?.next)
  print("LL item is: \(node?.value as? Int ?? 0)")
  }
  
  func printReverse() {
      printReverseRecursive(node: first)
      
  }
}

让我们从LinkedList中添加，插入或者删除元素。

let ll = SingleLinkedList<Int>()
ll.append(value: 1)
ll.append(value: 2)
ll.append(value: 4)
ll.insert(data: 5, at: 0)
ll.insert(data: 10, at: 1)
ll.printList()
ll.deleteNode(at: 0)
print("Printing Reverse:")
ll.printReverse()

双链表

让我们为双重链接列表创建一个节点。

public class DNode<T> {
var value: T
var next: DNode<T>?
weak var previous: DNode<T>?

init(value: T) {
  self.value = value
}
}

为了防止出现记忆周期，我们将先前的参考设置为弱。

public class DoublyLinkedList<T> {
var head: DNode<T>?
private var tail: DNode<T>?

public var isEmpty: Bool {
  return head == nil
}

//first
public var first: DNode<T>? {
  return head
}

//last
public var last: DNode<T>? {
  return tail
}
//Append node to LinkedList
public func append(value: T) {
  let newNode = DNode(value: value)
  if let tailNode = tail {
    newNode.previous = tailNode
    tailNode.next = newNode
  } else {
    head = newNode
  }
  tail = newNode
}
  
  func insert(node: DNode<T>, at index: Int) {
      if index == 0,
          tail == nil {
          head = node
          tail = node
      } else {
          guard let nodeAtIndex = nodeAt(index: index) else {
              print("Index out of bounds.")
              return
          }
          
          if nodeAtIndex.previous == nil {
              head = node
          }
          
          node.previous = nodeAtIndex.previous
          nodeAtIndex.previous?.next = node
      
          node.next = nodeAtIndex
          nodeAtIndex.previous = node
      }
  }

//Find Node at Index
public func nodeAt(index: Int) -> DNode<T>? {
  if index >= 0 {
    var node = head
    var i = index
    while node != nil {
      if i == 0 { return node }
      i -= 1
      node = node!.next
    }
  }
  return nil
}
  
public func removeAll() {
  head = nil
  tail = nil
}

//remove Node
public func remove(node: DNode<T>) -> T {
  let previousNode = node.previous
  let nextNode = node.next

  if let prev = previousNode {
    prev.next = nextNode
  } else {
    head = nextNode
  }
  nextNode?.previous = previousNode

  if nextNode == nil {
    tail = previousNode
  }

  node.previous = nil
  node.next = nil
  
  return node.value
}
  
  var count: Int {
      if (head?.value == nil) {
          return 0
      }
      else {
          var current: DNode? = head
          var x: Int = 1
          
          //cycle through the list of items
          while ((current?.next) != nil) {
              current = current?.next!
              x = x + 1
          }
          return x
      }
  }
  
  func printReverse() {
      var current: DNode? = tail;
      //assign the next instance
      while (current != nil) {
          print("DLL item is: \(current?.value as? String ?? "NA")")
          current = current?.previous
      }
  }
  
  func printForward() {
      var current: DNode? = head
      //assign the next instance
      while (current != nil) {
          print("DLL item is: \(current?.value as? String ?? "NA")")
          current = current?.next
      }
  }
  //remove from index
  func remove(at index: Int) {
      var toDeleteNode = nodeAt(index: index)
      guard toDeleteNode != nil else {
          print("Index out of bounds.")
          return
      }
      
      let previousNode = toDeleteNode?.previous
      let nextNode = toDeleteNode?.next
      
      if previousNode == nil {
          head = nextNode
      }
      
      if toDeleteNode?.next == nil {
          tail = previousNode
      }
      
      previousNode?.next = nextNode
      nextNode?.previous = previousNode
      
      toDeleteNode = nil
  }
}

在双向链接列表中，我们会同时处理上一个和下一个参考。

let dd = DoublyLinkedList<String>()
dd.append(value: "Harry Potter")
dd.append(value: "Ron")
dd.append(value: "Hermione")
dd.append(value: "Hagrid")
dd.append(value: "Draco")
dd.append(value: "Snape")

//Run the following
print(dd.count)
dd.printReverse()
dd.remove(at: 1)
var dNode = DNode(value: "Harry Potter")
dd.remove(node: dNode)
print(dd.nodeAt(index: 4))
print(dd.nodeAt(index: 10))
dd.insert(node: dNode, at: 4)
dd.printForward()