Singly linked lists
Why do we need singly linked lists
Singly linked lists and arrays are both linear lists, so why do you need to design singly linked lists when you have arrays?
Think in terms of time complexity
A: Linked lists are better than arrays when there are a lot of consecutive inserts or deletes. Because the time complexity of the first linked list is O(n) and the time complexity of subsequent operations is O(1) when continuous insertion or deletion is performed. For arrays, the time complexity of multiple operations is O(n).
The time complexity of search, update, insert and delete operations of array and linked list is compared as follows:
- Array: the time complexity of search and update is O(1); Insert and delete time order n
- Single linked list: search, update, insert, delete time complexity is O(n)
Therefore, if we need to find and update a lot of operations, we recommend using arrays; In the case of continuous insert and delete operations, a linked list is recommended.
2. Think about memory space
Arrays occupy a contiguous chunk of memory, whereas linked lists do not, and can be scattered across memory. Memory can be used more efficiently.
Code implementation
Full code address
First, for a linked list, we define its nodes:
Class LinkNode<E: Equatable> {var val: E var next: LinkNode? init(val: E) { self.val = val } static func == (lhs: LinkNode, rhs: LinkNode) -> Bool {return lhs.val == rhs.val
}
}
Copy the codeFunctions supported by linked lists
Next, we need to define the interface supported by the linked list. Since we may need to create bidirectional and circular lists later, we will implement the generic interface with Protocol:
Protocol LinkedListFunction {associatedType E: Equatable /// Add node to the header of the list /// -parameter newElement: Func Append (atHead newElement: E) /// add a node to the end of the list /// -parameter newElement: add a node func append(atTail newElement: // -parameters: /// -newElement: /// -i: // func insert(_ newElement: E, at I:) Func remove(at index: Int) -> E? Func remove(at index: Int) -> E? Func removeFirst() -> E? Func removeFirst() -> E? Func removeLast() -> E? Func removeLast() -> E? Func removeAll() -parameters: // -parameters: // -newelement: new node func update(at index: Int, _ newElement: E) /// -parameter index: obtain the value of the current index /// - Returns: the value of the current index func index(of index: Int) -> E? /// -parameter Element: The element to be found /// - Returns: if the element is included in the linked listtrueOtherwise, returnfalse
func contains(_ element: E) -> Bool
}
Copy the codeThe structure of linked lists
After defining the nodes and interfaces, let’s implement a single-linked list class:
Class SingleLinkedList<E: Equatable> {/// // List length private()setVar count = 0 var count = 0 /// -parameter index: Returns the current index node private func _node(_ index: Int) -> LinkNode<E>? { guard index < countelse {
return nil
}
if index == 0 { return head }
var curNode = head
var curIndex = index
whilecurIndex > 0 { curNode = curNode? .next curIndex -= 1 }returnFunc linkedListPrint() -> [E] {var nodes = [E]() var curNode = headwhilecurNode ! = nil { nodes.append(curNode! .val) curNode = curNode? .next }print("linkedListPrint ==== \(nodes)")
return nodes
}
}
Copy the codeThe addition of a single linked list
func append(atHead newElement: E) {
if head == nil {
head = LinkNode(val: newElement)
} else {
let newHead = LinkNode(val: newElement)
newHead.next = head
head = newHead
}
count += 1
}
func append(atTail newElement: E) {
if let tail = _node(count - 1) {
tail.next = LinkNode(val: newElement)
count += 1
}
}
func insert(_ newElement: E, at i: Int) {
guard i <= count else { return }
if i == 0 {
append(atHead: newElement)
} else if i == count {
append(atTail: newElement)
} else {
if let curNode = _node(i - 1) {
let insertNode = LinkNode(val: newElement)
insertNode.next = curNode.next
curNode.next = insertNode
count += 1
}
}
}
Copy the codeDelete single linked lists
@discardableResult func remove(at index: Int) -> E? { guard head ! = nilelse { return nil }
guard index < count else { return nil }
if index == 0 {
return removeFirst()
} else if index == count - 1 {
return removeLast()
} else {
let prevTail = _node(index - 1)
letval = prevTail? .next? .val prevTail? .next = prevTail? .next? .next count -= 1return val
}
}
@discardableResult
func removeFirst() -> E? {
letval = head? .valif count == 1 {
head = nil
} else{ head = head? .next } count -= 1returnval } @discardableResult func removeLast() -> E? { guard head ! = nilelse { return nil }
if count == 1 {
letval = head? .val head = nil count -= 1return val
} else {
let prevTail = _node(count - 2)
letval = prevTail? .next? .val prevTail? .next = prevTail? .next? .next count -= 1return val
}
}
func removeAll() {
count = 0
head = nil
}
Copy the codeUpdate, find and include single linked lists
func update(at index: Int, _ newElement: E) {
guard let curNode = _node(index) else { fatalError("Index out of range") }
curNode.val = newElement
}
@discardableResult
func index(of index: Int) -> E? {
return_node(index)? .val } func contains(_ element: E) -> Bool { guard head ! = nilelse { return false }
var curNode = head
whilecurNode ! = nil {ifcurNode! .val == element {return true} curNode = curNode? .next }return false
}
Copy the codetest
The above is all the code for implementing a single linked list with Swift, and the following is the test code to ensure that the code is correct.
struct SingleLinkedListTest {
static func test() {
self.testAppend()
self.testRemove()
self.testUpdate()
self.testContains()
}
static func testAppend() {
let linkedList = SingleLinkedList<Int>()
linkedList.append(atHead: 1)
assert(linkedList.count == 1, "append(atHead newElement: Int) error")
linkedList.append(atTail: 3)
assert(linkedList.count == 2, "append(atTail newElement: Int) error")
linkedList.insert(2, at: 1)
assert(linkedList.count == 3, "insert(_ newElement: Int, at i: Int) error")
let res1 = linkedList.index(of: 1)!
assert(res1 == 2, "index(of index: Int) error")
}
static func testRemove() {
let linkedList = SingleLinkedList<Int>()
linkedList.append(atHead: 1)
linkedList.append(atTail: 3)
linkedList.insert(2, at: 1)
linkedList.removeLast()
assert(linkedList.linkedListPrint() == [1, 2])
linkedList.removeLast()
assert(linkedList.linkedListPrint() == [1])
linkedList.removeLast()
assert(linkedList.linkedListPrint() == [])
linkedList.append(atHead: 1)
linkedList.append(atTail: 3)
linkedList.insert(2, at: 1)
linkedList.removeFirst()
assert(linkedList.linkedListPrint() == [2, 3])
linkedList.removeFirst()
assert(linkedList.linkedListPrint() == [3])
linkedList.removeFirst()
assert(linkedList.linkedListPrint() == [])
linkedList.append(atHead: 1)
linkedList.append(atTail: 3)
linkedList.insert(2, at: 1)
linkedList.remove(at: 1)
assert(linkedList.linkedListPrint() == [1, 3])
linkedList.remove(at: 2)
assert(linkedList.linkedListPrint() == [1, 3])
linkedList.remove(at: 1)
assert(linkedList.linkedListPrint() == [1])
linkedList.remove(at: 0)
assert(linkedList.linkedListPrint() == [])
}
static func testUpdate() {
letlinkedList = SingleLinkedList<Int>() linkedList.append(atHead: 1) linkedList.append(atTail: 3) linkedList.insert(2, at: 1) linkedList.update(at: 1, 5) assert(linkedList.index(of: 1)! = = 5,"update(at index: Int, _ newElement: E) error")
}
static func testContains() {
let linkedList = SingleLinkedList<Int>()
linkedList.append(atHead: 1)
linkedList.append(atTail: 3)
linkedList.insert(2, at: 1)
assert(linkedList.contains(3))
assert(linkedList.contains(1))
assert(linkedList.contains(2))
}
}
Copy the code