Doubly-linked list/Definition: Difference between revisions

Content added Content deleted

Inline

@@ Line 4,151: / Line 4,151: @@
 =={{header|Swift}}==
-<syntaxhighlight lang="text">typealias NodePtr<T> = UnsafeMutablePointer<Node<T>>
+<syntaxhighlight lang="Swift">typealias NodePtr<T> = UnsafeMutablePointer<Node<T>>
 class Node<T> {
@@ Line 4,300: / 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}}==