无法将整个双链接列表元素打印到控制台

Question

我在 Swift 中实现了一个双向链表。一切都很顺利。链接设置得很好，我可以使用 nextNode 和 previousNode 属性访问每个元素。但是当我将列表打印到控制台时，它只是打印出列表的头部。

import Foundation
struct DoublyLinkedList<DataItem> {
    fileprivate var head : Node<DataItem>?
    fileprivate var tail : Node<DataItem>?
    var isEmpty : Bool {
        return head == nil
    }
    //to add at the beginning
    mutating func InsertAtBeginning(_ dataItem : DataItem) {
        let node = Node(dataItem: dataItem, nextNode: head, previousNode: nil)
        head?.previousNode = node
        head = node
        if tail == nil {
            tail = head
        }
    }
    //to add at the end
    mutating func insertAtEnd(_ dataItem : DataItem) {
        guard !isEmpty else {
            InsertAtBeginning(dataItem)
            return
        }
        let newNode = Node(dataItem: dataItem, nextNode: nil, previousNode: tail)
        tail?.nextNode = newNode
        //newNode.previousNode = tail
        tail = newNode
    }
}
extension DoublyLinkedList : CustomStringConvertible {
    var description : String {
        guard let doublyLinkedListHead = head else { return "UnderFlow"}
        return String(describing: doublyLinkedListHead)
    }
}
class Node<DataItem> {
    var dataItem : DataItem
    var nextNode : Node?
    var previousNode : Node?
    init(dataItem : DataItem , nextNode : Node? = nil , previousNode : Node? = nil) {
        self.dataItem = dataItem
        self.nextNode = nextNode
        self.previousNode = previousNode
    }
}
extension Node : CustomStringConvertible {
    var description: String {
        return "(dataItem) "
    }
}
var list = DoublyLinkedList<Int>()
list.InsertAtBeginning(4)
list.InsertAtBeginning(7)
print(list)
list.insertAtEnd(5)
list.insertAtEnd(4)
print(list)
let node1 = list.head?.nextNode
node1?.previousNode
list.tail?.previousNode?.previousNode

当我打印node时，它应该打印node和nextNode和previousNode的node，当我打印list时，它应该打印整个列表。例如，当我访问head时，它应该返回nil <-> 7 <-> 4.当我打印list时，它应该给出所有元素。

Answer 1

下面是满足您要求的实现。

Node description现在返回previousNode!.dataItem <-> dataItem <-> nextNode!dataItem 。 如果previousNode或nextNode nil，则将打印nil。

