Creating Linked Lists in Python

John Machin sjmachin at lexicon.net
Sat Mar 21 13:50:40 CET 2009


On Mar 21, 10:38 pm, J-Burns <arslanbur... at gmail.com> wrote:
> Hey thr,
>
> I need some help here actually. So i thought i could get it easily
> from here.
>
> I need to make a linked list that can do the following:
>
> 1) Point to multiple nodes at one time

The term "linked list" is usually restricted to a collection of nodes
each of which has a value, a pointer to the next mode in the list, and
maybe a pointer to the previous node in the list. You want much more
than that.

> 2) Should have 2 values:
>     a) The node no.
>     b) The value of that node in reference to the next node that it is
> pointing to
>
> 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.

What you want is a collection of nodes each of which has a value (that
you haven't specified and may not need) plus a mapping from something
to other nodes. In this case the something appears to be the input
characters from a text to be match against your RE.

The simplest structure for that in Python, omitting your maybe-needed
node value, would be a list of nodes, where each node is a dict
mapping input characters to node numbers ...

nfa = [
  {'a': 1, 'b': 2, }, # this is node 0
  etc,
  etc,
  ]

Instead of a Python list and using list indexes as node IDs, you may
end up writing a class that maintains an NFA as a collection of nodes,
where each node is an instance of an NFANode class  ... each such node
would have as an attribute a dict mapping input characters to other
nodes -- this is the essential concept.

BTW, is this homework?

Cheers,
John



More information about the Python-list mailing list