Doubly Linked List Implementation in Swift

1. Introduction

A DoublyLinkedList is an extension of the regular singly linked list. In a DoublyLinkedList, each node contains a value and two references (links) pointing to its next and previous node in the sequence. This bidirectional link provides more flexibility, allowing operations to traverse both forward and backward through the list.

2. Implementation Steps

1. Define a Node class to represent each node in the doubly linked list.

2. Define a DoublyLinkedList class to manage the nodes.

3. Implement methods to add, remove, and retrieve values from the doubly linked list.

3. Implementation in Swift

// 1. Definition of the Node class
class Node<T> {
    var value: T
    var next: Node?
    weak var previous: Node?
    init(value: T) {
        self.value = value
    }
}
// 2. Definition of the DoublyLinkedList class
class DoublyLinkedList<T> {
    private var head: Node<T>?
    private var tail: Node<T>?
    // Add a value to the end of the list
    func append(_ value: T) {
        let newNode = Node(value: value)
        if let tailNode = tail {
            tailNode.next = newNode
            newNode.previous = tailNode
            tail = newNode
        } else {
            head = newNode
            tail = newNode
        }
    }
    // Remove the first occurrence of a value from the list
    func remove(_ value: T) where T: Equatable {
        var currentNode = head
        while currentNode != nil {
            if currentNode!.value == value {
                if let prev = currentNode!.previous {
                    prev.next = currentNode!.next
                    currentNode!.next?.previous = prev
                } else {
                    head = currentNode!.next
                    head?.previous = nil
                }
                if currentNode!.next == nil {
                    tail = currentNode!.previous
                }
                return
            }
            currentNode = currentNode!.next
        }
    }
    // Print the linked list's values
    func printList() {
        var currentNode = head
        while currentNode != nil {
            print(currentNode!.value, terminator: " <-> ")
            currentNode = currentNode?.next
        }
        print("nil")
    }
}
// Example Usage
let list = DoublyLinkedList<Int>()
list.append(1)
list.append(2)
list.append(3)
list.printList()  // Outputs: 1 <-> 2 <-> 3 <-> nil
list.remove(2)
list.printList()  // Outputs: 1 <-> 3 <-> nil

Output:

1 <-> 2 <-> 3 <-> nil
1 <-> 3 <-> nil

Explanation:

1. The Node class represents each node in the doubly linked list. Each node contains a value, a reference (next) to the next node, and another reference (previous) to its previous node.

2. The DoublyLinkedList class manages the sequence of nodes. It contains references to the first (head) and the last (tail) nodes.

3. The append method adds a new value to the end of the list. If there's a tail, it sets the new node as its next and updates the tail reference. If there's no tail, it means the list is empty, so the new node becomes both the head and the tail.

4. The remove method removes the first occurrence of a given value from the list, adjusting the previous and next pointers as necessary.

5. The printList method prints the values in the linked list in sequence, demonstrating the bidirectional traversal capability of a doubly linked list.

This DoublyLinkedList provides a deeper understanding of linked list traversal, emphasizing the versatility of a bidirectional data structure.