Doubly Linked List Data Structure Initialization and Methods Python

# //almost identical to doubly linked list but 
# //every node has another pointer to previous node 
# //Advantages: able to access list at end instead of going from start 
# //Disadvantages: takes up more memory 

class Node: 
  def __init__(self, value, next=None, previous=None): 
    self.value = value 
    self.next = next 
    self.previous = previous 

class DoublyLinkedList:
  def __init__(self, head=None, tail=None, length=0):
    self.head = head 
    self.tail = tail 
    self.length = length 

  #add to end of list 
  def append(self, value): 
    new_node = Node(value)
    #if there is no head (list is empty), set head and tail to be new_node 
    if self.head == None: 
      self.head = new_node 
      self.tail = new_node
    #otheriwse, set next property on tail to be new node and set tail to be newly created node 
    else: 
      self.tail.next = new_node 
      new_node.previous = self.tail 
      self.tail = new_node 
    #increment length and return 
    self.length += 1 
    return self 
  
  #removes last element of list 
   def pop(self): 
    if self.head == None: 
      return None 
    #current will eventually be the last elemeent and will be removed 
    current = self.head 
    #variable right before end 
    new_tail = current 
    #while loop to traverse to end 
    while current.next: 
      new_tail = current 
      current = current.next 
    #sets new tail 
    self.tail = new_tail 
    #cuts off old tail and current previous property 
    self.tail.next = None 
    current.previous = None 
    #decrement list 
    self.length -= 1 
    #to account when list will be destroyed 
    if self.length == 0: 
      self.head = None
      self.tail = None 
    return current 
  
  #removes elememnt at head. Note in python, shift doesn't exist, it would be .pop(0) or you can use remove which is defined later
  def shift(self): 
    if self.head == None: 
      return None 
    #current_head will be removed and returned 
    current_head = self.head 
    self.head = current_head.next 
    #severs new self.head previous property
    self.head.previous = None 
    self.length -= 1 
    #to account when list will be destroyed 
    if self.length == 0: 
      self.tail = None 
    #severs current_head. Note previous is already set to None 
    current_head.next = None 
    return current_head 

  
  #adds to start of list and replaces head. I included shift/unshift because this is what makes linked list special in terms of reducing big O 
  def unshift(self, value): 
    new_node = Node(value)
    #edge case to account if list is originally empty 
    if self.head == None: 
      self.head = new_node 
      self.tail = self.head 
    else: 
      temp = self.head 
      self.head = new_node 
      self.head.next = temp 
      temp.previous = self.head 
    self.length += 1 
  
  #travels to node at index and returns node 
  def traverse(self, index): 
    if index < 0 or index >= self.length: 
      raise IndexError('index out of range')
    counter = 0 
    current = self.head 
    #since this is doubly linked list, you can also approach from tail and go backwards 
    while counter != index: 
      current = current.next 
      counter += 1 
    return current 
  
  #travels to node at index and returns node's value 
  def get(self, index): 
    #to accomodate normal python function, where if you give index = -1 in a get(), it will return last index and so on 
    if index < 0: 
      index = self.length + index 
    node = self.traverse(index)
    return node.value 
  
  #replaces value at index 
  def set(self, index, value): 
    found_node = self.traverse(index) 
    if found_node: 
      found_node.value = value
      return True 
    else: 
      return False 
  
  #insert value at index and adds 1 to length, returns boolean if successful 
  def insert(self, index, value): 
    if index < 0 or index > self.length: 
      raise IndexError('index out of range')
    if index == self.length: 
      #not not is similar to !! in javascript and it's so it returns a boolean if successful 
      return not not self.append(value)
    if index == 0: 
      return not not self.unshift(value) 
    else: 
      new_node = Node(value) 
      previous_node = self.traverse(index - 1) 
      after_node = previous_node.next 
      
      #creating relations before new_node 
      previous_node.next = new_node 
      new_node.previous = previous_node 
      #creating relations after new_node 
      new_node.next = after_node 
      after_node.previous = new_node 
      
      #increment length
      self.length += 1 
      return self 
  
  
  def remove(self, index): 
    if index < 0 or index > self.length: 
      return indexError('index out of range') 
    if index == self.length - 1: 
      return self.pop()
    if index == 0: 
      return self.shift() 
    else: 
      #need to get previous node and after node to create relationships 
      previous_node = self.traverse(index - 1) 
      #removed_node will be removed and returned  
      removed_node = previous_node.next 
      after_node = removed_node.next 
      #unlink removed_node 
      previous_node.next = removed_node.next 
      after_node.previous = previous_node 
      #sever removed_node next 
      removed_node.next = None 
      removed_node.previous = None 
      self.length -= 1 
      return removed_node 
  
 #common interview question 
  def reverse(self): 
    #switching head and tail 
    current = self.head 
    self.head = self.tail 
    self.tail = current 
    
    next, previous = None, None 
    #to show for loop is possible in LL. Could use while loop as well 
    for i in range(0, self.length): 
      #think of this as creating the block 
      next = current.next 
      current.next = previous #initially None 
      current.previous = next
      #think of this as connecting head/previous to the block 
      previous = current 
      current = next 
    return self 

# # // [100. 201, 250, 350, 999]
# # // first part 
# # // NODE  NEXT 
# # // 100 -> null 
 
# # // second part (for loop and beyond) 
# # // PREV  NODE  NEXT 
# # // line 154( prev = current; ) specifically: 
# # // 201 -> 100  -> null 
# # // line 155 (current = next;): 
# # //        PREV  NODE  NEXT 
# # // 250 -> 201 -> 100 
  
  #useful to visualize reverse() or any other function works 
  def print_linkedlist_to_list(self): 
    result = []
    current = self.head 
    while current: 
      result.append(current.value)
      current = current.next 
    print(result)
    
    
    

# l = DoublyLinkedList() 
# l.append(1) 
# l.append(2)
# l.pop()
# l.shift()
# l.unshift(3)
# l.append(4) 
# l.traverse(0)
# l.get(-2)
# l.set(2, 7)
# l.insert(0, 99)
# l.remove(2)
# l.print_linkedlist_to_list()
# l.reverse() 
# l.print_linkedlist_to_list()

# y = l.length
# print(y)

# // Insertion: 
# // O(1) 
# // Removal: recall in SL it depends 
# // O(1)
# // Searching: 
# // O(N) but optimized bc you can start from head or tail (but more memory)
# // Access: 
# // Same as searching