Data Structures and Algorithms – Simple Linked List Code (SWIFT)

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
    var next: LinkedListNode?
    init(value: T, next: LinkedListNode? = nil) {
        self.value = value
        self.next = next
    }
}
extension LinkedListNode: CustomStringConvertible {

    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> {

    var head: LinkedListNode<T>?

    var tail: LinkedListNode<T>?

    init() {}
}

extension LinkedList: CustomStringConvertible {

    var description: String {
        guard let head = head else { return "Empty List" }
        return String(describing: head)
    }
}

extension LinkedList {

    var isEmpty: Bool {

        return head == nil
    }
}
Copy the code

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

Add elements to a linked list

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.

Linked list lookup elements

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

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

Two-way linked list

Two-way list need extra space to store two subsequent nodes and precursor node address, so, stored the same amount of data, the two-way chain table than singly linked lists takes up more memory storage space, from the list on the structure of bidirectional it can support the O (1) time complexity of the cases to find precursors node, formal characteristics, Also makes the two-way linked list in some cases to insert, delete and other operations than the single linked list is simple, efficient.

Two-way linked list although more expensive memory, but still more widely used than single linked list, such as Java language LikedHashMap this container implementation principle is to use the structure of double linked list

conclusion

Array in the insert and delete operations, in order to maintain the continuity of memory data, you need to do a lot of data is moved So the time complexity is O (n), and insert or delete a data in the list, we don’t need to keep the continuity of memory moving nodes, because the list of storage space itself is not continuous, So the list inserts and deletes a piece of data very quickly

However, because the data in a linked list is not stored contiguously, you cannot use an addressing formula to directly find the corresponding memory address based on the first address and the subscript, as you can do with an array.Space for time, or time for space. When memory space is sufficient, if we are more interested in the speed of code execution, we can choose an algorithm with relatively high space complexity but relatively low time complexity. On the contrary, when memory is scarce, Can consume more time (time for space) to reduce the consumption of memory to find a time to learn their own, bits and pieces of things summed up, mainly to think more when writing, and then the good code, their own problems to solve their own things. Lebron has always been my mentor in my study

Lebron code reference, click here to view the original