How can states of a automaton being traversed in linear time and space complexity? How would the states/transitions be expressed as data structures?
Also, is there a algorithm for converting a NFA to a DFA in linear time and space?
Implementation depends on the exact application. In general case, you can always implement it as a node with multiple outgoing links. In this case, transitioning is O(1).
However, you could implement using a matrix. Especially when the transitions are dense.