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

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 以及 node 的一个 previousNode，当我打印 list，它应该打印整个列表。例如，当我访问 head 时，它应该 return nil <-> 7 <-> 4。当我打印 list 时，它应该给出所有元素。

Answer 1

这是满足您要求的实现。

description Node 现在 returns previousNode!.dataItem <-> dataItem <-> nextNode!dataItem。如果 previousNode 或 nextNode 是 nil，那么将打印 nil。

description for a DoublyLinkedList 将使用 linkedDescription of a Node 来提供列表的递归描述。每个 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

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

Cannot print entire doubly linked-list elements to console

swift

linked-list

doubly-linked-list