How to implement doubly linked list in swift?

Question

How can I implement a doubly linked list in Swift with all the operations like insert and deletion?

I know how to implement singly linked list but I can't find a way to make it a doubly linked list. I am a beginner in coding.

import UIKit

struct LinkedList<Value> {

    var Head : node<Value>?
    var Tail : node<Value>?

    var isEmpty : Bool {
        return Head == nil
    }

    // to add at the beginning of the list
    mutating func push(_ value : Value) {
        Head = node(value: value, nextNode: Head)
        if Tail == nil {
            Tail = Head
        }
    }

    // to add at the end of the list
    mutating func append(_ value : Value) {
        guard !isEmpty else {
            push(value)
            return
        }

        let newNode = node(value: value)
        Tail?.nextNode = newNode
        Tail = newNode
    }

    //to find the node at particular index
    func findNode(at index: Int) -> node<Value>? {
         var currentIndex = 0
         var currentNode = Head
        while(currentNode != nil && currentIndex < index) {
             currentNode = currentNode?.nextNode
            currentIndex += 1
        }
        return currentNode
    }

    // to insert at a particular location

    func insert(_ value : Value, afterNode : node<Value>) {
        afterNode.nextNode = node(value: value, nextNode: afterNode.nextNode)
    }

    mutating func pop() -> Value? {

        defer {
            Head = Head?.nextNode
            if isEmpty {
                Head = nil
            }
        }

        return Head?.value
    }


    mutating func removeLast() -> Value? {

        guard let head = Head else {
            return nil
        }
        guard head.nextNode != nil else {
            return pop()
        }

        var previous = head
        var current = head

        while let next = current.nextNode {
            previous = current
            current = next
        }

        previous.nextNode = nil
        Tail = previous
        return current.value

    }

    mutating func remove(after node : node<Value>?) -> Value? {

        defer {
            if node === Tail {
                Tail = node
            }
            node?.nextNode = node?.nextNode?.nextNode
        }
        return node?.nextNode?.value
    }
}

extension LinkedList : CustomStringConvertible {
    var description: String {

        guard let linkedListHead = Head else {
            return "Empty List"
        }
        return String(describing: linkedListHead)
    }


}

class node<Value> {

    var value : Value
    var nextNode : node?

    init(value : Value , nextNode : node? = nil) {

        self.value = value
        self.nextNode = nextNode

    }

}


extension node : CustomStringConvertible {
    var description: String {
        guard let nextValue = nextNode else { return "\(value)" }

        return "\(value) -> " + String(describing: nextValue) + " "
    }


}

var listOfIntegers = LinkedList<Int>()
var listOfStrings = LinkedList<String>()

listOfIntegers.push(1)
listOfIntegers.push(3)
listOfIntegers.push(4)
listOfIntegers.append(6)
let nodeInfo = listOfIntegers.findNode(at: 1)!
listOfIntegers.insert(8, afterNode: nodeInfo)
print(listOfIntegers)
listOfStrings.push("hello")
listOfStrings.push("Sardar Ji!")
print(listOfStrings)
let index = 3
let node2 = listOfIntegers.findNode(at: index - 1)
listOfIntegers.remove(after: node2)
print(listOfIntegers)

I want to implement doubly linked list the same way and the output should be like this:

node1 <-> node2 <-> node3

Answer 1

Fundamentally, your problem is that you've got head and tail pointers in LinkedList, but node only has nextNode pointer. If node is the structure representing each item in the list, and if you want to be able to traverse the list in either direction, then each item needs a link to the next item and also the previous item. That's why they call it a "doubly linked list" after all.

1. Add a previousNode pointer to your node structure.
2. Go find every spot in your code where you modify a nextNode pointer and change the code to also maintain the previousNode pointer.

Answer 2

//here is the full implementaion of doubly-linked-list in swift. 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