LinkedList in swift with node as structure

Question

Can anyone tell me how to create a linked-list in swift with node as structure and linked-list as class.

I tried to create a node Node with reference to itself and faced a error "value type 'Node' cannot have a stored property that references itself"

for resolving it i created one more class Next and now I am unable to proceed further.

Answer 1

A workaround that I can think of is to describe the linked list node as a protocol and then create a struct that confirms that protocol

protocol LinkedNode {
    var value: Int { get }
    var next: LinkedListNode? { get }
}

struct Node: LinkedNode {
    let value: Int
    let next: LinkedListNode?
}

let linkedList = Node(value: 2, next: Node(value: 4, next: nil))

Answer 2

Details

• Xcode 11.3.1, Swift 5.1

Base Interface

Nodeable protocol

import Foundation

protocol Nodeable: class {
    associatedtype Value
    var value: Value { get set }
    var next: Self? { get set }
    init(value: Value, next: Self?)
}

// MARK: Extensions

extension Nodeable where Self.Value: Equatable {
    static func == (lhs: Self, rhs: Self) -> Bool { lhs.value == rhs.value }
}

extension Nodeable where Self: AnyObject {
    var retainCount: Int { CFGetRetainCount(self as CFTypeRef) }
}

extension Nodeable where Self: CustomStringConvertible {
    var description: String { return "{ value: \(value), next: \(next == nil ? "nill" : "exist") }" }
}

LinkedListable protocol

import Foundation

protocol LinkedListable where Node.Value == Value {
    associatedtype Node: Nodeable
    associatedtype Value
    var firstNode: Node? { get set }
    var lastNode: Node? { get set }
    init()
}

extension LinkedListable {
    var firstValue: Value? { return firstNode?.value }
    var lastValue: Value? { return lastNode?.value }
    var isEmpty: Bool { return firstNode == nil }
}

// MARK: Initializers

extension LinkedListable {
    init(_ array: [Value]) {
        self.init()
        array.forEach { append(newLast: $0) }
    }

    init(copyValuesFrom linkedList: Self) {
        self.init()
        if linkedList.isEmpty { return }
        linkedList.forEachNode { append(newLast: $0.value) }
    }

    init(copyReferencesFrom linkedList: Self) {
        self.init()
        firstNode = linkedList.firstNode
        lastNode = linkedList.lastNode
    }
}

// MARK: Iteration

extension LinkedListable {

    func node(at index: Int) -> Node? {
        if isEmpty { return nil }
        var currentIndex = 0
        var resultNode: Node?
        forEachWhile {
            if index == currentIndex { resultNode = $0; return false }
            currentIndex += 1
            return true
        }
        return resultNode
    }

    func forEachWhile(closure: (Node) -> (Bool)) {
        var currentNode = self.firstNode
        while currentNode != nil {
            guard closure(currentNode!) else { return }
            currentNode = currentNode?.next
        }
    }

    func forEachNode(closure: (Node) -> ()) {
        forEachWhile { closure($0); return true }
    }
}

// MARK: Add/Get values

extension LinkedListable {
    func value(at index: Int) -> Value? { node(at: index)?.value }

    // MARK: Add new node to the end of list

    mutating func append(newLast value: Value) {
        let newNode = Node(value: value, next: nil)
        if firstNode == nil {
            firstNode = newNode
            lastNode = firstNode
        } else {
            lastNode?.next = newNode
            lastNode = lastNode?.next
        }
    }
}

LinkedListable protocol extensions

// MARK: CustomStringConvertible

extension LinkedListable where Self: CustomStringConvertible {
    var description: String {
        var values = [String]()
        forEachNode { values.append("\($0.value)") }
        return values.joined(separator: ", ")
    }
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// MARK: ExpressibleByArrayLiteral

extension LinkedListable where Self: ExpressibleByArrayLiteral, ArrayLiteralElement == Value {
    init(arrayLiteral elements: Self.ArrayLiteralElement...) { self.init(elements) }
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// MARK: Sequence

extension LinkedListable where Self: Sequence {
    typealias Iterator = LinkedListableIterator<Node>
    func makeIterator() -> LinkedListableIterator<Node> { return .init(firstNode) }
}

struct LinkedListableIterator<Node>: IteratorProtocol where Node: Nodeable {
    private var currentNode: Node?
    init(_ firstNode: Node?) { self.currentNode = firstNode }
    mutating func next() -> Node.Value? {
        let node = currentNode
        currentNode = currentNode?.next
        return node?.value
    }
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// MARK: Collection

extension LinkedListable where Self: Collection, Self.Index == Int, Self.Element == Value {
    var startIndex: Index { 0 }
    var endIndex: Index {
        guard !isEmpty else { return 0 }
        var currentIndex = 0
        forEachNode { _ in currentIndex += 1 }
        return currentIndex
    }

