Data Structures with Generic Types in Python/

...

/

DLList: A Doubly-Linked List

DLList: A Doubly-Linked List

Learn to implement a doubly-linked list.

We'll cover the following...

A DLList (doubly-linked list) is very similar to an SLList except that each node u in a DLList has references to both the node u.next that follows it and the node u.prev that precedes it.

Press + to interact
class DLList(BaseList):
    
    class Node(object):
        def __init__(self, x):
            self.x = x
            self.next = None
            self.prev = None
    def __init__(self, iterable=[]):
        self._initialize()
        self.add_all(iterable)

A dummy node in DLList

When implementing an SLList, we saw that there were always several special cases to worry about. For example, removing the last element from an SLList or adding an element to an empty SLList requires care to ensure that head and tail are correctly updated. In a DLList, the number of these special cases increases considerably. Perhaps the cleanest way to take care of all these special cases in a DLList is to introduce a dummy node. This is a node that does not contain any data, but acts as a placeholder so that there are no special nodes; every node has both a next and a prev, with dummy acting as the node that follows the last node in the list and that precedes the first node in the list. In this way, the nodes of the list are (doubly-)linked into a cycle, as illustrated below:

Press + to interact
A DLList containing a, b, c, d, e
A DLList containing a, b, c, d, e
Press + to interact
class DLList(BaseList):
    
    class Node(object):
        def __init__(self, x):
            self.x = x
            self.next = None
            self.prev = None
    def __init__(self, iterable=[]):
        self._initialize()
        self.add_all(iterable)
        
    def _initialize(self):
        self.n = 0
        self.dummy = DLList.Node(None)
        self.dummy.prev = self.dummy
        self.dummy.next = self.dummy

Finding the node with a particular index in a DLList is easy; we can either start at the head of the list (dummy.next) and work forward, or start at the tail of the list (dummy.prev) and work backward. This allows us to reach the iith node in O(1+min⁡{i,n−i})O(1 + \min\{i, n − i\}) ...

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy