This is the 11th day of my participation in Gwen Challenge

Arrays are an important data structure in software development, but they have at least two limitations:

  • Element sizes need to be determined at compile time
  • Arrays are contiguous in memory, and insertion or deletion requires moving other data in the array

Arrays are good for handling data of definite length that is insensitive to insertion or deletion. If the data is changing frequently, you need to choose another data structure. Linked lists are logically simple and useful data structures,

  1. Singly linked lists,
    1. In addition to storing data, each node in the linked list also needs to record the address of the next node on the chain
    2. Header (base address of the linked list)
    3. End node
  2. Circular linked list
    1. A pointer to the tail of a circular list points to the head of the list
  3. Two-way linked list
    1. Bidirectionally linked lists require two extra Spaces to store the addresses of successor nodes and precursor nodes; Comparison memory
    2. Insert and delete are more efficient

The design idea of exchanging space for time

When memory is available, we can choose algorithms or data structures with relatively high spatial complexity but low time complexity if we are more interested in fast code execution. On the contrary, if the memory is relatively short, such as the code running on the mobile phone or microcontroller, at this time, it is necessary to reverse the design idea of time for space

Compare data to linked lists

  1. Arrays require contiguous memory space and can be preread with the help of the CPU’s cache mechanism, so access efficiency is higher
  2. Fixed size, once declared to occupy the whole block of continuous memory space. If the declared array is too large, the system may not have enough contiguous memory to allocate to it, resulting in “out of memory.” It is stated that the next operation needs to copy the past first, which is very time-consuming; List dynamic capacity expansion
  3. Linked list can dynamically allocate storage, adapt to the situation of dynamic increase and decrease of data, and can easily insert and delete data items. The list must find the next element based on the next pointer
  4. As you can see from the above comparison, arrays should be used if you need fast access to data with little or no insertion or deletion. In contrast, linked list data structures are used if you need to insert and delete elements frequently.

Use SWIFT to implement data linked lists

public class Node<Value> {
    public var value: Value
    public var next: Node?
    
    public init(value:Value.next:Node? = nil) {
        self.value = value
        self.next = next
    }
}
extension Node: CustomStringConvertible {
    public var description: String {
        guard let next = next else {
            return "\(value)"
        }
        return "\(value) -> " + String(describing:next)
    }
}

let node1 = Node(value: "A")
let node2 = Node(value: "B")
let node3 = Node(value: "C")
node1.next = node2
node2.next = node3
// print(node1.description)

public struct LinkedList<Value> {
    public var head: Node<Value>?
    public var tail: Node<Value>?
    public init(a){}
    
    public var isEmpty: Bool {
        return head = = nil}}extension LinkedList: CustomStringConvertible {
    public var description: String {
        guard let head = head else {
            return "Empty list"
        }
        return String(describing:head)
    }
}

/// Expand the push method
extension LinkedList {
    public mutating func push(_ value: Value) {
        head = Node(value: value, next: head)
        if tail = = nil {
            tail = head
        }
    }
}

/// Expand the append method
extension LinkedList {
    public  mutating func append(_ value: Value) {
        guard !isEmpty else
        {
            push(value)
            return
        }
        tail?.next = Node(value: value)
        tail = tail?.next
    }
}

/// Expand the insert method to specify inserts
extension LinkedList {
    
    public mutating func insert(_ value:Value.after node:Node<Value>)->Node<Value> {
        guard tail ! = = node else {
            append(value)
            return tail!
        }
        node.next = Node(value: value, next: node.next)
        return node.next!}}// Test
var linked = LinkedList<String>()
linked.head = node1
linked.tail = node2
print(linked.description)

// linked.push(value: <#T##String#>)
linked.push("E")
linked.push("D")
linked.push("F")
// linked.tail = node1
print(linked.description)
linked.insert("AA", after: node1)
print(linked.description)


/ / / the result
A -> B -> C
F -> D -> E -> A -> B -> C
F -> D -> E -> A -> AA -> B -> C

Copy the code

reference

Zhuanlan.zhihu.com/p/52878334 www.jianshu.com/p/edbae3d56…