    func index(after i: Index) -> Index { i+1 }
    subscript(position: Index) -> Element { node(at: position)!.value }
    var isEmpty: Bool { return firstNode == nil }
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////


extension LinkedListable where Self: MutableCollection, Self.Index == Int, Self.Element == Value {

    subscript(position: Self.Index) -> Self.Element {
        get { return node(at: position)!.value }
        set(newValue) { node(at: position)!.value = newValue }
    }
}

Usage

implementation of a Node class

import Foundation

final class LinkedListNode<Value>: Nodeable {
    var value: Value
    var next: LinkedListNode?
    init(value: Value, next: LinkedListNode?) {
        self.value = value
        self.next = next
    }
}

extension LinkedListNode: Equatable, CustomStringConvertible where Value: Equatable {}

Implementation of a List class (option 1)

class BaseLinkedList<Value>: LinkedListable where Value: Equatable {
    typealias Node = LinkedListNode<Value>
    var firstNode: LinkedListNode<Value>?
    weak var lastNode: LinkedListNode<Value>?
    required init() { }
}

Manipulations with List class (option 1)

var linkedList = BaseLinkedList(["one", "two", "three"])
linkedList = BaseLinkedList(copyReferencesFrom: linkedList)
linkedList = BaseLinkedList(copyValuesFrom: linkedList)

var node = linkedList.firstNode!
print("node value: \(node.value) \(String(describing: node.next))")

node = linkedList.lastNode!
print("node value: \(node.value) \(String(describing: node.next))")

print("isEmpty: \(linkedList.isEmpty)")

linkedList.append(newLast: "four")

linkedList.forEachNode { print($0.value) }

linkedList.forEachNode { print($0.value) }

print("node at index 3: \(String(describing: linkedList.node(at: 3)))")
print("value at index 5: \(String(describing: linkedList.value(at: 4)))")

Implementation of a List class (option 2)

class LinkedList<Value>: BaseLinkedList<Value> where Value: Equatable {}
extension LinkedList: CustomStringConvertible, ExpressibleByArrayLiteral, Sequence, Collection, MutableCollection {}

Manipulations with List class (option 2)

var linkedList = LinkedList(arrayLiteral: "one", "two", "three")

print(linkedList)
print(linkedList.map { $0 + "!" })
print(linkedList.reduce("", { "\($0)_\($1)" }))
linkedList[2] = "five"
print(linkedList[2])
print(linkedList.count)

Some unit tests

import XCTest

// MARK: Test basic List functionality

class TestBasicList: XCTestCase {
    typealias LinkedList = BaseLinkedList<Int>
    // typealias Value = Int

    private var linkedList: LinkedList!
    private var possibleValues: [LinkedList.Value] { [1, 2, 3, 4] }

    override func setUp() { linkedList = LinkedList() }

    func testInitListFromArray() {
        TestBasicList.assertCollectionsContainsSameValues(linkedList: LinkedList(possibleValues), array: possibleValues)
    }

    func testInitListByCopyingValuesFromAnotherList() {
        linkedList = .init(possibleValues)
        let copiedLinkedList = LinkedList(copyValuesFrom: linkedList)
        assertCollections(linkedList1: linkedList, linkedList2: copiedLinkedList, containEqualValues: true)
        assertCollections(linkedList1: linkedList, linkedList2: copiedLinkedList, containsSameReferencesToNodes: false)
    }

    func testInitListByCopyingElementsReferencesFromAnotherList() {
        linkedList = .init(possibleValues)
        let copiedLinkedList = LinkedList(copyReferencesFrom: linkedList)
        assertCollections(linkedList1: linkedList, linkedList2: copiedLinkedList, containEqualValues: true)
        assertCollections(linkedList1: linkedList, linkedList2: copiedLinkedList, containsSameReferencesToNodes: true)
    }

