Can double-linked lists be implemented in python?

[Robin Munn]

sdieselil <sdieselil at yahoo.com> wrote:
> Hi
> 
> How can I implement double-linked lists and other complex tree-like
> structures in Python?

Do you *need* doubly-linked lists? Is there something that Python's
builtin list type can't do for you? Consider whether it's worth taking
the time to code up a data structure, with all the attendant edge cases,
when you've already got such nice useful builtin types...

Having said that, if you really need to code up a data structure that
doesn't already exist in Python, I'd recommend the same thing that
others have said: code up a class. E.g.,

class BinaryTreeNode(object):
    def __init__(self, data=None):
        self.data = data
        self.left = None
        self.right = None

class BinaryTree(object):
    def __init__(self):
        self.root = None

    def insert(self, data):
        if self.root is None:
            self.root = BinaryTreeNode(data)
        else:
            cur = self.root
            parent = None
            while cur is not None:
                cmp_result = cmp(cur.data, data)
                if cmp_result == 0:
                    raise DuplicateDataError
                elif cmp_result > 0:
                    # cur.data > data
                    parent = cur
                    cur = cur.right
                else:
                    # cur.data < data
                    parent = cur
                    cur = cur.left
            # Found the right place, now insert a node
            if cmp_result > 0:
                assert(parent.right is None)
                parent.right = BinaryTreeNode(data)
            else:
                assert(parent.left is None)
                parent.left = BinaryTreeNode(data)

    def search(self, data):
        # Etc.

-- 
Robin Munn <rmunn at pobox.com>
http://www.rmunn.com/
PGP key ID: 0x6AFB6838    50FF 2478 CFFB 081A 8338  54F7 845D ACFD 6AFB 6838