Daily development, will use a large number of collection types, usually we often say: data structure refers to a group of data storage, algorithm is a group of methods to operate data, data structure is for the service of algorithm, algorithm should act on a specific data node, algorithm and data structure complement each other. Code execution performance is a very important standard, usually write the business logic basically do not consider performance, first development and then, but the more may be to write business. Anyway, the sooner you realize that the sooner you get it right, the better. You master the data structure and the algorithm, and you look at the depth of the problem and you solve it from a completely different perspective.

## Linear and nonlinear

Linear table: is to arrange the data into a line like data structure, each linear table data only before and after the two methods usually we use arrays, lists, queues, stacks and other linear table structure.

Non-linear table: non-sequential relationships in data, such as binary trees, heaps, graphs, etc. Whether it’s a linked list,

The most basic guarantee operation should realize the function of adding, deleting, checking and changing.

## An array of

Since it was so good, curiosity drove me to open the door to find out. The first thing that comes to mind is an array, and an array is a structure of a linear list. It is a continuous set of memory Spaces to store a set of data of the same type.

We know that a computer assigns an address to each element of memory. The computer accesses the data in memory through the address. When the computer needs random access, it calculates the memory address of the element by using the following addressing formula

``````a[i]_address = base_address + i * data_type_size
Copy the code``````

In most programming languages, arrays are numbered from 0, not 1. From the perspective of the array memory model, the most precise definition of “subscript” should be offset. A [0] is the first address of an array offset by 0, so a[k] is the offset by k type_size positions.

``````a[k]_address = base_address + k * type_size
Copy the code``````

If the array starts at 1, then the memory address of the element a[k] that we calculate will become

``````a[k]_addrss = base_address + (k - 1) * type_size
Copy the code``````

And what we find is that if you start numbering at 1, each random access to an element of the array gives you one more subtraction, so for the CPU, there’s one more layer of subtraction

## The list

The first time I saw a linked list, I couldn’t figure out how to do this programmatically. It took a lot of detours. Before I could get into a bracelet, I had to understand the concept of a pointer. So when you assign a variable to a pointer, you actually assign the address of the variable to the pointer, or vice versa, the pointer stores the memory address of the variable, points to the variable, and you can find the variable through the pointer

P -> next = q the next pointer in the p node stores the memory address of the q node. There is a more complicated one: p -> next = p -> next -> next. This line of code indicates that the next address of node P stores the memory address of the next node of node P. This is also the code to remove the final node assignment.

The first is the declaration of the node:

``````final class LinkedListNode<T> {
var value: T
init(value: T, next: LinkedListNode? = nil) {
self.value = value
self.next = next
}
}

var description: String {
guard let next = next else {
return "\(value)"
}
return "\(value) -> \(String(describing: next))"
}
}
Copy the code``````

Nodes use:

``let node1 = LinkedListNode(value: 1) let node2 = LinkedListNode(value: 2) let node3 = LinkedListNode(value: 3) node1.next = node2 node2.next = node3 print(node1Copy the code``

We create a LinkedList defined as a Struct type, which is also generic

``````struct LinkedList<T> {

init() {}
}

var description: String {
}
}

var isEmpty: Bool {

}
}
Copy the code``````

Head is the first node, tail is the last node, and isEmpty is added for future use