    func testPushFunctionality() {
        possibleValues.forEach { linkedList.append(newLast: $0) }
        TestBasicList.assertCollectionsContainsSameValues(linkedList: linkedList, array: possibleValues)
    }

    func testRandomAccess() {
        linkedList = .init(possibleValues)
        (0 ..< possibleValues.count).forEach {
            XCTAssertEqual(possibleValues[$0], linkedList.node(at: $0)?.value)
        }
    }

    private func assertCollections(linkedList1: LinkedList, linkedList2: LinkedList, containEqualValues: Bool) {
        var values1 = [LinkedList.Value]()
        linkedList1.forEachNode { values1.append($0.value) }

        var values2 = [LinkedList.Value]()
        linkedList2.forEachNode { values2.append($0.value) }

        if containEqualValues {
            XCTAssertEqual(values1, values2)
        } else {
            XCTAssertNotEqual(values1, values2)
        }
    }

    private func assertCollections(linkedList1: LinkedList, linkedList2: LinkedList, containsSameReferencesToNodes: Bool) {
        var values1 = [LinkedList.Node]()
        linkedList1.forEachNode { values1.append($0) }

        var values2 = [LinkedList.Node]()
        linkedList2.forEachNode { values2.append($0) }

        var areSame: Bool!
        for i in 0 ..< values1.count {
            areSame = values1[i] === values2[i]
            if containsSameReferencesToNodes {
                XCTAssertTrue(areSame)
            } else {
                XCTAssertFalse(areSame)
            }
        }
    }
}

extension TestBasicList {
    class func assertCollectionsContainsSameValues<List: LinkedListable>(linkedList: List, array: [List.Value]) where List.Value: Equatable  {
        var values = [List.Value]()
        linkedList.forEachNode { values.append($0.value) }
        XCTAssertEqual(values, array)
    }
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// MARK: Sequence

class LinkedListSequence<Value>: BaseLinkedList<Value>, Sequence where Value: Equatable {}

protocol LinkedListSequenceTestable {
    typealias Value = Int
    typealias LinkedList = LinkedListSequence<Value>
    var linkedList: LinkedList { get set }
    var possibleValues: [Value] { get}
}

extension LinkedListSequenceTestable {

    func _testFilter() {
        XCTAssertEqual(linkedList.filter ({ $0 % 2 == 0 }),
                       possibleValues.filter({ $0 % 2 == 0 }))
    }

    func _testMap() {
        guard let num = possibleValues.first else { return }
        XCTAssertEqual(linkedList.map({ $0 + num}), possibleValues.map({ $0 + num}))
    }

    func _testCompactMap() {
        let array1 = linkedList.compactMap { value -> String? in
            if value % 2 != 0 { return "\(value)" }
            return nil
        }

        let array2 = possibleValues.compactMap { value -> String? in
            if value % 2 != 0 { return "\(value)" }
            return nil
        }
        XCTAssertEqual(array1, array2)
    }

    func _testReduce() {
        let result1 = linkedList.reduce(LinkedList.Element()) { $0 + $1 }
        let result2 = possibleValues.reduce(LinkedList.Element()) { $0 + $1 }
        XCTAssertEqual(result1, result2)
    }

    func _testForEach() {
        var values1 = [LinkedList.Value]()
        linkedList.forEach { values1.append($0) }

        var values2 = [LinkedList.Value]()
        possibleValues.forEach { values2.append($0) }

        XCTAssertEqual(values1, values2)
    }
}

class TestLinkedListSequence_nonEmpty: XCTestCase, LinkedListSequenceTestable {

    var linkedList = LinkedList()
    var possibleValues: [Value] { [1, 2, 3, 4] }

    override func setUp() { linkedList = LinkedList(possibleValues) }

