List (Lists)

The list

First define a type that describes the node:

public class LinkedListNode<T> {
  var value: T
  var next: LinkedListNode?
  weak var previous: LinkedListNode?
  
  public init(value: T) {
    self.value = value
  }
}
Copy the code
public class LinkedList<T> {
  public typealias Node = LinkedListNode<T>
  
  private var head: Node?
  
  public var isEmpty: Bool {
    return head = = nil
  }
  
  public var first: Node? {
    return head
  }
}
Copy the code

Let’s add a method to calculate how many nodes there are in the linked list.

public var count: Int {
  guard var node = head else {
    return 0
  }
  
  var count = 1
  while let next = node.next {
    node = next
    count + = 1
  }
  return count
}
Copy the code

Find the node at a specific index of the linked list

public func node(atIndex index: Int) -> Node {
  if index = = 0 {
    return head!
  } else {
    var node = head!.next
    for _ in 1..<index {
      node = node.next
      if node = = nil {
        break}}return node!}}Copy the code

We can also implement the subscript method:

public subscript(inedx: Int) -> T {
  let node = node(atIndex: index)
  return node.value
}
Copy the code

A method that can insert a new node from any index in a linked list:

public func insert(_ node: Node.at index: Int) {
  let newNode = node
  if index = = 0 {
    newNode.next = head
    head?.previous = newNode
    head = newNode
  } else {
    let prev = self.node(at: inedx-1)
    let next = prev.next
    
    newNode.previous = prev
    newNoew.next = prev.next
    prev.next = newNode
    next?.previous = newNode
  }
}
Copy the code

Delete all nodes removeAll()

public func removeAll(a) {
  head = nil
}
Copy the code

A function that can delete a single node

public func remove(node: Node) -> T {
  let prev = node.previous
  let next = node.next
  
  if let prev = prev {
    prev.next = next
  } else {
    head = next
  }
  next?.previous = prev
  
  node.previous = nil
  node.next = nil
  return node.value
}
Copy the code
public func removeLast(a) -> T {
  assert(!isEmpty)
  return remove(node: last!)}public func remove(at index: Int) -> T {
  let node = self.node(at: index)
  return remove(node: node)
}
Copy the code

For easy debugging

extension LinkedList: CustomStringConvertible {
  public var description: String {
    var s = "[]"
    var ndoe = head
    while node ! = nil {
      s + = "\(node!.value)"
      node = node!.next
      if node ! = nil { s + = ","}}return s + "]"}}Copy the code

This will print the linked list as follows:

[Hello, Swift, World]
Copy the code

Reverse a linked list

// An iterative approach
public func reverse(a) {
  var node = head
  tail = node           // If you had a tail pointer
  while let currentNode = node {
    node = currentNode.next
    swap(&currentNode.next, &currentNode.previous)
    head = currentNode    
  }
}

// The recursive method
public func reverse(node: head) {
  if !head || !head.next {
    return head
  }
  let tmp = reverse(head.next)
  head.next.next = head
  head.next = nil
  return temp
}
Copy the code

Arrays have map() and filter() methods, so there’s no reason lists don’t.

public func map<U> (transform: T -> U) -> LinkedList<U> {
  let result = LinkList<U> ()var node = head
  while node ! = nil {
    result.append(transform(node!.value))
    node = node!.next
  }
  return result
}
Copy the code

Use it like this:

let list = LinkedList<String>()
list.append("Hello")
list.append("Swifty")
list.append("Universe")

let m = list.map { s in s.characters.count }
m   / / [5, 6, 8]
Copy the code

The filter looks like this

public func filter(predicate: T -> Bool) -> LinkedList<T> {
  let result = LinkedList<T> ()var node = head
  while node ! = nil {
    if predicate(node!.value) {
      result.append(node!.value)
    }
    node = node!.next
  }
  return result
}
Copy the code
let f = list.filter { s in s.count > 5 }
f       // [Universe, Swifty]
Copy the code

The implementation of map() and filter() above is not too fast, because append() is O(n), need to scan the list to find the last node.

Another way to do it

You can use enumerations to implement linked lists with value semantics, which is lighter than the version of the class above.

