Data Structures with Generic Types in Python/

...

/

Operations on SEList

Operations on SEList

Learn different operations supported by a space-efficient linked list.

We'll cover the following...

Finding elements

The first challenge we face with an SEList is finding the list item with a given index ii. Note that the location of an element consists of two parts:

  1. The node u that contains the block that contains the element with index ii; and
  2. The index j of the element within its block.

To find the block that contains a particular element, we proceed the same way as we do in a DLList. We either start at the front of the list and traverse in the forward direction, or at the back of the list and traverse backwards until we reach the node we want. The only difference is that, each time we move from one node to the next, we skip over a whole block of elements.

Press + to interact
class SEList(BaseList):
    class BDeque(ArrayDeque):
        def __init__(self, b):
            super(SEList.BDeque, self).__init__()
            self.a = new_array(b+1)
        
        def _resize(self):
            pass
        
    class Node(object):
        def __init__(self, b):
            self.d = SEList.BDeque(b)
            self.prev = None
            self.next = None
            
    def __init__(self, b):
        super(SEList, self).__init__()
        self.b = b
        self._initialize()
        
    def _get_location(self, i):
        if i < self.n//2:
            u = self.dummy.next
            while i >= u.d.size():
                i -= u.d.size()
                u = u.next
            return u,i
        else:
            u = self.dummy
            idx = self.n
            while i < idx:
                u = u.prev
                idx -= u.d.size()
        return u, i-idx

Remember that, with the exception of at most one block, each block contains at least b−1b − 1 elements, so each step in our search gets us b−1b − 1 elements closer to the element we are looking for. If we are searching forward, this means that we reach the node we want after O(1+i/b)O(1 + i/b) steps. If we search backwards, then we reach the node we want after O(1+(n−i)/b)O(1 + (n − i)/ b) steps. The algorithm takes the smaller of these two quantities depending on the value of i, so the time to locate the item with index i is O(1+min⁡{i,n−i}/b).O(1+\min\{i,n−i\}/b).

Once we know how to locate the item with index i, the get(i) and set(i, x) operations translate into getting or setting a particular index in the correct block:

Press + to interact
class SEList(BaseList):
    class BDeque(ArrayDeque):
        """A bounded-size deque"""
        def __init__(self, b):
            super(SEList.BDeque, self).__init__()
            self.a = new_array(b+1)
        
        def _resize(self):
            pass
        
    class Node(object):
        def __init__(self, b):
            self.d = SEList.BDeque(b)
            self.prev = None
            self.next = None
            
    def __init__(self, b):
        super(SEList, self).__init__()
        self.b = b
        self._initialize()
        
    def get(self, i):
        u, j = self._get_location(i)
        return u.d.get(j)
    def set(self, i, x):
        u, j = self._get_location(i)
        return u.d.set(j, x)

The running times of these operations are dominated by the time it takes to locate the item, so they also run in O(1+min⁡{i,n−i}/b)O(1+\min\{i,n−i\}/b) time.

Adding an element

Adding elements to an SEList is a little more complicated. Before considering the general case, we consider the easier operation, add(x), in which x is added to the end of the list. If the last block is full (or does not exist because there are no blocks yet), then we first allocate a new block and append it to the list of blocks. Now that we are sure that the last block exists and is not full, we append x to the last block.

Press + to interact
class SEList(BaseList):
    class BDeque(ArrayDeque):
        """A bounded-size deque"""
        def __init__(self, b):
            super(SEList.BDeque, self).__init__()
            self.a = new_array(b+1)
        
        def _resize(self):
            pass
        
    class Node(object):
        def __init__(self, b):
            self.d = SEList.BDeque(b)
            self.prev = None
            self.next = None
            
    def __init__(self, b):
        super(SEList, self).__init__()
        self.b = b
        self._initialize()
    
    def append(self, x):
        last = self.dummy.prev
        if last is self.dummy or last.d.size() == self.b+1:
            last = self._add_before(self.dummy)
        last.d.append(x)
        self.n += 1

Things get more complicated when we add to the interior of the list using add(i, x). We first locate i to get the node u whose block contains the ii ...

Create a free account to access the full course.

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