Linked List Implementation in Swift

1. Introduction

A Linked List is a linear data structure where elements, referred to as nodes, are connected by pointers. Each node contains data and a reference (link) to the next node in the sequence. Linked Lists allow for dynamic memory allocation, which means elements can be added or removed from the list without the need to resize or move other elements, unlike arrays.

2. Implementation Steps

1. Create a Node class that will store the value and a reference to the next node.

2. Define a LinkedList class or structure.

3. Initialize a head node to represent the start of the linked list.

4. Implement methods to append (add) nodes to the end of the list.

5. Implement a method to delete a node from the list.

6. Implement a method to print all the elements of the linked list.

7. Implement 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 LinkedList<T> {
    var head: Node<T>?    // 3. Head node
    // 4. Append node to the list
    func append(value: T) {
        let newNode = Node(value: value)
        if let tailNode = tail {
            tailNode.next = newNode
        } else {
            head = newNode
        }
    }
    // Returns the last node (used in append)
    private var tail: Node<T>? {
        var node = head
        while node?.next != nil {
            node = node?.next
        }
        return node
    }
    // 5. Delete a node
    func delete(value: T) {
        var previousNode: Node<T>?
        var currentNode = head
        while currentNode != nil && currentNode!.value != value {
            previousNode = currentNode
            currentNode = currentNode?.next
        }
        if previousNode == nil {
            head = currentNode?.next
        } else {
            previousNode?.next = currentNode?.next
        }
    }
    // 6. Print all elements
    func printList() {
        var currentNode = head
        while currentNode != nil {
            print(currentNode!.value)
            currentNode = currentNode?.next
        }
    }
    // 7. Retrieve size
    var size: Int {
        var count = 0
        var node = head
        while node != nil {
            count += 1
            node = node?.next
        }
        return count
    }
    // Check if list is empty
    var isEmpty: Bool {
        return head == nil
    }
}
// Usage:
let list = LinkedList<Int>()
list.append(value: 1)
list.append(value: 2)
list.append(value: 3)
list.printList()  // Outputs: 1, 2, 3
list.delete(value: 2)
list.printList()  // Outputs: 1, 3
print(list.size)  // Outputs: 2

Output:

1
2
3
1
3
2

Explanation:

1. We start with the creation of a Node class that holds a value and a reference to the next node.

2. The LinkedList class has a head property, which is the first node of the linked list.

3. The append method is used to add new nodes to the end of the list. If there's a tail node (the last node), we attach the new node to its next property. Otherwise, the linked list is empty, and the new node becomes the head.

4. For convenience, a tail computed property is provided to always find the last node of the list.

5. The delete method removes a node with a given value. It navigates through the list to find the node and then updates the next property of the previous node.

6. The printList method iterates over each node and prints its value.

7. The size computed property counts and returns the number of nodes in the list. The isEmpty property checks if the list has any nodes.