    func testFilter() { _testFilter() }
    func testMap() { _testMap() }
    func testCompactMap() { _testCompactMap() }
    func testReduce() { _testReduce() }
    func testForEach() { _testForEach() }
}

class TestLinkedListSequence_oneElement: TestLinkedListSequence_nonEmpty {
    override var possibleValues: [Value] { [1] }
}

class TestLinkedListSequence_empty: TestLinkedListSequence_nonEmpty {
    override var possibleValues: [Value] { [] }
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// MARK: Collection

class LinkedListCollection<Value>: BaseLinkedList<Value>, Sequence, Collection where Value: Equatable {}

protocol LinkedListCollectionTestable {
    associatedtype Value: Equatable
    typealias LinkedList = LinkedListCollection<Value>
    var linkedList: LinkedList { get set }
    var possibleValues: [Value] { get}
}

extension LinkedListCollectionTestable {

    func _testCount() {
        XCTAssertEqual(linkedList.count, possibleValues.count)
    }

    func _testIsEmpty() {
        XCTAssertEqual(linkedList.isEmpty, possibleValues.isEmpty)
        XCTAssertEqual(LinkedList().isEmpty, [].isEmpty)
    }

    func _testIndexes() {
        for i in 0 ..< linkedList.count {
            XCTAssertEqual(linkedList.index(after: i), possibleValues.index(after: i))
        }
    }
}
class TestLinkedListCollection_nonEmpty: XCTestCase, LinkedListCollectionTestable {
    typealias LinkedList = LinkedListCollection<Int>
    var linkedList = LinkedList()
    var possibleValues: [LinkedList.Value] { [1, 2, 3, 4] }
    override func setUp() { linkedList = LinkedList(possibleValues) }

    func testCount() { _testCount() }
    func testIsEmpty() { _testIsEmpty() }
    func testIndexes() { _testIndexes() }
}

class TestLinkedListCollection_oneElement: TestLinkedListCollection_nonEmpty {
    override var possibleValues: [LinkedList.Value] { [1] }
}

class TestLinkedListCollection_empty: TestLinkedListCollection_nonEmpty {
    override var possibleValues: [LinkedList.Value] { [] }
}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

// MARK: RangeReplaceableCollection

class LinkedListMutableCollection<Value>: BaseLinkedList<Value>, Sequence, Collection, MutableCollection where Value: Equatable & Comparable {}

protocol LinkedListMutableCollectionTestable {
    associatedtype Value: Equatable & Comparable
    typealias LinkedList = LinkedListMutableCollection<Value>
    var linkedList: LinkedList { get set }
    var possibleValues: [Value] { get}
}

extension LinkedListMutableCollectionTestable {
    func _testSorted() {
        XCTAssertEqual(linkedList.sorted(by: { $0 > $1 }),
                       possibleValues.sorted(by: { $0 > $1 }))

    }

    func _testSubscriptReading() {
        for (index, value) in possibleValues.enumerated() {
            XCTAssertEqual(linkedList[index], value)
        }
    }

    func _testSubscriptWriting() {
        var list = linkedList
        var testArray = possibleValues
        TestBasicList.assertCollectionsContainsSameValues(linkedList: linkedList, array: testArray)
        for (index, value) in possibleValues.reversed().enumerated() {
            testArray[index] = value
            list[index] = value
            XCTAssertEqual(linkedList[index], testArray[index])
        }
        print(testArray)
        TestBasicList.assertCollectionsContainsSameValues(linkedList: linkedList, array: testArray)
    }
}

class TestLinkedListMutableCollection_nonEmptyCollection: XCTestCase, LinkedListMutableCollectionTestable {
    typealias LinkedList = LinkedListMutableCollection<Int>
    var linkedList = LinkedList()
    var possibleValues: [LinkedList.Value] { [1, 3, 2, 4] }
    override func setUp() { linkedList = LinkedList(possibleValues) }

    func testSorted() { _testSorted() }
    func testSubscriptReading() { _testSubscriptReading() }
    func testSubscriptWriting() { _testSubscriptWriting() }
}

class TestLinkedListMutableCollection_oneElement: TestLinkedListMutableCollection_nonEmptyCollection {
    override var possibleValues: [LinkedList.Value] { [1] }
}

class TestLinkedListMutableCollection_empty: TestLinkedListMutableCollection_nonEmptyCollection {
    override var possibleValues: [LinkedList.Value] { [] }
}

Answer 3

Custom LinkedList Type

Xcode 10.2.1, Swift 5.0

My LinkedList type implements all of the following protocols:

• CustomStringConvertible
• ExpressibleByArrayLiteral
• Sequence
• Collection
• MutableCollection
• RangeReplaceableCollection
• BidirectionalCollection

As well, it keeps its node type private so the user never needs to know anything of its existence.

This implementation is a doubly linked list so to efficiently enable bidirectional traversal.

Code:

public struct LinkedList<Element> {

