Github
First list
Linked list: A chain structure that uses nodes to store content, with the current node’s next pointer pointing to the next node. Nodes can be stored with scattered memory, so memory utilization is higher and memory footprint is smaller. But because the next node can only be found through the next pointer, each node lookup needs to start at the beginning.
Because of the next pointer, it is not as efficient at finding and modifying as arrays, but it is more efficient at adding and deleting.
Structure: (Node) (Node) (Node) ----------- ----------- ----------- | | | | | | head--> | value | ---> | value | ---> | value | --> nil | | | | | | ----------- ----------- -----------Copy the codeDefine a linked list
class Node { var val: Int var next: Node? init(val: Int, next: Node?) { self.val = val self.next = next } } class LinkList { var dummy: Node? var size: Int init() { dummy = Node(val: 0, next: nil) size = 0 } private func node(_ index: Int) -> Node? { var curNode = dummy? .next var curIndex = index while curIndex > 0 { curNode = curNode? .next curIndex -= 1 } return curNode } }Copy the codeStart by declaring a Node class that contains val and next. Val is used to store values, and next is used to point to the next node.
We then declare a class named LinkList to represent the list. Dummy next points to the head node and size stores the current length of the linked list.
It is important to explain why dummy nodes are set up. This avoids a lot of logical judgment when adding the first node.
Finally, create a node(_:) private function to get the current index node.
add
public func append(val: Int) { let newNode = Node(val: val, next: nil) if size == 0 { dummy? .next = newNode } else { var curSize = size var curNode = dummy while curSize > 0 { curNode = curNode? .next curSize -= 1 } curNode? .next = newNode } size += 1 }Copy the codeThere are two scenarios for adding nodes to the tail:
- Condition 1: size == 0, indicating that there is no linked list and no nodes are saved.
- Condition 2: size > 0
In condition 1, dummy next points to newNode, while in condition 2, dummy next points to newNode.
Finally, don't forget to add size + 1.
delete
public func remove(_ index: Int) -> Int? { guard index > -1 && index < size else { return nil } let val: Int if index == 0 { val = dummy? .next? .val ?? 0 dummy? .next = dummy? .next? .next } else { let prev = node(index - 1) val = prev? .next? .val ?? 0 prev? .next = prev? .next? .next } size -= 1 return val }Copy the codeBefore removing the index, verify the validity of the index.
Remove operation and add operation also have the following two cases:
- Condition 1: Removes the header.
- Condition 2: Removes other nodes.
The core of the remove operation is to find the previous node prev (obtained by node(_:)) and point the next pointer of prev to its next next. Such as: prev? .next = prev? .next? The next.
Finally, don’t forget size-1.
insert
public func insert(_ val: Int, atIndex index: Int) { guard index > -1 && index <= size else { return } let newNode = Node(val: val, next: nil) if index == 0 { newNode.next = dummy? .next dummy? .next = newNode } else { let pre = node(index - 1) newNode.next = pre? .next pre? .next = newNode } size += 1 }Copy the codeInsert operation is a relatively complex operation, which should take into account index == 0, index == size and other conditions.
The core operation of the insert operation has two steps:
- Next points the newNode newNode to the node with the current index.
- Point next of the prev node of the current node to the newNode newNode.
The sequence of these two steps is very important, so don’t make any mistakes.
Follow the steps above to examine the code for the insert operation. – newNode.next = dummy? – newNode.next = dummy? .next; Next: next of the prev of the current node to the newNode newnode-dummy? .next = newNode.
Same as above when index > 0. Finally, don’t forget size + 1.
The query
public func get(_ index: Int) -> Int? { guard index > -1 && index < size - 1 else { return nil } return node(index)? .val }Copy the codeThe query operation is the simplest one. Check the validity of index and obtain the corresponding node through node(_:).
The above is the realization of the basic operation of the linked list.
extension
Supports generics
The above example code only supports storing data of type Int, and in a project you may need to support multiple types, so it’s worth changing it to support generics.
class Node<Element> { var val: Element? var next: Node? init(val: Element? , next: Node?) { self.val = val self.next = next } } class LinkList<Element> { var dummy: Node<Element>? var size: Int public init() { dummy = Node(val: nil, next: nil) size = 0 } public func append(val: Element) { let newNode = Node(val: val, next: nil) if size == 0 { dummy? .next = newNode} else {// find the end node var curSize = size var curNode = dummy while curSize > 0 {curNode = curNode? .next curSize -= 1 } curNode? .next = newNode } size += 1 } public func remove(_ index: Int) -> Element? { guard index > -1 && index < size else { return nil } let val: Element? if index == 0 { val = dummy? .next? .val dummy? .next = dummy? .next? .next } else { let prev = node(index - 1) val = prev? .next? .val prev? .next = prev? .next? .next } size -= 1 return val } public func get(_ index: Int) -> Element? { guard index > -1 && index < size - 1 else { return nil } return node(index)? .val } public func insert(_ val: Element, atIndex index: Int) { guard index > -1 && index <= size else { return } let newNode = Node(val: val, next: nil) if index == 0 { newNode.next = dummy? .next dummy? .next = newNode } else { let pre = node(index - 1) newNode.next = pre? .next pre? .next = newNode } size += 1 } private func node(_ index: Int) -> Node<Element>? { var curNode = dummy? .next var curIndex = index while curIndex > 0 { curNode = curNode? .next curIndex -= 1 } return curNode } }Copy the codeSupport the index
Indexing can also be supported by overriding subscript.
extension LinkList { public subscript(index: Int) -> Element? { return node(index)? .val } }Copy the code