DoublyLinkedList的description将使用Node的linkedDescription来提供列表的递归描述。 每个Node的linkedDescription将包括Node的dataItem加上nextNode的linkedDescription(如果它不是nil(。 节点之间使用<->来表示链接。

extension DoublyLinkedList : CustomStringConvertible {
    var description : String {
        guard let doublyLinkedListHead = head else { return "UnderFlow"}
        return doublyLinkedListHead.linkedDescription
    }
}
extension Node : CustomStringConvertible {
    var description: String { return
        ((previousNode == nil) ? "nil" : "(previousNode!.dataItem)") +
        " <-> (dataItem) <-> " +
        ((nextNode == nil) ? "nil" : "(nextNode!.dataItem)")
    }
    var linkedDescription: String {
        return "(dataItem)" + ((nextNode == nil) ? "" : " <-> (nextNode!.linkedDescription)")
    }
}

这将在您print(list) 时递归提供整个列表。 当您print(node)时，它将提供previousNode!.dataItem <-> dataItem <-> nextNode!.dataItem。

---

例：

var list = DoublyLinkedList<Int>()
list.InsertAtBeginning(4)
list.InsertAtBeginning(7)
print(list)

7 <-> 4

print(list.head!)

nil <-> 7 <-> 4

list.insertAtEnd(5)
list.insertAtEnd(4)
print(list)

7 <-> 4 <-> 5 <-> 4

print(list.head!.nextNode!)

7 <-> 4 <-> 5

Answer 2

// Here is the full implementation of doubly-linked-list. updates will be appreciated. 

import Foundation
struct DoublyLinkedList<DataItem> {
    fileprivate var head : Node<DataItem>?
    fileprivate var tail : Node<DataItem>?
    var isEmpty : Bool {
        return head == nil
    }
    //to add at the beginning
    mutating func InsertAtBeginning(_ dataItem : DataItem) {
        let node = Node(dataItem: dataItem, nextNode: head, previousNode: nil)
        head?.previousNode = node
        head = node
        if tail == nil {
            tail = head
        }
    }
    //to add at the end
    mutating func insertAtEnd(_ dataItem : DataItem) {
        guard !isEmpty else {
            InsertAtBeginning(dataItem)
            return
        }
        let newNode = Node(dataItem: dataItem, nextNode: nil, previousNode: tail)
        tail?.nextNode = newNode
        //newNode.previousNode = tail
        tail = newNode
    }
    //to insert at particular node
    func insertParticularly(_ dataItem : DataItem , afterNode : Node<DataItem>) {
        let node = Node(dataItem: dataItem)
        afterNode.nextNode?.previousNode = node
        node.nextNode = afterNode.nextNode
        afterNode.nextNode = node
        node.previousNode = afterNode

    }
    //to find a node at particular index
    func findNode(at index : Int) -> Node<DataItem>? {
        var currentIndex = 0
        var currentNode =  head
        while currentNode != nil && currentIndex < index {
            currentNode = currentNode?.nextNode
            currentIndex += 1
        }
        return currentNode
    }
    //MARK:- remove functionality
    //remove the first element
    mutating func removeFirst() -> DataItem? {
        defer {
            head = head?.nextNode
            if isEmpty {
                head = nil
            }
        }
        return head?.dataItem
    }
    // remove the last element
    mutating func removeLast() -> DataItem? {

        guard let headValue = head else {
            return nil
        }
        guard headValue.nextNode != nil else {
            return removeFirst()
        }
        var previous = headValue
        var current = headValue
        while let next = current.nextNode {
            previous = current
            current = next
        }
        previous.nextNode = nil
        tail = previous
        return current.dataItem
    }
    // remove from a specific location
    mutating func removeAt(at node : Node<DataItem>?) -> DataItem? {
        defer {
            if node === tail {
                removeLast()
            }
            node?.previousNode?.nextNode = node?.nextNode
            node?.nextNode?.previousNode = node?.previousNode
        }
        return node?.nextNode?.dataItem
    }
}
extension DoublyLinkedList : CustomStringConvertible {
    var description : String {
        guard let doublyLinkedListHead = head else { return "UnderFlow"}
        //return String(describing: doublyLinkedListHead)
        return doublyLinkedListHead.linkedDescription
    }
}
class Node<DataItem> {
    var dataItem : DataItem
    var nextNode : Node?
    var previousNode : Node?

    init(dataItem : DataItem , nextNode : Node? = nil , previousNode : Node? = nil) {
        self.dataItem = dataItem
        self.nextNode = nextNode
        self.previousNode = previousNode
    }
}
extension Node : CustomStringConvertible {
    var description: String {
        return ((previousNode == nil) ? "nil" : "(previousNode!.dataItem)") +
                " <-> (dataItem) <-> " +
            ((nextNode == nil) ? "nil" : "(nextNode!.dataItem)")
    }
        var linkedDescription: String {
            return "(dataItem)" + ((nextNode == nil) ? "" : " <-> (nextNode!.linkedDescription)")
        }
}

var list = DoublyLinkedList<Int>()
list.InsertAtBeginning(4)
list.insertAtEnd(5)
list.insertAtEnd(4)
list.insertAtEnd(7)
list.insertAtEnd(2)
list.insertAtEnd(0)
list.description
let node1 = list.findNode(at: 3)
node1?.previousNode
list.head