CODEWITHSUNDEEP
swiftlinked-list
lanza
lanza

Reputation: 1642

Swift: Recursive use of generic struct

I'm playing around with linked lists in Swift and I'm using:

struct Node<Element> {
    var next: Node<Element>? 
}

it yields this error:

Recursive value type "Node<Element>" is not allowed.

I tried using indirect on both the struct declaration and the property but neither worked. How do you implement this type of structure?

Upvotes: 2

Views: 1446

Answers (3)

lanza
lanza

Reputation: 1642

It's not possible with Structs. It's also doesn't seem wise to do linked list with value types. Unless you feel like doing 

head.next.next.next.next.next = head.next.next.next.next.next.next

to delete the seventh node, you're going to want to be able to set

let next = head.next

Upvotes: 0

Andrea
Andrea

Reputation: 26383

It seems that is not possible to create a recursive use of struct, but you can do by using enum, associated values and the indirect attribute.

A recursive enumeration is an enumeration that has another instance of the enumeration as the associated value for one or more of the enumeration cases. You indicate that an enumeration case is recursive by writing indirect before it, which tells the compiler to insert the necessary layer of indirection.

indirect enum Tree<Element: Comparable> {
    case Empty
    case Node(Tree<Element>,Element,Tree<Element>)
}

Code taken from AirspeedVelocity.

Upvotes: 2

jtbandes
jtbandes

Reputation: 118741

When you write var next: Node<Element>?, Swift tries to put this storage inline, but since it's recursive, that results in an infinite-size struct.

indirect only applies to enums, so you could do something like this:

enum Node<Element> {
    indirect case Node(Element, next: Node?)
}

Node.Node(42, next: nil)

Or you can use a regular reference type, a.k.a. class:

class Node<Element> {
    var next: Node<Element>?
}

Upvotes: 3

Related Questions