Doubly-linked list/Definition: Difference between revisions
m
→{{header|Wren}}: Minor tidy
(Added XPL0 example.) |
m (→{{header|Wren}}: Minor tidy) |
||
| (One intermediate revision by one other user not shown) | |||
Line 4,151:
=={{header|Swift}}==
<syntaxhighlight lang="
class Node<T> {
Line 4,300:
[0, 1, 2, 3, 4, 5, 100, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 100, 6, 7, 8, 9]</pre>
{{works with|Swift|5.8}}
This version uses classes instead of structs and unsafe pointers. It thus obviates the need for explicit memory management and i, I think, a little cleaner.
Loops are avoided by handling the management of all links within the class itself.
<syntaxhighlight lang="Swift">public class DoublyLinkedList<Element>
{
public class Entry
{
// Each entry owns the next entry
public fileprivate(set) weak var prev: Entry?
public fileprivate(set) var next: Entry?
public let item: Element
init(prev: Entry? = nil, next: Entry? = nil, item: Element)
{
self.prev = prev
self.next = next
self.item = item
}
}
public init(){}
public private(set) var headEntry: Entry? = nil
public private(set) var tailEntry: Entry? = nil
public var head: Element? { headEntry?.item }
public var tail: Element? { tailEntry?.item }
public func append(item: Element)
{
let newEntry = Entry(prev: tailEntry, item: item)
if let tailEntry
{
tailEntry.next = newEntry
}
else
{
headEntry = newEntry
}
tailEntry = newEntry
}
public func prepend(item: Element)
{
let newEntry = Entry(next: headEntry, item: item)
if let headEntry
{
headEntry.prev = newEntry
}
else
{
tailEntry = newEntry
}
headEntry = newEntry
}
public func insert(item: Element, before: Entry)
{
let newEntry = Entry(next: before, item: item)
if let previous = before.prev
{
newEntry.prev = previous
previous.next = newEntry
}
else
{
headEntry = newEntry
}
newEntry.next = before
}
public func insert(item: Element, after: Entry)
{
let newEntry = Entry(prev: after, item: item)
if let next = after.next
{
newEntry.next = next
next.prev = newEntry
}
else
{
tailEntry = newEntry
}
after.next = newEntry
}
@discardableResult public func remove(entry: Entry) -> Element
{
if let prevEntry = entry.prev
{
prevEntry.next = entry.next
}
else
{
headEntry = entry.next
}
if let nextEntry = entry.next
{
nextEntry.prev = entry.prev
}
else
{
tailEntry = entry.prev
}
entry.prev = nil
entry.next = nil
return entry.item
}
}
extension DoublyLinkedList: CustomStringConvertible where Element: CustomStringConvertible
{
public var description: String
{
var array: [Element] = []
var currentEntry = headEntry
while let thisEntry = currentEntry
{
array.append(thisEntry.item)
currentEntry = thisEntry.next
}
return "[" + array.map({ $0.description }).joined(separator: ", ") + "]"
}
}
let list = DoublyLinkedList<Int>()
for i in 0 ... 5
{
list.append(item: i)
}
for i in 10 ... 15
{
list.prepend(item: i)
}
if let insertPoint = list.headEntry?.next?.next
{
list.insert(item: 99, after: insertPoint)
}
print("\(list)")
if let removePoint = list.headEntry?.next?.next?.next
{
let item = list.remove(entry: removePoint)
}
print("\(list)")
</syntaxhighlight>
{{out}}
<pre>
[15, 14, 13, 99, 12, 11, 10, 0, 1, 2, 3, 4, 5]
[15, 14, 13, 12, 11, 10, 0, 1, 2, 3, 4, 5]
</pre>
=={{header|Tcl}}==
Line 4,548 ⟶ 4,704:
{{libheader|Wren-llist}}
The DLinkedList class in the above module is a generic doubly-linked list and is implemented in such a way that circular loops are not possible. We therefore use it here.
<syntaxhighlight lang="
var dll = DLinkedList.new()
| |||