    private var headNode: Node?
    private var tailNode: Node?
    public private(set) var count: Int = 0
    private var id = ID()
    public init() { }

    fileprivate class ID {
        init() { }
    }
}

//MARK: - LinkedList Node
extension LinkedList {

    fileprivate class Node {
        public var value: Element
        public var next: Node?
        public weak var previous: Node?

        public init(value: Element) {
            self.value = value
        }
    }

}

//MARK: - Initializers
public extension LinkedList {

    private init(_ nodeChain: (head: Node, tail: Node, count: Int)?) {
        guard let chain = nodeChain else {
            return
        }
        headNode = chain.head
        tailNode = chain.tail
        count = chain.count
    }

    init<S>(_ sequence: S) where S: Sequence, S.Element == Element {
        if let linkedList = sequence as? LinkedList<Element> {
            self = linkedList
        } else {
            self = LinkedList(chain(of: sequence))
        }
    }

}

//MARK: Chain of Nodes
extension LinkedList {
    // Creates a chain of nodes from a sequence. Returns `nil` if the sequence is empty.
    private func chain<S>(of sequence: S) -> (head: Node, tail: Node, count: Int)? where S: Sequence, S.Element == Element {
        var iterator = sequence.makeIterator()
        var head, tail: Node
        var count = 0
        guard let firstValue = iterator.next() else {
            return nil
        }

        var currentNode = Node(value: firstValue)
        head = currentNode
        count = 1

        while let nextElement = iterator.next() {
            let nextNode = Node(value: nextElement)
            currentNode.next = nextNode
            nextNode.previous = currentNode
            currentNode = nextNode
            count += 1
        }
        tail = currentNode
        return (head: head, tail: tail, count: count)
    }
}

//MARK: - Copy Nodes
extension LinkedList {

    private mutating func copyNodes(settingNodeAt index: Index, to value: Element) {

        var currentIndex = startIndex
        var currentNode = Node(value: currentIndex == index ? value : currentIndex.node!.value)
        let newHeadNode = currentNode
        currentIndex = self.index(after: currentIndex)

        while currentIndex < endIndex {
            let nextNode = Node(value: currentIndex == index ? value : currentIndex.node!.value)
            currentNode.next = nextNode
            nextNode.previous = currentNode
            currentNode = nextNode
            currentIndex = self.index(after: currentIndex)
        }
        headNode = newHeadNode
        tailNode = currentNode
    }

    @discardableResult
    private mutating func copyNodes(removing range: Range<Index>) -> Range<Index> {

        id = ID()
        var currentIndex = startIndex

        while range.contains(currentIndex) {
            currentIndex = index(after: currentIndex)
        }

        guard let headValue = currentIndex.node?.value else {
            self = LinkedList()
            return endIndex..<endIndex
        }

        var currentNode = Node(value: headValue)
        let newHeadNode = currentNode
        var newCount = 1

        var removedRange: Range<Index> = Index(node: currentNode, offset: 0, id: id)..<Index(node: currentNode, offset: 0, id: id)
        currentIndex = index(after: currentIndex)

        while currentIndex < endIndex {
            guard !range.contains(currentIndex) else {
                currentIndex = index(after: currentIndex)
                continue
            }

            let nextNode = Node(value: currentIndex.node!.value)
            if currentIndex == range.upperBound {
                removedRange = Index(node: nextNode, offset: newCount, id: id)..<Index(node: nextNode, offset: newCount, id: id)
            }
            currentNode.next = nextNode
            nextNode.previous = currentNode
            currentNode = nextNode
            newCount += 1
            currentIndex = index(after: currentIndex)

        }
        if currentIndex == range.upperBound {
            removedRange = Index(node: nil, offset: newCount, id: id)..<Index(node: nil, offset: newCount, id: id)
        }
        headNode = newHeadNode
        tailNode = currentNode
        count = newCount
        return removedRange
    }

}


//MARK: - Computed Properties
public extension LinkedList {
    var head: Element? {
        return headNode?.value
    }

