Last active
September 14, 2023 03:53
-
-
Save staticVoidMan/38e2ce79b2e37836d669d43ff7959d9c to your computer and use it in GitHub Desktop.
Data Structure - Linked List
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Node<T: Equatable> { | |
| let value: T | |
| var next: Node<T>? | |
| init(_ value: T, next: Node<T>? = nil) { | |
| self.value = value | |
| self.next = next | |
| } | |
| } | |
| extension Node: CustomStringConvertible { | |
| var description: String { "\(value)" } | |
| } | |
| class LinkedList<T: Equatable> { | |
| var root: Node<T>? | |
| var last: Node<T>? | |
| init(root: Node<T>? = nil) { | |
| self.root = root | |
| self.last = root | |
| } | |
| func insert(_ node: Node<T>) { | |
| if root == nil { | |
| root = node | |
| last = node | |
| } else { | |
| last?.next = node | |
| last = node | |
| } | |
| } | |
| func delete(_ value: T) { | |
| let (previous, current) = _find(value) | |
| previous?.next = current?.next | |
| } | |
| private func _find(_ value: T) -> (previous: Node<T>?, node: Node<T>?) { | |
| var current: Node<T>? = root | |
| var previous: Node<T>? = nil | |
| while current != nil { | |
| if current?.value == value { | |
| break | |
| } | |
| previous = current | |
| current = current?.next | |
| } | |
| return (previous, current) | |
| } | |
| func find(_ value: T) -> Node<T>? { | |
| _find(value).node | |
| } | |
| func reverse() { | |
| var current: Node<T>? = root | |
| var previous: Node<T>? = nil | |
| var next: Node<T>? = nil | |
| while current != nil { | |
| next = current?.next | |
| current?.next = previous | |
| previous = current | |
| current = next | |
| } | |
| root = previous | |
| } | |
| } | |
| extension LinkedList: CustomStringConvertible { | |
| var description: String { | |
| guard let root else { return "" } | |
| var result = "" | |
| var current: Node<T>? = root | |
| while current != nil { | |
| result += "\(current!.value) -> " | |
| current = current?.next | |
| } | |
| return result + "nil" | |
| } | |
| } | |
| let list = LinkedList<Int>() | |
| list.insert(Node(0)) | |
| list.insert(Node(1)) | |
| list.insert(Node(2)) | |
| list.insert(Node(3)) | |
| print(list) | |
| print(list.find(2) ?? Node(-1)) | |
| list.delete(2) | |
| print(list.find(2) ?? Node(-1)) | |
| print(list) | |
| list.reverse() | |
| print(list) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment