We know array in memory is a continuous distribution, if the current allocation of memory is full, and then to add elements, the system will be conducted on the basis of the current memory size must be a multiple of expansion to create a new memory area, after the success of the expansion to the original memory array elements copied to a new continuous memory.

One problem with this is that some of the memory in the array may not be needed, causing a certain amount of waste. So can you add an element to allocate a block of memory? A linked list is a linear data structure that dynamically allocates memory for each element (not necessarily consecutively).

Linked list data structure:

Node (the Node)

Each element in a linked list is represented by a node, which has the following characteristics:

  • Save a value
  • There is a reference to the next node

Node code implementation:

Class Node<Value> {var Value: Value // Save Node Value var next: Node? Init (value: value, next: Node? = nil) { self.value = value self.next = next } } extension Node: CustomStringConvertible { var description: String { guard let next = next else { return "\(value)" } return "\(value) -> " + String(describing: next) + " " } }Copy the code

Simple test:

    func nodeTest() {
        let node1 = Node(value: 1)
        let node2 = Node(value: 2)
        let node3 = Node(value: 3)
        node1.next = node2
        node2.next = node3
        print(node1)
    }
Copy the code

You can see the output looks like this:

1 -> 2 -> 3  
Copy the code

Why do nodes use class implementations instead of structs? This is because with reference types, objects can be destroyed when appropriate when there is no pointer to them.

Implementation of linked list

The elements in the list are represented by nodes. The first node is called head and the last node is tail.

Basic code:

struct LinkedList<Value> { var head: Node<Value>? Var tail: Node<Value>? } extension LinkedList: CustomStringConvertible {var description: String { guard let head = head else { return "Empty list" } return String(describing: head) } }Copy the code

In practice, linked lists are mainly used to add and delete nodes.

Add functionality

You can add a node in the following three ways:

  • Push, adding nodes to the head of the list;

  • Append, add nodes to the end of the list;

  • Insert (after:), insert the node to a location.

Push to realize

O(1) mutating func push(_ value: value) {head = Node(value: value, next: head) if tail == nil { tail = head } }Copy the code

Append to realize

Var isEmpty: Bool head == nil // Time complexity O(1) mutating func append(_ value: Value) { if isEmpty { push(value) return } tail? .next = Node(value: value, next: nil) tail = tail? .next }Copy the code

Insert (after)

Inserting a node into a location requires two steps:

1. Locate the position to insert the node.

2. Insert a new node.

Find a node at a location:

O(n) func node(at index: Int) -> node <Value>? { var current = head var currentIndex = 0 while current ! = nil && currentIndex < index { current = current? .next currentIndex += 1 } return current }Copy the code

Insert a new node:

O(1) @discardableresult func insert(_ value: value, after node: node < value >) -> node < value > {guard tail! == node else { return tail! } node.next = Node(value: value, next: node.next) return node.next! }Copy the code

Add all the functions to this node that need to be implemented. Here is the test code:

    func listAddTest() {
        var list = LinkedList<Int>()
        list.push(1)
        list.append(2)
        list.append(7)
        print("before inserting, list: \(list)")
        if let node = list.node(at: 1) {
            list.insert(10, after: node)
        }
        print("after inserting, list: \(list)")
        print("list is empty: \(list.isEmpty)")
    }
Copy the code

View the output:

before inserting, list: 1 -> 2 -> 7  
after inserting, list: 1 -> 2 -> 10 -> 7   
list is empty: false
Copy the code

Delete function

You can delete a node in the following three ways:

  • Pop, remove the linked list header node;

  • RemoveLast: delete the tail node.

  • Remove (after:) : deletes a node.

Pop implementation

O(1) @discardableresult mutating func pop() -> Value? { defer { head = head? .next if isEmpty { tail = nil } } return head? .value }Copy the code

RemoveLast implementation

The key point of removing the tail node is to find the previous node of the tail node, and then reset the pointing of the tail node after removal.

O(n) @discardableresult mutating func removeLast() -> Value? { guard let head = head else { return nil } guard head.next ! = nil else { return pop() } var prev = head var current = head while let next = current.next { prev = current current = next } prev.next = nil tail = prev return current.value }Copy the code

Remove (after)

O(1) @discardableresult mutating func remove(after node: node <Value>) -> Value? { defer { if node.next === tail { tail = node } node.next = node.next? .next } return node.next? .value }Copy the code

Test delete function code:

    func listDeleteTest() {
        var list = LinkedList<Int>()
        list.push(1)
        list.push(7)
        list.append(5)
        list.append(9)
        list.append(3)

        print("before pop, list: \(list)")
        list.pop()
        print("after pop, list: \(list)")
        list.removeLast()
        print("after removeLast, list: \(list)")
        list.remove(after: list.node(at: 0)!)
        print("remove node after index 0, list: \(list)")
    }
Copy the code

View the output:

before pop, list: 7 -> 1 -> 5 -> 9 -> 3    
after pop, list: 1 -> 5 -> 9 -> 3   
after removeLast, list: 1 -> 5 -> 9  
remove node after index 0, list: 1 -> 9 
Copy the code

At present, the main functions of the linked list have been realized. In the actual code implementation, we need to pay attention to the boundary problems of adding and deleting, such as whether the linked list is empty, or whether the linked list has only one node.

(Since in Swift, struct data is used as value data, and collection data structures like this ideally require array-like copy-on-write functionality, but for now the focus is on data structures, so those features are not implemented.)

Some practice

Reverse output linked list data

For example, a linked list looks like this: 1 -> 5 -> 9 Output: 9, 5, 1Copy the code

Implementation code:

Func reversedPrintList(_ list: LinkedList<Int>) {var tmpList = list var arry: [Int] = [] // Space complexity O(n) while let node = tmplist.pop () {arry.append(node)} while! arry.isEmpty { let node = arry.removeLast() print(node) } }Copy the code

Looking at the print test output, you can see that it is OK. However, one problem with the current implementation is that it creates an array temporarily, and the space complexity is O(n).

Here is an implementation using recursive optimization:

func printInReverse<T>(_ node: Node<T>?) {guard let node = node else {return} PrintInReverse (node.next) // print("\(node.value)")} func printInReverseForList<T>(_ list: LinkedList<T>) { printInReverse(list.head) }Copy the code

Find the intermediate node

// Index = 2, value = 10 1 -> 5 -> 10 -> 9 // Index = 1, value = 1 -> 5 -> 10Copy the code

Code implementation:

func middleNode() -> Node<Value>? Var current = head var curentIndex = 0 while let next = current? .next { current = next curentIndex += 1 } let count = curentIndex + 1 let middle = count/2 return node(at: middle) }Copy the code

Implementation using fast and slow Pointers (the core idea is that the slow pointer takes 1 step and the fast pointer takes 2 steps) :

func middleNode() -> Node<Value>? { var fast = head var slow = head while let fastNext = fast? .next { fast = fastNext.next slow = slow? .next } return slow }Copy the code

If you want more practice with linked lists, there are plenty of LeetCode filters.

In the actual practice solution, if the idea is vague, take a pen to draw more may be clear.