Use hash table. Each node is a single entry in a Python dictionary. The key models a pointer, and is a randomly generated hex integer, just as a real pointer would be. The value models the attributes of a node and is implemented as a tuple containing (data, key_of_next_node).

The beginning of the list is stored in self.root.

Initialization requires at least one item in the list. Example:

>>> import linkedlist as L
>>> x = L.LinkedList(5)
>>> x.print()
5

Functions:

1. insert(datum[, prior_node]): if datum is list or string, each index will be inserted into its own node of the linked list; otherwise, insertion is at the root. Returns key of inserted node. Only the initial creation of the list does not return anything, but the list itself is then accessible at x.root.
2. delete(datum); returns deleted key of else None. On empty list, calls destroy_on_empty().
3. find(datum). Returns key of found node or else None.
4. length()
5. print(verbose = False): Prints whole list in a single line. On verbose = True, prints both key and data of each node on a successive line.
6. garbage_collect(). On empty list, calls destroy_on_empty().
7. return_list()
8. destroy_on_empty(): destroys llist and root to prevent further use of object. Used when delete(datum) or garbage_collect() produce an empty list.

Maybe no function for traversal — the cost of calling a function is expensive compared with implementing its content in place.

• Test suite.
• Option for doubly linked list using XOR.
• Option for circular linked list.
• insert at a particular index

[end]