basic implementation of doubly linked list we begin by providing preliminary implementation of doubly linked listin the form of class named doublylinkedbase we intentionally name the class with leading underscore because we do not intend for it to provide coherent public interface for general use we will see that linked lists can support general insertions and deletions in ( worst-case timebut only if the location of an operation can be succinctly identified with array-based sequencesan integer index was convenient means for describing position within sequence howeveran index is not convenient for linked lists as there is no efficient way to find the jth elementit would seem to require traversal of portion of the list when working with linked listthe most direct way to describe the location of an operation is by identifying relevant node of the list howeverwe prefer to encapsulate the inner workings of our data structure to avoid having users directly access nodes of list in the remainder of this we will develop two public classes that inherit from our doublylinkedbase class to provide more coherent abstractions specificallyin section we provide linkeddeque class that implements the double-ended queue adt introduced in section that class only supports operations at the ends of the queueso there is no need for user to identify an interior position within the list in section we introduce new positionallist abstraction that provides public interface that allows arbitrary insertions and deletions from list our low-level doublylinkedbase class relies on the use of nonpublic node class that is similar to that for singly linked listas given in code fragment except that the doubly linked version includes prev attributein addition to the next and element attributesas shown in code fragment class node"""lightweightnonpublic class for storing doubly linked node ""slots _element _prev _next streamline memory def init (selfelementprevnext)self element element self prev prev self next next initialize node' fields user' element previous node reference next node reference code fragment python node class for use in doubly linked list the remainder of our doublylinkedbase class is given in code fragment the constructor instantiates the two sentinel nodes and links them directly to each other we maintain size member and provide public support for len and is empty so that these behaviors can be directly inherited by the subclasses