This document explains a specific implementation of a linked list in Swift that utilizes the copy-on-write technique. This approach ensures that modifications to the list are performed on a unique copy of the underlying data structure. The implementation includes several methods that allow users to manipulate the list as needed.

The LinkedList struct provides various methods that enable users to manipulate the list in several ways. For instance, users can check if the list is empty through the isEmpty method, which returns a boolean value. The count method returns the number of elements in the list. The elements method returns an array of all the elements in the list. Also, there are methods for appending and removing elements. The removeFirst method returns the first element in the list and removes it from the list.

Moreover, the implementation includes a test suite to validate the correctness of the implementation. The test cases cover various scenarios, such as appending elements to the list, removing elements from the list, and testing the copy-on-write functionality.

The code for the LinkedList struct is written in Swift and is presented in the document. The code is well-organized and easy to read, with clear comments to guide developers who might want to modify the code. The code includes a LinkedListRef class, a Node class, and several extensions of the LinkedList struct that define the various methods.

The document also includes an overview of the copy-on-write technique used in the implementation. This includes a detailed explanation of the copyIfNeeded function, which checks if the reference to the LinkedList struct is uniquely referenced. If it is not, the function creates a copy of the reference before making any modifications to the data structure.

In conclusion, this document provides a comprehensive overview of the implementation of a linked list in Swift that uses copy-on-write to ensure that modifications to the list are performed on a unique copy of the underlying data structure. The document includes details about the various methods available, the code used to implement the linked list, and an explanation of the copy-on-write technique used. The test suite provides validation for the correctness of the implementation.

Implementation

struct LinkedList<T> {

  private var ref: LinkedListRef<T>

  public init() {
    self.ref = .init()
  }

  private mutating func copyIfNeeded() {
    guard isKnownUniquelyReferenced(&ref) == false else {
      return
    }
    let newRef = ref.copy()
    self.ref = newRef
  }

}

extension LinkedList {
  var isEmpty: Bool {
    return ref.head == nil
  }

  var count: Int {
    var count = 0
    var node = ref.head
    while node != nil {
      count += 1
      node = node?.next
    }
    return count
  }

  var elements: [T] {
    var elements: [T] = []
    var node = ref.head
    while node != nil {
      elements.append(node!.value)
      node = node?.next
    }
    return elements
  }
}

extension LinkedList {

  mutating func append(_ value: T) {

    copyIfNeeded()

    let newNode = Node(value: value)
    if ref.tail == nil {
      ref.head = newNode
      ref.tail = newNode
    } else {
      ref.tail!.next = newNode
      ref.tail = newNode
    }
  }

  @discardableResult
  mutating func removeFirst() -> T? {
    copyIfNeeded()

    if ref.head == nil {
      return nil
    }

    let removedValue = ref.head?.value
    ref.head = ref.head?.next

    if ref.head == nil {
      ref.tail = nil
    }

    return removedValue
  }
}

fileprivate final class LinkedListRef<T> {

  var head: Node<T>?
  var tail: Node<T>?

  init(head: Node<T>? = nil, tail: Node<T>? = nil) {
    self.head = head
    self.tail = tail
  }

  func copy() -> LinkedListRef<T> {
    guard let copiedHead = head?.copy() else {
      return .init()
    }

    var currentNode = copiedHead
    while currentNode.next != nil {
      currentNode = currentNode.next!
    }

    return .init(head: copiedHead, tail: currentNode)
  }

}

fileprivate final class Node<T> {
  var value: T
  var next: Node<T>?

  init(value: T, next: Node<T>? = nil) {
    self.value = value
    self.next = next
  }

  func copy() -> Node<T> {
    return Node(value: value, next: next?.copy())
  }
}

Test Cases

The test cases for the LinkedList implementation cover three main areas of functionality: appending elements to the list, removing elements from the list, and testing the copy-on-write functionality.

The testAppend function tests whether elements can be successfully appended to the list, and whether the isEmpty method correctly identifies whether the list is empty.

The testRemoveFirst function tests whether elements can be successfully removed from the list using the removeFirst method, and whether the method correctly returns nil when the list is empty.

The testCopyOnWrite function tests whether the copy-on-write functionality works correctly by creating two separate copies of the list, modifying one of them, and then testing if the other list was also modified.

The testCopyOnWriteIndependence function tests whether the copy-on-write functionality allows the two separate copies of the list to exist independently of each other. It modifies one list and then checks if the other list was also modified.

import XCTest
@testable import Verge

class LinkedListTests: XCTestCase {

  func testAppend() {
    var list = LinkedList<Int>()

    XCTAssertTrue(list.isEmpty)

    list.append(1)
    list.append(2)
    list.append(3)

    XCTAssertFalse(list.isEmpty)
  }

  func testRemoveFirst() {
    var list = LinkedList<Int>()
    list.append(1)
    list.append(2)
    list.append(3)

    XCTAssertEqual(list.removeFirst(), 1)
    XCTAssertEqual(list.removeFirst(), 2)
    XCTAssertEqual(list.removeFirst(), 3)
    XCTAssertNil(list.removeFirst())
    XCTAssertTrue(list.isEmpty)
  }

  func testCopyOnWrite() {
    var list1 = LinkedList<Int>()
    list1.append(1)
    list1.append(2)

    var list2 = list1
    list1.append(3)
    list2.append(4)

    XCTAssertEqual(list1.removeFirst(), 1)
    XCTAssertEqual(list1.removeFirst(), 2)
    XCTAssertEqual(list1.removeFirst(), 3)

    XCTAssertEqual(list2.removeFirst(), 1)
    XCTAssertEqual(list2.removeFirst(), 2)
    XCTAssertEqual(list2.removeFirst(), 4)
  }

  func testCopyOnWriteIndependence() {
    var list1 = LinkedList<Int>()
    list1.append(1)
    list1.append(2)
    list1.append(3)

    var list2 = list1

    // Modify list1
    list1.removeFirst()
    list1.append(4)

    // Verify list1 and list2 have independent states
    XCTAssertEqual(list1.removeFirst(), 2)
    XCTAssertEqual(list1.removeFirst(), 3)
    XCTAssertEqual(list1.removeFirst(), 4)

    XCTAssertEqual(list2.removeFirst(), 1)
    XCTAssertEqual(list2.removeFirst(), 2)
    XCTAssertEqual(list2.removeFirst(), 3)
    XCTAssertNil(list2.removeFirst())
  }
}