     /// Create an empty list.
     public init() { }
 
+    /// - Complexity: O(n), where n is the length of `sequence`.
     public init<S : SequenceType where S.Generator.Element == Element>(_ sequence: S) {
         for v in sequence {
             append(v)

        return startIndex.advancedBy(offset)
    }

    public var startIndex: Index {
        return head ?? endIndex
    }

    public var endIndex = Index(value: nil)

    /// - Complexity: O(1).
    public subscript(index: Index) -> Element {
        get {


extension List {

    /// Insert `newElement` before the element at `index`.
    ///
    /// If this is the *first* modification to the list since creation or copying, invalidates all indices with respect to `self`.
    ///
    /// - Complexity: O(1).
    public mutating func insert(newElement: Element, atIndex index: Index) {
        let index = needsUnique ? uniqueTransferringIndex(index) : index
        let node = Node(value: newElement)
