Creating Linked Lists in Python

[Aaron Brady]

On Mar 21, 8:11 am, "andrew cooke" <and... at acooke.org> wrote:
> J-Burns wrote:
snip
> > For example, this means that there can be a start node supposedly.
> > Having a value of 0. It is pointing to node 1 with the value of "a"
> > and to node 2 with the value of "b". Trying to make something like an
> > NFA. Where id be changing regular expressions to NFAs.
>
> > How can I do this? And if I could do this by some other way than using
> > linked lists than do tell me about that as well.
>
> when you mention NFAs and regular expressions, you make me think that you
> don't want a linked list at all, but a graph.  there are various ways of
> storing a graph, but one of the simplest is to use a dict() that maps from
> source to destination node(s).
>
> in your case you could use ints for the nodes and a dict([int]) for the
> graph.  so:
>
> {1: [2,3], 2: [3], 3: [3]}
>
> is a graph in which 1 and 2 are connected in each direction, both 1 and 2
> are linked to 3, and 3 has a loop that links back to itself.
>
> andrew

WARNING, spoiler.

So far, Andrew's and John's structures can be used for both a DFA and
a NFA.  The only thing further you need is a collection instead of a
single value to hold current state.

states= set( [ 1 ] )
while 1:
  _newstates= set( )
  for state in states:
    _newstates.update( transitions[ state ] )
  states= _newstates
  # or states.clear( ); states.update( _newstates )

How will you mark a state as 'final'/ success?