Circular Linked List Implementation in Swift

1. Introduction

A Circular Linked List is a variation of the linked list in which the last node of the list points back to the first node, forming a closed loop. It provides a more cyclic and continuous structure compared to the standard linked list. Each node in a circular linked list has a successor, and there is no "end" node.

2. Implementation Steps

1. Define a Node class to represent each element in the list. This class will contain a value and a next pointer.

2. Create the CircularLinkedList class.

3. Initialize a head node which will be the starting point of the list.

4. Implement methods to append, prepend, and delete nodes.

5. Implement methods to traverse and print the list.

6. Implement utility methods to retrieve the size of the list and check if it's empty.

3. Implementation in Swift

class Node<T> {              // 1. Node class
    var value: T
    var next: Node?
    init(value: T) {
        self.value = value
    }
}
class CircularLinkedList<T> {
    var head: Node<T>?       // 3. Head node
    // 4. Append node
    func append(value: T) {
        let newNode = Node(value: value)
        if var tailNode = head {
            while tailNode.next !== head {
                tailNode = tailNode.next!
            }
            tailNode.next = newNode
            newNode.next = head
        } else {
            head = newNode
            newNode.next = head  // Point back to itself
        }
    }
    // 4. Prepend node
    func prepend(value: T) {
        let newNode = Node(value: value)
        var lastNode = head
        newNode.next = head
        if head != nil {
            while lastNode!.next !== head {
                lastNode = lastNode!.next
            }
            lastNode!.next = newNode
            head = newNode
        } else {
            head = newNode
            newNode.next = head
        }
    }
    // 4. Delete a node
    func delete(value: T) {
        if let headNode = head {
            if headNode.value == value {
                var currentNode = head
                while currentNode!.next !== head {
                    currentNode = currentNode!.next
                }
                currentNode!.next = headNode.next
                head = headNode.next
            } else {
                var prevNode = head
                var currentNode = head?.next
                while currentNode != nil && currentNode!.next !== head && currentNode!.value != value {
                    prevNode = currentNode
                    currentNode = currentNode!.next
                }
                if currentNode!.value == value {
                    prevNode!.next = currentNode!.next
                }
            }
        }
    }
    // 5. Print list
    func printList() {
        if let headNode = head {
            var currentNode: Node? = headNode
            repeat {
                print(currentNode!.value)
                currentNode = currentNode?.next
            } while currentNode !== head
        }
    }
    // 6. Retrieve size
    var size: Int {
        if var node = head {
            var count = 1
            while node.next !== head {
                count += 1
                node = node.next!
            }
            return count
        } else {
            return 0
        }
    }
    // Check if list is empty
    var isEmpty: Bool {
        return head == nil
    }
}
// Usage:
let list = CircularLinkedList<Int>()
list.append(value: 1)
list.append(value: 2)
list.append(value: 3)
list.prepend(value: 0)
list.printList()   // Outputs: 0, 1, 2, 3
list.delete(value: 2)
list.printList()   // Outputs: 0, 1, 3

Output:

0
1
2
3
0
1
3

Explanation:

1. The Node class represents each element in the Circular Linked List. It contains a value and a single next pointer.

2. The CircularLinkedList class manages the overall list and operations on it.

3. The append method adds a node to the end of the list. It makes sure to adjust the next pointer of the last node to point to the head, ensuring the circular nature of the list.

4. The prepend method adds a node at the beginning. It also ensures the circular linkage by updating the last node's next pointer.

5. The delete method removes a node from the list based on its value. Deleting in a circular linked list requires careful handling to maintain the loop.

6. The printList method traverses and prints all nodes until it reaches the starting point again.

7. Utility methods like size and isEmpty give more information about the list's state.