amzlist

A linked list implementation by John Keyes.

Getting the code

The simplest way is to clone the repository from GitHub:

git clone https://github.com/jkeyes/amzlist.git

Or you can download the repository in a ZIP file.

Basic Usage

You can prepend items to a linked list, which adds each new Node as the head of the list:

from amzlist import LinkedList

lnkd_list = LinkedList()
lnkd_list.prepend("amazon.com")
lnkd_list.prepend("@")
lnkd_list.prepend("jkeyes")

You can also append. Note this is much slower as we must traverse the entire list to find where to insert the node:

lnkd_list.append("Why would you use append?")

It’s also possible to insert a node after another node:

from amzlist import Node
n_color = Node("Red")
n_answer = Node(42)

lnkd_list.prepend(n_color)
lnkd_list.insert(n_answer, n_color) # insert n_answer after n_color

To remove a node the remove method can be used:

lnkd_list.remove("Red")

Alternatively you can use push and pop to add and remove nodes from the list:

lnkd_list.push("Item 1")
lnkd_list.push("Item 2")
node = lnkd_list.pop()
node.data == "Item 2"

Reversing

There are two methods to reverse the list, one uses an iterative approach and the other a recursive one:

rvsd_list = lnkd_list.reverse_iterative()
rvsd_list = lnkd_list.reverse_recursive()

Cycle Detection

If the LinkedList methods are used no cycles can be introduced. However, it is possible to introduct a cycle by directly manipulating the nodes:

lnkd_list = LinkedList()
node_john = Node('John')
lnkd_list.prepend(node_john)
node_james = Node('James')
lnkd_list.prepend(node_james)
node_joe = Node('Joe')
lnkd_list.prepend(node_joe)

# introduce a cycle
# Joe->James->John->Jules->John
node_jules = Node('Jules')
node_john.next = node_jules
node_jules.next = node_john

To prevent this you can create a strict LinkedList.

lnkd_list = LinkedList(strict=True)
...
node_jules.next = node_john
# Raises ValueError

WARNING: this is an EXTREMELY costly feature, as it requires traversal of the list for each Node that is added to the List (if the node being added has a value for next).

Running the Tests

To run the testsuite you’ll need to setup the environment first:

cd amzlist
virtualenv venv
source venv/bin/activate
pip install -r requirements.txt

Then you can run the testsuite:

nosetests tests

You can also get a coverage report:

nosetests tests --with-coverage --cover-package amzlist

Continuous Integration

The testsuite has been run on Python 2.5, 2.6, 2.7 and 3.2 on Travis CI.

API Documentation

Browse the API Documentation.

If you want to generate the documentation use the following commands:

cd docs
make html # docs will be generated in _build/html