    var tail: Element? {
        return tailNode?.value
    }
}

//MARK: - Sequence Conformance
extension LinkedList: Sequence {

    public typealias Element = Element

    public __consuming func makeIterator() -> Iterator {
        return Iterator(node: headNode)
    }

    public struct Iterator: IteratorProtocol {

        private var currentNode: Node?

        fileprivate init(node: Node?) {
            currentNode = node
        }

        public mutating func next() -> Element? {
            guard let node = currentNode else {
                return nil
            }
            currentNode = node.next
            return node.value
        }

    }
}

//MARK: - Collection Conformance
extension LinkedList: Collection {

    public var startIndex: Index {
        return Index(node: headNode, offset: 0, id: id)
    }

    public var endIndex: Index {
        return Index(node: nil, offset: count, id: id)
    }

    public var first: Element? {
        return head
    }

    public var isEmpty: Bool {
        return count == 0
    }

    public func index(after i: Index) -> Index {
        precondition(i.listID === self.id, "LinkedList index is invalid")
        precondition(i.offset != endIndex.offset, "LinkedList index is out of bounds")
        return Index(node: i.node?.next, offset: i.offset + 1, id: id)
    }

    public struct Index: Comparable {
        fileprivate weak var node: Node?
        fileprivate var offset: Int
        fileprivate weak var listID: ID?

        fileprivate init(node: Node?, offset: Int, id: ID) {
            self.node = node
            self.offset = offset
            self.listID = id
        }

        public static func ==(lhs: Index, rhs: Index) -> Bool {
            return lhs.offset == rhs.offset
        }

        public static func <(lhs: Index, rhs: Index) -> Bool {
            return lhs.offset < rhs.offset
        }
    }

}


//MARK: - MutableCollection Conformance
extension LinkedList: MutableCollection {

    public subscript(position: Index) -> Element {
        get {
            precondition(position.listID === self.id, "LinkedList index is invalid")
            precondition(position.offset != endIndex.offset, "Index out of range")
            guard let node = position.node else {
                preconditionFailure("LinkedList index is invalid")
            }
            return node.value
        }
        set {
            precondition(position.listID === self.id, "LinkedList index is invalid")
            precondition(position.offset != endIndex.offset, "Index out of range")

            // Copy-on-write semantics for nodes
            if !isKnownUniquelyReferenced(&headNode) {
                copyNodes(settingNodeAt: position, to: newValue)
            } else {
                position.node?.value = newValue
            }
        }
    }
}



//MARK: LinkedList Specific Operations
public extension LinkedList {

    mutating func prepend(_ newElement: Element) {
        replaceSubrange(startIndex..<startIndex, with: CollectionOfOne(newElement))
    }

    mutating func prepend<S>(contentsOf newElements: __owned S) where S: Sequence, S.Element == Element {
        replaceSubrange(startIndex..<startIndex, with: newElements)
    }

    @discardableResult
    mutating func popFirst() -> Element? {
        if isEmpty {
            return nil
        }
        return removeFirst()
    }

    @discardableResult
    mutating func popLast() -> Element? {
        if isEmpty {
            return nil
        }
        return removeLast()
    }
}

//MARK: - BidirectionalCollection Conformance
extension LinkedList: BidirectionalCollection {
    public var last: Element? {
        return tail
    }

    public func index(before i: Index) -> Index {
        precondition(i.listID === self.id, "LinkedList index is invalid")
        precondition(i.offset != startIndex.offset, "LinkedList index is out of bounds")
        if i.offset == count {
            return Index(node: tailNode, offset: i.offset - 1, id: id)
        }
        return Index(node: i.node?.previous, offset: i.offset - 1, id: id)
    }

}

//MARK: - RangeReplaceableCollection Conformance
extension LinkedList: RangeReplaceableCollection {
    public mutating func append<S>(contentsOf newElements: __owned S) where S: Sequence, Element == S.Element {
        replaceSubrange(endIndex..<endIndex, with: newElements)
    }

