Linked List

First of all, LinkedList was relatively harder to implement rather the ArrayDeque. This is because I had to keep track of the head, the tail, the size and all of the nodes using LinkedList. I was using more lines of code in LinkedList. As simple as adding in the first index, it was quite a hassle because I had to create another node, point that to where the head is, let the previous head point to the new node, etc. It was more operations inside the implementation of a list or deque using LinkedList. Iterating through the list was also uneasy, you have to start from the head or the tail, and work through till the end. LinkedList is more memory consuming than ArrayDeque. In my part, it was a challenge because this is the first time I had encountered a challenge using a LinkedList, so once again, I searched it and tried understood it to the best of my abilities.

I think I would use more of ArrayDeque rather than DLList but if ever I choose to use the latter, if I have a simple ADT such as a queue or a stack. However, a LinkedList is much more flexible than an ArrayDeque. Meaning, we can grow it without having to resize our list, as contrast to what ArrayDeque can do. When we general insertions, or when our list is very large and we don’t know how larger it can get, we can use a LinkedList. There are pros and cons when using either. It all depends now on the situation.

Here is the code I used for Linked List:

class Node:
  def __init__(self, element, next, previous):
    self._element = element
    self._next = next
    self._previous = previous

  
class DoublyLinkedList:
  def __init__(self):
    self._head = Node(None, None, None)
    self._tail = Node(None, None, None)
    self._head._next = self._tail
    self._tail._prev = self._head
    self._size = 0

  def _len(self):
    return self._size

  def is_empty(self):
    return self._size == 0

  def add_first(self, element):
    new_node = Node(element, None, None)
    if self.is_empty():
      self._head = new_node
      self._tail = new_node
    else:
      new_node._next = self._head
      self._head._previous = new_node  
    self._head = new_node
    self._size += 1

  def add_last(self, element):
    new_node = Node(element, None, None)
    if self.is_empty():
      self._head = new_node
      self._tail = new_node
    else:
      self._tail._next = new_node
      new_node._previous = self._tail
    self._tail = new_node
    self._size += 1

  def add(self, element, index):
    new_node = Node(element, None, None)
    temp = self._head
    i = 1
    while i < index:
      temp = temp._next
      i += 1
    
    new_node._next = temp._next
    temp._next = new_node
    temp._next._previous = new_node
    new_node._previous = temp
    self._size += 1
  
  def remove_first(self):
    if self.is_empty():
      raise Exception("List is empty! Cannot remove anything")
    value = self._head._element
    self._head = self._head._next 
    self._head._prev = None
    self._size -= 1
    if self.is_empty():
      self._tail = None
    return value

  def remove_last(self):
    if self.is_empty():
      raise Exception("List is empty! Cannot remove anything")
    temp = self._head
    i = 0
    while i < len(self)-2:
      temp = temp._next
      i += 1
    self._tail = temp
    temp = temp._next
    value = temp._element
    self._tail._next = None
    self._size -= 1
    return value

  def remove(self, index):
    if self.is_empty():
      raise Exception("List is empty! Cannot remove anything")
    temp = self._head
    i = 1
    while i < (index - 1):
      temp = temp._next
      i += 1
    temp._next = temp._next._next
    temp._next._next._previous = temp
    self._size -= 1

  def get(self, index):
    if index >= self._len():
      raise Exception("Index is out of bounds!")
      return None
    i = 0
    temp = self._head
    while temp:
      if i == index:
        return temp._element
      temp = temp._next
      i += 1

  def _set(self, element, index):
    if index >= self._len():
      raise Exception("Index is out of bounds!")
      return None
    i = 0
    temp = self._head
    while temp:
      if i == index:
        temp._element = element
      temp = temp._next
      i += 1
    
  def display(self):
    temp = self._head
    while temp:
      print(temp._element)
      temp = temp._next
    print()
  
  def show_dll(self):
    dll = []
    temp = self._head
    while temp:
      dll.append(temp._element)
      temp = temp._next
    return dll
    


# tests 

# dll = DoublyLinkedList()

# dll.add_first(2)
# dll.add_first(1)

# print(dll.show_dll())
# print(dll.get(1))
# dll._set(5,0)
# print(dll.show_dll())