Like an array, a linked list is a collection of elements.
Classification of linked lists
Singly linked list
A node in a unidirectional list stores the address of the next node. The diagram below:
+--------+ +--------+ +--------+ +--------+ | | | | | | | | | node 0 |--->| node 1 |--->| node 2 |--->| node 3 | | | | | | | | | +--------+ +--------+ +--------+ +--------+Copy the codeTwo-way linked list
Nodes in a bidirectional list store the addresses of the previous and the next nodes. The diagram below:
+--------+ +--------+ +--------+ +--------+
| |--->| |--->| |--->| |
| node 0 | | node 1 | | node 2 | | node 3 |
| |<---| |<---| |<---| |
+--------+ +--------+ +--------+ +--------+
Copy the codeComparison of unidirectional and bidirectional linked lists
A unidirectional linked list uses less memory because it does not store the address of the previous node; But if we need to access the previous node, the one-way list is very cumbersome and needs to start from scratch, while the two-way list is very easy. In many cases, two-way lists are easier to use.
Linked list implementation
Here we take a unidirectional linked list as an example.
LinkedListNode
Since a linked list is made up of a series of nodes, we first define a node type.
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 codeDefine a node as generic, so it can store any type of data; There are two properties, the value of the current node and the next node; Implemented CustomStringConvertible protocol, so it looks better when printing lists.
Let’s try it out:
let node1 = LinkedListNode(value: 1)
let node2 = LinkedListNode(value: 2)
let node3 = LinkedListNode(value: 3)
node1.next = node2
node2.next = node3
print(node1)
/ / the result
1 -> 2 -> 3
Copy the codeLinkedList
We define LinkedList as a Struct type, which is also generic.
struct LinkedList<T> {
var head: LinkedListNode<T>?
var tail: LinkedListNode<T>?
init(a){}}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 codeHead is the first element; Tail is the last element. The isEmpty property has also been added for later use.
Add elements
Here we define two ways to add elements: 1) append() : adds an element to the end of the list; 2) Insert (after:) : add elements after a node.
extension LinkedList {
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); return }
node.next = LinkedListNode(value: value, next: node.next)
}
}
Copy the codeappend(): First determines whether it is null. If it is, thenheadandtailAre the currently added elements; If not, updatetail? .nextFor the currently added element, finally in the puttailUpdate to the currently added element.insert(after:): First judgenodeIs there already the last element, if so, call directlyappend()Add; Otherwise, updatenode.next.
Remove elements
1) removeLast() : remove the last element from the list; 2) remove(after:) : remove the elements after a node.
extension LinkedList {
mutating func removeLast(a) -> 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 coderemoveLast(): checks whether the element is empty. If it is empty, it returnsnil;head.next ! = nilDetermine if there is only one element. If so, define a variable storehead.value,headandtailAll set tonilAnd returnheadValue; A linked list has multiple elements, usingwhileLoop to find the last element, put the penultimate element ofnextSet tonil.tailSet to the penultimate element and return the last elementvalue.remove(after:):deferThe code inside will be inreturnThe statement is run after execution, so inreturn node.next? .valueAfter that, judgenodeIs the next element of omega the last element? If it is, the last element becomes omeganode; Because we deleted itnodeThe next element of theta, sonode.nextTurned out to benode.next? .next.
Access to the 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 codeHere we mean implementing a method: find elements at an index. If currentIndex == index, then the node corresponding to index is currentNode.
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 aindexCorresponding element |
O(I), I is index, because I have to start from scratch, so it’s O(I). |
Achieve SwiftCollectionagreement
Why implement the Collection protocol? First of all, a list can store a series of elements, so it is reasonable to implement the Sequence protocol. In addition, the elements of the linked list are limited, which is also in line with the requirements of the Collection protocol. With the Collection protocol implemented, we can use for-in loops and get a lot of handy methods. Since Collection inherits from Sequence, we can simply implement Collection. Sequence and Collection protocols, you can look at the official documents to understand.
As we can see from apple’s documentation, the implementation of the Collection protocol requires: 1) startIndex and endIndex properties; 2) the realization of subscript; 3) index(after:) implementation. It also requires O(1) time to access the startIndex and endIndex attributes and to access the element by subscript. However, in the linked list, the time complexity of accessing elements through index is O(I), which cannot meet the requirements of the Collection protocol. Therefore, we define a custom Index type to store the corresponding Node, which can meet the requirements of the Collection protocol.
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: Index.rhs: 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)
}
func index(after i: Index) -> Index {
return Index(node: i.node?.next)
}
subscript(index: Index) -> T {
return index.node!.value
}
}
Copy the codeIn the above code, we first define an Index type and then implement the properties and methods required by the Collection protocol.
theLinkedListChange to value type
As anyone familiar with Swift knows, many types in the Swift standard library are value types. Let’s take an array as an example:
var array1 = [1.2.3.4.5]
let array2 = array1
print(array1)
print(array2)
print("======== dividing line ========")
array1.append(6)
print(array1)
print(array2)
/ / the result
array1: [1.2.3.4.5]
array2: [1.2.3.4.5]
= = = = = = = =The divider= = = = = = = =
array1: [1.2.3.4.5.6]
array2: [1.2.3.4.5]
Copy the codeArray1 is defined, array1 is assigned to Array2, and array1 and Array2 are identical. Then I added a 6 to array1, and when I print the result, ARRAY1 has an extra 6, but Array2 has not changed. This proves that the array is a value type.
So back to LinkedList, let’s define it as a Struct type. Under the impression that all Struct types are value types. Let’s imitate the array example and see what happens:
var list1 = LinkedList<Int>()
list1.append(1)
list1.append(2)
list1.append(3)
let list2 = list1
print("list1: \(list1)")
print("list2: \(list2)")
print("======== dividing line ========")
list1.append(4)
print("list1: \(list1)")
print("list2: \(list2)")
/ / the result
list1: 1 -> 2 -> 3
list2: 1 -> 2 -> 3
= = = = = = = =The divider= = = = = = = =
list1: 1 -> 2 -> 3 -> 4
list2: 1 -> 2 -> 3 -> 4
Copy the codeResult: Changing one list affects the other. Our LinkedList is currently a reference type. The reason for this is that the LinkedListNode of our underlying storage node is of type Class and is a reference type.
To fix this problem, we need to make a copy of LinkedListNode in all methods that change the LinkedListNode element before operating on the element, so that multiple LinkedListNode variables do not refer to the same instance. The implementation method is as follows:
mutating func copyNodes(a) {
guard !isKnownUniquelyReferenced(&head) else { return }
guard var oldNode = head else { return }
head = LinkedListNode(value: oldNode.value)
var newNode = head
while let nextOldNode = oldNode.next {
let nextNewNode = LinkedListNode(value: nextOldNode.value)
newNode?.next = nextNewNode
newNode = nextNewNode
oldNode = nextOldNode
}
tail = newNode
}
Copy the codeThis method replicates all the nodes of the list. The guard! IsKnownUniquelyReferenced (& head) else {return} is used to determine whether the current list is only a variable reference, if it is, you do not need to copy; Otherwise, the replication will continue on all nodes.
Add the copyNodes() method to the top of all the methods that change linked list elements: append(), insert(after:), removeLast() and remove(after:). Such as:
mutating func append(_ value: T) {
copyNodes()
guard !isEmpty else {
let node = LinkedListNode(value: value)
head = node
tail = node
return
}
let next = LinkedListNode(value: value)
tail?.next = next
tail = next
}
Copy the codeThis completes a simple linked list.
conclusion
This article mainly explains some features of the list, and a simple implementation of the list. Currently there are few methods to add and remove elements. If you are interested, you can add more methods, such as Append a list, Insert a list, and so on.
Welcome to join my Swift development group: 536353151.
Complete code >>
The resources
Data Structures and Algorithms in Swift — Raywenderlich.com. Click on the link to buy the original.