    public mutating func replaceSubrange<S, R>(_ subrange: R, with newElements: __owned S) where S: Sequence, R: RangeExpression, Element == S.Element, Index == R.Bound {

        var range = subrange.relative(to: indices)
        precondition(range.lowerBound.listID === id && range.upperBound.listID === id, "LinkedList range of indices are invalid")
        precondition(range.lowerBound >= startIndex && range.upperBound <= endIndex, "Subrange bounds are out of range")

        // If range covers all elements and the new elements are a LinkedList then set references to it
        if range.lowerBound == startIndex, range.upperBound == endIndex, let linkedList = newElements as? LinkedList {
            self = linkedList
            return
        }

        var newElementsCount = 0

        // There are no new elements, so range indicates deletion
        guard let nodeChain = chain(of: newElements) else {

            // If there is nothing in the removal range
            // This also covers the case that the linked list is empty because this is the only possible range
            guard range.lowerBound != range.upperBound else {
                return
            }

            // Deletion range spans all elements
            if range.lowerBound == startIndex && range.upperBound == endIndex {
                headNode = nil
                tailNode = nil
                count = 0
                return
            }

            // Copy-on-write semantics for nodes and remove elements in range
            guard isKnownUniquelyReferenced(&headNode) else {
                copyNodes(removing: range)
                return
            }

            // Update count after mutation to preserve startIndex and endIndex validity
            defer {
                count = count - (range.upperBound.offset - range.lowerBound.offset)
            }

            // Move head up if deletion starts at start index
            if range.lowerBound == startIndex {
                // Can force unwrap node since the upperBound is not the end index
                headNode = range.upperBound.node!
                headNode!.previous = nil

                // Move tail back if deletion ends at end index
            } else if range.upperBound == endIndex {
                // Can force unwrap since lowerBound index must have an associated element
                tailNode = range.lowerBound.node!.previous
                tailNode!.next = nil

                // Deletion range is in the middle of the linked list
            } else {
                // Can force unwrap all bound nodes since they both must have elements
                range.upperBound.node!.previous = range.lowerBound.node!.previous
                range.lowerBound.node!.previous!.next = range.upperBound.node!
            }

            return
        }

        // Obtain the count of the new elements from the node chain composed from them
        newElementsCount = nodeChain.count

        // Replace entire content of list with new elements
        if range.lowerBound == startIndex && range.upperBound == endIndex {
            headNode = nodeChain.head
            tailNode = nodeChain.tail
            count = nodeChain.count
            return
        }

        // Copy-on-write semantics for nodes before mutation
        if !isKnownUniquelyReferenced(&headNode) {
            range = copyNodes(removing: range)
        }

        // Update count after mutation to preserve startIndex and endIndex validity
        defer {
            count += nodeChain.count - (range.upperBound.offset - range.lowerBound.offset)
        }

        // Prepending new elements
        guard range.upperBound != startIndex else {
            headNode?.previous = nodeChain.tail
            nodeChain.tail.next = headNode
            headNode = nodeChain.head
            return
        }

        // Appending new elements
        guard range.lowerBound != endIndex else {
            tailNode?.next = nodeChain.head
            nodeChain.head.previous = tailNode
            tailNode = nodeChain.tail
            return
        }

        if range.lowerBound == startIndex {
            headNode = nodeChain.head
        }
        if range.upperBound == endIndex {
            tailNode = nodeChain.tail
        }

        range.lowerBound.node!.previous!.next = nodeChain.head
        range.upperBound.node!.previous = nodeChain.tail
    }

}

//MARK: - ExpressibleByArrayLiteral Conformance
extension LinkedList: ExpressibleByArrayLiteral {
    public typealias ArrayLiteralElement = Element

    public init(arrayLiteral elements: ArrayLiteralElement...) {
        self.init(elements)
    }
}

//MARK: - CustomStringConvertible Conformance
extension LinkedList: CustomStringConvertible {
    public var description: String {
        return "[" + lazy.map { "\($0)" }.joined(separator: ", ") + "]"
    }
}

//MARK: - Equatable Conformance
extension LinkedList: Equatable where Element: Equatable {
    public static func ==(lhs: LinkedList<Element>, rhs: LinkedList<Element>) -> Bool {
        for (a, b) in zip(lhs, rhs) {
            guard a == b else {
                return false
            }
        }
        return true
    }
}

If you'd like to use this type fully-documented in your own project, feel free to download it or add it as a dependency with Swift PM by checking out my LinkedList GitHub repository.

Answer 4

Checked on XCode 10 playground - Swift 4.2

