It is important for us to understand the efficiency of those basic Python data structures (string, list, tuple, dictionary, โ€ฆ) because they are the building blocks we will use as we implement other advanced data structures.

  • List

    Considering the time efficiency of creat a list. Use list(range(100)) is faster than list comprehension, than append, and much faster than concatenation.

  • Dictionary

    Contains โ€œinโ€ operator for lists is ๐‘‚(๐‘›) and the contains operator for dictionaries is ๐‘‚(1).

ADT: Abstract Data Type

  • stack, queue, deque, and list

    Stacks, queues, deques, and lists are examples of data collections whose items are ordered depending on how they are added or removed.

    • Stack: LIFO, last-in first-out

    For stack, the order that they are removed is exactly the reverse of the order that they were placed. So โ€ฆ stacks are fundamentally important, as they can be used to reverse the order of items.

    Items are added to and removed from one end called the โ€˜topโ€™

    [Implementation]: Use a list to implement a stack, the end of the list will hold the top element of the stack.

    [Application]: Balanced Parentheses?

    Stack is a proper data structure to solve this problem. The code is as belows:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    def par_checker(symbol_string):
      
      s = Stack()
      balanced = True
      index = 0
      while index < len(symbol_string) and balanced:
          
          symbol = symbol_string[index]
          if symbol == "(":
              s.push(symbol)
          else:
              if s.is_empty():
                  balanced = False
              else:
                  s.pop()
                  
          index = index + 1

      if balanced and s.is_empty():
          return True
      else:
          return False

    print(par_checker('((()))'))
    print(par_checker(')((()))('))

    Stacks are very important data structures for the processing of language constructs in computer science.

    • Queue: FIFO, first-in first-out

    A queue is an ordered collection of items where the addition of new items happens at one end, called the โ€œrear,โ€ and the removal of existing items occurs at the other end, commonly called the โ€œfrontโ€.

    Items are added to and removed from two ends called the โ€œrearโ€ (add items) and โ€œfrontโ€ (remove items).

    [Implementation]: Use a list to implement a queue, and we need to decide which end of the list to use as the rear and which to use as the front. This means that enqueue will be ๐‘‚(๐‘›) and dequeue will be ๐‘‚(1).

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    # A implementation of a queue ADT
    class Queue:
      def __init__(self):
        self.items = []
      def is_empty(self):
        return self.items == []
      def enqueue(self, item):
        self.items.insert(0,item)
      def dequeue(self):
        return self.items.pop()
      def size(self):
        return len(self.items)

    [Application]: Hot potato

    • Deque: a double-ended queue, two ends, a front and a rear. New items can be added/removed at either the front or the rear. Combine the capabilities of stacks and queues. Donโ€™t require LIFO and FIFO orderings, itโ€™s up to you to make a consistant use of the addition and removal operations.

    [Application]: Palindrome Checker

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    class Deque:
      def __init__(self):
          
          self.items = []
          
      def is_empty(self):
          return self.items == []
      
      def add_front(self, item):
          self.items.append(item)
          
      def add_rear(self, item):
          self.items.insert(0,item)
      
      def remove_front(self):
          return self.items.pop()
      
      def remove_rear(self):
          return self.items.pop(0)
      
      def size(self):
          return len(self.items)

    # Palindrome Checker
    def pal_checker(a_string):
      char_deque = Deque()
      
      for ch in a_string:
          char_deque.add_rear(ch)
          
      still_equal = True
      
      while char_deque.size() > 1 and still_equal:
          first = char_deque.remove_front()
          last = char_deque.remove_rear()
          if first != last:
              still_equal = False
      return still_equal

    print(pal_checker("firstf"))
    print(pal_checker("radar"))
    • Unordered List: using Linked Lists to implement

    We need to be sure that we can maintain the relative positioning of the items. However, there is no requirement that we maintain that positioning in contiguous memory. โ€” Linked Lists

    The basic building block for the linked list is the node, which must contain two pieces of information:

    • data field: the list item itself
    • reference: reference to the next node

    The linked list structure provides us with only one entry point, the head of the list. All of the other nodes can only be reached by accessing the first node and then following next links.

    Notice: the first item (31) added to the list will eventually be the last node on the linked list as every other item is added ahead of it.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class UnorderedList:
        def __init__(self):
            self.head = None

        def is_empty(self):
            return self.head == None

        # add a new node
        def add(self,item):
            temp = Node(item)
            temp.set_next(self.head)
            self.head = temp

        #