<jupyter_start><jupyter_text>7.1 Single Lingled Lists Advantages of Lists are 1. The length of a dynamic array might be longer than the actual number ofelements that it stores.2. Amortized bounds for operations may be unacceptable in real-time systems.3. Insertions and deletions at interior positions of an array are expensive.A singly linked list, in its simplest form, is a collection of nodes that collectivelyform a linear sequence. Each node stores a reference to an object that is an elementof the sequence, as well as a reference to the next node of the list.The first and last node of a linked list are known as the head and tail of thelist, respectively. By starting at the head, and moving from one node to anotherby following each node’s next reference, we can reach the tail of the list. We canidentify the tail as the node having None as its next reference. This process iscommonly known as traversing the linked list. Because the next reference of anode can be viewed as a link or pointer to another node, the process of traversinga list is also known as link hopping or pointer hopping.<jupyter_code># The analysis of our LinkedStack operations: all of the methods complete in worst-case constant time O(1)
class LinkedStack:
    class _Node: # nested Class
        __slots__ = '_element', '_next' # streamline memory message
        def __init__(self, element, next):
            self._element = element
            sellf._next = next
    def __init__(self):
        self._head = None
        self._size = 0
        
    def __len__(self):
        return self._size
    
    def is_empty(self):
        return self._size == 0
    
    def push(self,e):
        self._head = self._Node(e, self._head)
        self._size += 1
    
    def top(self):
        
        if self.is_empty():
            raise Empty('Stack is empty')
        else:
            return self._head._element
    
    def pop(self):
        
        if self.is_empty():
            raise Empty('Stack is empty')
        else:
            answer = self._head._element
            self._head = slef._head._next
            self._size -= 1
            return answer
class LinkedQueue:
    class _Node: # nested Class
        __slots__ = '_element', '_next' # streamline memory message
        def __init__(self, element, next):
            self._element = element
            sellf._next = next
    
    def __init__(self):
        self._head = None
        self._tail = None
        self._size = 0
        
    def __len__(self):
        return self._size
    
    def is_empty(self):
        return self._size == 0
    
    def deque(self):
        if self.is_empty():
            raise Empty('Queue is Empty')
        answer = self._head._element
        self._head = self._head._next
        self._size -=1
        if self.is_empty():
            self._tail = None
        return answer
    
    def enque(self,e):
        newest = self._Node(e, None)
        if self.is_empty():
            self._head = newest
        else:
            self._tail._next = newest
        self._tail = newest
        self._size += 1

# Round Roubin Scheduler - Circular list to iterate through known tasks and subroutines
# Looks like
# 1. Start et e = Q.dequeue
# 2. Service element e
# 3. Q.enqueue(e)
# 4.. .....

class CircularQueue:
    class _Node:
        __slots__ = '_element', '_next' # streamline memory message
        def __init__(self, element, next):
            self._element = element
            sellf._next = next
            
    def __init__(self):
        self._tail = None # will represent tail of queue
        self._size = 0    # number of queue elements
        
    def __len__(self):
        return self._size
    
    def is_empty(self):
        return self._size == 0 
    
    def first(self):
        if self.is_empty():
            raise Empty('Queue is empty')
        head = self._tail._next
        return head._element

    def deque(self):
        if self.is_empty():
            raise Empty('Queue is Empty')
        oldhead = self._tail._next
        if self._size == 1:
            self._tail = None
        else:
            self._tail._next = oldhead._next
        self._size -= 1
        return oldhead._element
    
    def enque(self,e):
        newest = self._Node(e, None)
        if self.is_empty():
            self._next = newest
        else:
            newest._next = self._tail._next
            self._tail._next = newest
        self._tail = newest
        self._size += 1
    
    def rotate(self):
        if self._size >0:
            self._tail = self._tail._next<jupyter_output><empty_output><jupyter_text>Double Linked ListsDisadvantage of single linked lists: we cannot efficiently delete an arbitrary node from an interior position of the list if only given a reference to that node, because we cannot determine the node that immediately precedes the node to be deleted.In order to avoid some special cases when operating near the boundaries of a doubly linked list, it helps to add special nodes at both ends of the list: a header node at the beginning of the list, and a trailer node at the end of the list. The advantage of using sentinel cells is that just the node between a trailer and a header node changes.<jupyter_code>class _DoublyLinkedBase:
    class _Node:
    ##Lightweight, nonpublic class for storing a doubly linked node.”””
    __slots__ = '_element' , '_prev' , '_next' # streamline memory
        def __init__ (self, element, prev, next): # initialize node’s fields
            self._element = element # user’s element
            self._prev = prev # previous node reference
            self._next = next # next node reference
    def __init__(self):
      #”””Create an empty list.”””
        self._header = self._Node(None, None, None)
        self._trailer = self._Node(None, None, None)
        self._header._next = self._trailer # trailer is after header
        self._trailer._prev = self._header # header is before trailer
        self._size = 0 # number of elements
    
    def __len__(self):
        return self._size
    
    def is_empty(self):
        #”””Return True if list is empty.”””
        return self. size == 0

    def insert between(self, e, predecessor, successor):
        #”””Add element e between two existing nodes and return new node.”””
        newest = self. Node(e, predecessor, successor) # linked to neighbors
        predecessor. next = newest
        successor. prev = newest
        self. size += 1
return newest
def delete node(self, node):
”””Delete nonsentinel node from the list and return its element.”””
predecessor = node. prev
successor = node. next
predecessor. next = successor
successor. prev = predecessor
self. size −= 1
element = node. element # record deleted element
node. prev = node. next = node. element = None # deprecate node
return element # return deleted element<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.07583212735166425, 'fraction_numerical': 0.004052098408104197, 'mean_word_length': 2.280018984337921, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '545179', 'license': 'Unlicense', 'n_tokens_mistral': 1884, 'n_tokens_neox': 1830, 'n_words': 756, 'path': 'Data Structure and Algorithms/.ipynb_checkpoints/Chapter 7 - Linked Lists-checkpoint.ipynb', 'repo_name': 'Nikolaikl/teachmyselfcs', 'size': '6910'}