``Mutating func append(_ value: T) {guard! isEmpty else { let node = LinkedListNode(value: value) head = node tail = node return } let next = LinkedListNode(value: value) tail? .next = next tail = next } mutating func insert(_ value: T, after node: LinkedListNode<T>) { guard tail ! == node else { append(value) ; Next = LinkedListNode(value: value, next: node.next) // Node.next is the next pointer}}Copy the code``

Append if the list is empty, assign Node to both the head Node and the tail Node, and then point the original tail Node next to the new Node, and the tail Node equals the new Node

### List deletion operation

``Mutating func removeLast() -> T? { guard let head = head else { return nil } guard head.next ! = nil else { let headValue = head.value self.head = nil tail = nil return headValue } var prev = head var current = head  while let next = current.next { prev = current current = next } prev.next = nil tail = prev return current.value } mutating func remove(after node: LinkedListNode<T>) -> T? { defer { if node.next === tail { tail = node } node.next = node.next? .next } return node.next? .value } }Copy the code``

In a list deletion operation, note the possible boundary problem: the list is empty, the list has only one element, the instance prev variable and the current variable, the prev attribute is stored as the relay, and when current is traversed until next is nil, prev is the penultimate variable.

``extension LinkedList { func node(at index: Int) -> LinkedListNode<T>? { var currentNode = head var currentIndex = 0 while currentNode ! = nil && currentIndex < index { currentNode = currentNode? .next currentIndex += 1 } return currentNode } }Copy the code``

List lookup operation: start from the node step by step traversal operation

### Performance analysis

The method name Methods an overview Time complexity
append() Add the element at the end O(1)
insert(after:) Adds an element after a node O(1)
removeLast() Remove the last element O(n), n is the number of elements, because you have to start at the beginning to find the last element, so it’s O(n).
remove(after:) Removes the element after a node O(1)
node(at:) To find a`index`Corresponding element O(I), I is index, because I have to start from scratch, so it’s O(I).

## To implement the linked list of the collection protocol

Why implement a series of Collection protocols? Imagine, first of all, the list can store a series of nodes, it is reasonable to implement Sequence protocol, and the list nodes are limited, which is also in line with the requirements of Collection protocol. After implementing the Collection protocol, we can use a for-in loop. From apple’s documentation, we can see that implementing the Collection protocol requires:

``````startIndex()
endIndex()
index(after:)
subscript(index: Index) -> T
Copy the code``````

`It is important to note that the event complexity of accessing an element through index is O(I), which is different from linear collections such as arrays, which can be quickly found by addressing formulas, and linked lists, which can be stored in memory in non-sequential ways, store the address of the next element through next in the node. Therefore, there is no way to meet the requirements of the Collection protocol, so we define a custom Index type to store the corresponding Node. Why do collections do this? The performance of some Collection operations depends on the type of index provided by the Collection`

As you can see from the code implementation, since the custom Index itself contains the node, startIndex can directly get the head, endIndex can directly get the tail? Next, subscript can also directly obtain the value of the node corresponding to the index, so obviously the time complexity is O(1).

``extension LinkedList: Collection { struct Index: Comparable { var node: LinkedListNode<T>? static func == (lhs: Index, rhs: Index) -> Bool { switch (lhs.node, rhs.node) { case let (left? , right?) : return left.next === right.next case (nil, nil): return true default: return false } } static func < (lhs: LinkedList<T>.Index, rhs: LinkedList<T>.Index) -> Bool { guard lhs ! = rhs else { return false } let nodes = sequence(first: lhs.node) { \$0? .next } return nodes.contains { \$0 === rhs.node } } } var startIndex: Index { return Index(node: head) } var endIndex: Index { return Index(node: tail? .next) } subscript(index: Index) -> T { return index.node! .value } func index(after i: Index) -> Index { return Index(node: i.node? .next) } }Copy the code``

The above code defines the Index type and then implements the properties and methods required by the Collection protocol, but there are two more explanations

Sequence (first:) returns a sequence of the next first and repeated lazy applications. The first element in a sequence is always the first, and each subsequent element is the result of calling next to the previous element. The sequence ends when next returns nil. If next never returns nil, the sequence is infinite. This function can be used to replace many of the cases previously handled using a C-style for loop. For example, if the list contains the values 1, 2, and 3, if you pass in the first parameter 2, then nodes will be 2, 3 nodes. Contains {\$0 === hs. Node} Returns true if the following array sequence has RHS

Finally, I’d like to extend what the Comparable protocol means to our custom types:

``struct Person: Comparable, CostomStringConvertible { static func <(lhs:Person, rhs:Person) -> Bool { if lhs.age == rhs.age { return lhs.name < rhs.name } return lhs.age < rhs.age } let age: Int let name:String var description: String { "\(name:\(age))" } } let p1 = Person(age: 25, name: "wade") let p2 = Person(age: 25, name: "Lebron") let persons = [p1, P2] print("persons:\(persons)") let = persons. Sorted () print("sorted:\(sorted)")  sorted:[Lebron:25,wade: 25] If Person does not implement Comparable protocols, Let sorted = persons.sorted{LHS, RHS in if LHS. Age == RHS. Age {return LHS. Name < RHS < rhs.age }Copy the code``

## Make the list with content copy function

Many of the Swift library’s value types, such as array dictionary tuples, have content-copy capabilities,

``var list1 = LinkedList<Int>() list1.append(1) list1.append(2) list1.append(3) let list2 = list1 print("list1: \ [list1) ") print (" list2: \ (list2) ") list1. Append (4) print (" list1: \ (list1) ") print (" list2: \ (list2) ") / / list1 results: 1 - > 2 - > 3 list2:1 - > 2 - > 3 = = = = = = = = = = = = = = = = = = = segmentation list1:1 - > 2 - > 3 - > 4 list2:1 - > 2 - > 3 - > 4Copy the code``

Results: Changing one list will affect the other, indicating that our LinkedList is currently a reference type. The reason for this is that our underlying storage node LinkedListNode is of type Class and is a reference type. To fix this problem, We need to copy the node before changing the list element. And then there’s the question of why you use a Class instead of a struct for content copying in the first place, mainly because a struct stores the address of the next node, and if you use a struct it’s not the address of the next node.

``mutating func copyNodes() { guard ! IsKnownUniquelyReference (&head) else {return} guard var oldNode = head else {return} // Head node must have head = LinkedListNode(value: Var newNode = head while let nextOldNode = oldNode.next {let nextNewNode = LinkedList(value: nextOldNode.value) newNode? .next = nextNewNode newNode = nextNewNode // oldNode = nextOldNode // oldNode = nextOldNode}}Copy the code``

Add the copyNodes() method to the top of all methods that change a linked list element: append(),insert(after).

## LRU cache elimination algorithm

Buffer is a kind of improving the calculation of data read, but the size of the cache is limited, when the cache is used with the system to decide which data should be cleared out, like download images, or files, memory warning occurs when the app, the algorithm to the optimal cleaning resources, would require the elimination strategy to decide, there are three common strategies, FIFO FIFO, Policy LFU is used least and policy LRU is used least recently

We maintain an ordered list of single linked nodes. The nodes closer to the end of the list are accessed earlier. When a new data is accessed, we start at the head of the list and traverse the list sequentially

If this data is cached in chain table, before we traverse to get this data corresponding to the node, and will be removed from its original position, and then inserted into the list head If the buffer is not full, it will be the nodes directly inserted into the list of the head, if the buffer is full, the chain table tail node to delete, insert the new data node list head