CODEWITHSUNDEEP
pythonlinked-list
Dude
Dude

Reputation: 31

Sorted Doubly Linked List Python

I'm having trouble understanding and implementing a Doubly Linked List. I can grasp most of the concepts of a Linked List. Here is my code so far (in Python)

*This is a purely academic exercise. I would normally use list and dict.

class DoublyNode(object):
    """A node of the SortedDoublyLL object.

    DoublyNode(item, next=None, previous=None) -> a new DoublyNode with data as
    its data, and next and previous as its neighbors."""

    def __init__(self, data, next = None, previous = None):
        """Make a new DoublyNode from item, pointing to next and previous."""

        self.data = data
        self.next = next
        self.previous = previous

class SortedDoublyLL(object):
    """A Sorted Doubly Linked List.

    SortedDoublyLL() -> new SortedDoublyLL list that is empty
    SortedDoublyLL(sequence) -> a SortedDoublyLL initialized from sequence's
    items.

    """

    def __init__(self, sequence = []):
        """Make a new SortedDoublyLL from the elements of sequence."""

        if len(sequence) == 0:
            self.head = None
            self.tail = None
        else:
            cur_node = None
            prev_node = None
            sequence.sort()
            sequence.reverse()
            for element in sequence:
                prev_node = cur_node
                cur_node = DoublyNode(element, cur_node, prev_node)

            self.head = cur_node
            self.tail = DoublyNode(sequence[0])

Upvotes: 3

Views: 4387

Answers (1)

aaronasterling
aaronasterling

Reputation: 71004

Change your loop to

for element in sequence:
    prev_node = cur_node
    cur_node = DoublyNode(element, None, prev_node)
    prev_node.next = cur_node

Because the line prev_node = cur_node precedes the call DoublyNode(element, cur_node, prev_node), you end up setting both the previous and next elements to the previous element so you are ending up with a linked list that just has two links to the previous element. So you might as well just pass None as the next parameter1 and then initialize it manually on the next pass of the loop. This has the advantage of leaving it as None on the last element of the list.

1 Using the name next as a parameter in the constructor will shadow the builtin function next which advances an iterator. You could use the name next_ which is the canonical thing to do. Using next as an attribute isn't a problem because that qualifies the name so that no shadowing will occur. It will mess up in some syntax highlighters though.

Upvotes: 2

Related Questions