Anonymous user
Doubly-linked list/Definition: Difference between revisions
Add swift
No edit summary |
(Add swift) |
||
Line 3,103:
=={{header|Ruby}}==
See [[Doubly-Linked List (element)#Ruby]], [[Doubly-Linked List (element insertion)#Ruby]] and [[Doubly-Linked List (traversal)#Ruby]]
=={{header|Swift}}==
<lang>typealias NodePtr<T> = UnsafeMutablePointer<Node<T>>
class Node<T> {
var value: T
fileprivate var prev: NodePtr<T>?
fileprivate var next: NodePtr<T>?
init(value: T, prev: NodePtr<T>? = nil, next: NodePtr<T>? = nil) {
self.value = value
self.prev = prev
self.next = next
}
}
struct DoublyLinkedList<T> {
fileprivate var head: NodePtr<T>?
fileprivate var tail: NodePtr<T>?
@discardableResult
mutating func insert(_ val: T, at: InsertLoc<T> = .last) -> Node<T> {
let node = NodePtr<T>.allocate(capacity: 1)
node.initialize(to: Node(value: val))
if head == nil && tail == nil {
head = node
tail = node
return node.pointee
}
switch at {
case .first:
node.pointee.next = head
head?.pointee.prev = node
head = node
case .last:
node.pointee.prev = tail
tail?.pointee.next = node
tail = node
case let .after(insertNode):
var n = head
while n != nil {
if n!.pointee !== insertNode {
n = n?.pointee.next
continue
}
node.pointee.prev = n
node.pointee.next = n!.pointee.next
n!.pointee.next = node
if n == tail {
tail = node
}
break
}
}
return node.pointee
}
@discardableResult
mutating func remove(_ node: Node<T>) -> T? {
var n = head
while n != nil {
if n!.pointee !== node {
n = n?.pointee.next
continue
}
if n == head {
n?.pointee.next?.pointee.prev = nil
head = n?.pointee.next
} else if n == tail {
n?.pointee.prev?.pointee.next = nil
tail = n?.pointee.prev
} else {
n?.pointee.prev?.pointee.next = n?.pointee.next
n?.pointee.next?.pointee.prev = n?.pointee.prev
}
break
}
if n == nil {
return nil
}
defer {
n?.deinitialize(count: 1)
n?.deallocate()
}
return n?.pointee.value
}
enum InsertLoc<T> {
case first
case last
case after(Node<T>)
}
}
extension DoublyLinkedList: CustomStringConvertible {
var description: String {
var res = "["
var node = head
while node != nil {
res += "\(node!.pointee.value), "
node = node?.pointee.next
}
return (res.count > 1 ? String(res.dropLast(2)) : res) + "]"
}
}
var list = DoublyLinkedList<Int>()
var node: Node<Int>!
for i in 0..<10 {
let insertedNode = list.insert(i)
if i == 5 {
node = insertedNode
}
}
print(list)
list.insert(100, at: .after(node!))
print(list)
list.remove(node!)
print(list)</lang>
{{out}}
<pre>[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 100, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 100, 6, 7, 8, 9]</pre>
=={{header|Tcl}}==
| |||