 class Node {

        let value: Int
        var next: Node?

        init(value: Int, next: Node? = nil) {
            self.value = value
            self.next = next
        }

    }

    class LinkedList {

        let head: Node

        init(node: Node) {
            self.head = node
        }

        convenience init(nodeValue: Int) {
            self.init(node: Node(value: nodeValue))
        }

        func addNode(node: Node) {
            var current: Node = self.head
            while current.next != nil {
                current = current.next!
            }
            current.next = node
        }

        func addNode(withValue value: Int) {
            self.addNode(node: Node(value: value))
        }

        func traverse() -> [Int]{
            var results: [Int] = []
            var current: Node = self.head
            while current.next != nil {
                current = current.next!
                results.append(current.value)
            }
            return results
        }

    }


    let list = LinkedList(nodeValue: 4)
    list.addNode(withValue: 3)
    list.addNode(withValue: 8)
    list.addNode(withValue: 8)
    list.addNode(withValue: 8)
    list.addNode(withValue: 8)
    list.traverse()

Answer 5

Hopefully I can clarify a few points.

Can anyone tell me how to create a linked-list in swift with node as structure and linked-list as class.

The node essentially is the structure. As other people have pointed out, a linked list is nothing more than a very basic data type (often called a Node) that holds a value and a reference to another Node.

The code posted above is a linked list:

class Node {

    let value: Int
    var next: Node?

    init(value: Int, next: Node? = nil) {
        self.value = value
        self.next = next
    }
}

Think of a link in a chain. This is your Node.

Think of a couple of links together. This is your linked list.

My point here is that there is nothing additional. By having the ability to make a single Node, you have the ability to make a linked list (just a bunch of Nodes connected).

I tried to create a node Node with reference to itself and faced a error "value type 'Node' cannot have a stored property that references itself"

Others have explained why this won't work.

for resolving it i created one more class Next and now I am unable to proceed further.

Please don't do this. Your next node is just another Node. This is completely unnecessary.

Sometimes you will see a linked list class that holds a Node. This is just to help you manipulate the list a little easier. So when you say

linked-list as class

I'm pretty sure you're just referring to a collection of functions that help manipulate your list. These can just as easily be standalone functions that take a Node and operate on it.

For instance to add a link to the chain you can have a function add(value: Value, to list: Node). A function like this may or may not exist on some arbitrary LinkedList class. It often does but probably should not.

func append(_ node: Node, to list: Node) {
    var current = list
    while let nextNode = current.next {
        current = nextNode
    }
    current.next = node
}

Hope this helps!

Answer 6

You can not make node as a "struct" since Swift treats Struct and Enums as value types and Classes as reference type.

When you make the LinkedList Class you would very likely create a reference to your node structure. Now struct being a value type, capturing self for value types is dangerous practice and discouraged.

Therefore I would suggest you to create Node as Class and make use of the various access specifiers in Swift to achieve the abstraction you are trying to.

For more details on capturing self in value types you can refer to https://github.com/Wolox/ios-style-guide/blob/master/rules/avoid-struct-closure-self.md.

Answer 7

This is not really a good question for Stack Overflow, but I will answer anyway. Here is a super basic implementation of a singly linked list:

class Node {

    let value: Int
    var next: Node?

    init(value: Int, next: Node? = nil) {
        self.value = value
        self.next = next
    }

}

class LinkedList {

    let head: Node

    init(node: Node) {
        self.head = node
    }

    convenience init(nodeValue: Int) {
        self.init(node: Node(value: nodeValue))
    }

    func addNode(node: Node) {
        var current: Node = self.head
        while current.next != nil {
            current = current.next!
        }
        current.next = node
    }

    func addNode(withValue value: Int) {
        self.addNode(node: Node(value: value))
    }

}

let list = LinkedList(nodeValue: 4)
list.addNode(withValue: 3)
list.addNode(withValue: 8)
//The list is now [ 4 ]->[ 3 ]->[ 8 ]