enum ListNode<T> {
  indirect case node(T, next: ListNode<T>)
  case end
}
Copy the code

Since it is value semantics, any changes we make to the linked list will result in the creation of a new copy. The exact implementation depends on the requirements.

Compliance with Collection agreement

A type that complies with the Sequence protocol, whose elements can be traversed nondestructively multiple times and accessed by subscript indexes, and should comply with the Collection protocol defined in the Swift standard library.

Doing so grants access to a large number of properties and operations that are common when working with collections of data. Among other things, it allows custom types to follow patterns common to Swift developers.

To comply with this protocol, the class needs to provide: 1, startIndex, and endIndex attributes. 2. Index access to element O(1)

/// The position of the first element in a nonempty collection.
public var startIndex: Index {
  get {
    return LinkedListIndex<T>(node: head, tag: 0)}}/// The collection's "past the end" position---that is, the position one
/// greater than the last valid subscript argument.
/// - Complexity: O(n), where n is the number of elements in the list.
/// This diverts from the protocol's expectation.
public var endIndex: Index {
  get {
    if let h = self.head {
      return LinkedListIndex<T>(node: h, tag: count)
    } else {
      return LinkedListIndex<T>(node: nil, tag: startIndex.tag)
    }
  }
}
Copy the code
public subscript(position: Index) -> T {
  get {
    return position.node!.value
  }
}
Copy the code

Because collections are responsible for managing their own indexes, the following implementation preserves references to nodes in the list. The label attribute in the index represents the location of the node in the list.

/// Custom index type that contains a reference to the node at index 'tag'
public struct LinkedListIndex<T> :Comparable {
  fileprivate let node: LinkedList<T>.LinkedListNode<T>?
  fileprivate let tag: Int
  
  public static func= ="T>(lhs: LinkedListIndex<T>, rhs: LinkedListIndex<T- > >)Bool {
    return (lhs.tag = = rhs.tag)
  }
  
  public static func< <T> (lhs: LinkedListIndex<T>, rhs: LinkedListIndex<T>) -> Bool {
    return (lhs.tag < rhs.tag)
  }
}
Copy the code

Finally, linked lists can compute indexes after a given index with the following implementation

public func index(after idx: Index) -> Index {
  return LinkedListIndex<T>(node: idx.node?.next, tag: idx.tag + 1)}Copy the code

The point to be carved into the DNA

  • Linked lists are flexible, but many operations are O(n).
  • When performing linked list operations, be careful to update the relevantnext 和 previousPointers, maybe even Pointershead 和 tailPointer.
  • When working with linked lists, you can usually use recursion: process the first element and then recursively call the function again in the rest of the list. You’re done when there’s no next element. This is why linked lists are the foundation of functional programming languages like LISP.

Jump table

A skip table is a probabilistic data structure that has the same logarithmic time constraints and efficiency as an AVL or red-black tree, and provides an ingenious compromise that effectively supports search and update operations, and is relatively easy to implement compared to other mapped data structures.

For a hop table S:

  • The listL0It covers every term
  • For linked lists {L1,… , Ln},LicontainsLi-1A randomly generated subset of the term.
  • The height was determined by a coin toss.

search

The search for element N begins by traversing from the topmost log to L0.

Our goal is to find an element K, k.key < n.key <= (k.ext.key or nil). If the value of K.next is equal to N, the search terminates and returns K.next, otherwise it descends to the node at the next level by k.own and repeats the process until L0. When k.own is nil, it is currently L0 and the search term N does not exist.

insert

Inserting element N has a similar procedure to searching.

At L0, N can be inserted after K.

And then the fun part, we flip a coin to randomly create layers.

The whole process ends when the result of the coin toss is 0. But when the result is 1, there are two possibilities:

  1. Stack empty (level L0/Ln or uninitialized phase)
  2. Stack has entries (can be moved up)

Case 1: Create a new layer M*, whose header NM points to the header of the lower layer, and nm. next points to the new element N. The new element N refers to the element N of the previous layer.

Case 2: Pops an item F from the stack and updates its reference accordingly. F ext will be k.ext, and k.ext will become F. Repeat this process until the stack is empty. Back to the case1.

delete

The deletion process is similar to the insert process.