Doubly linked list, Stack, Queue, Deque

class Node:

    def __init__(self, val, prev, nxt):
        self.val = val
        self.prev = prev
        self.nxt = nxt

class LinkedList:

    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0

    def get_count(self):
        return self.count

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

    def __str__(self):
        ret = []
        curr = self.head
        while curr != None:
            ret.append(curr.val)
            curr = curr.nxt
        return str(ret)

    def get_node_at(self, idx):
        if idx >= self.get_count() or idx < -self.get_count():
            raise IndexError("list index out of range")
        if idx < 0:
            curr = self.tail
            for i in range(-1, idx, -1):
                curr = curr.prev
            return curr
        else:
            curr = self.head
            for i in range(idx):
                curr = curr.nxt
            return curr

    def __getitem__(self, idx):
        return (self.get_node_at(idx)).val

    def insert_front(self, val):
        self.count += 1
        self.head = Node(val, None, self.head)
        if self.get_count() == 1:
            self.tail = self.head
        else:
            self.head.nxt.prev = self.head # need to make sure to link the previous too

    def insert_back(self, val):
        if self.is_empty():
            self.head = Node(val, None, None)
            self.tail = self.head
            self.count += 1
            return
        self.tail.nxt = Node(val, self.tail, None)
        self.tail = self.tail.nxt
        self.count += 1

    def delete_front(self):
        if self.is_empty():
            raise IndexError("deleting from an empty list")
        self.head = self.head.nxt
        self.count -= 1
        if self.is_empty():
            self.tail = None
        else:
            self.head.prev = None

    def delete_back(self):
        if self.is_empty():
            raise IndexError("deleting from an empty list")
        self.tail = self.tail.prev
        self.count -= 1
        if self.is_empty():
            self.head = None
        else:
            self.tail.nxt = None

class Stack:

    def __init__(self):
        self.li = LinkedList()

    def count(self):
        return self.get_count()

    def empty(self):
        return self.is_empty()

    def top(self):
        return self.li[0]

    def pop(self):
        ans = self.li[0]
        self.li.delete_front()
        return ans

    def push(self, val):
        self.li.insert_front(val)

class Queue:

    def __init__(self):
        self.li = LinkedList()

    def count(self):
        return self.get_count()

    def empty(self):
        return self.is_empty()

    def front(self):
        return self.li[0]

    def dequeue(self):
        ans = self.li[0]
        self.li.delete_front()
        return ans

    def enqueue(self, val):
        self.li.insert_back(val)

class Deque: # double ended queue

    def __init__(self):
        self.li = LinkedList()

    def count(self):
        return self.get_count()

    def empty(self):
        return self.is_empty()

    def front(self):
        return self.li[0]
    def back(self):
        return self.li[-1]

    def pop_front(self):
        ans = self.li[0]
        self.li.delete_front()
        return ans
    def pop_back(self):
        ans = self.li[-1]
        self.li.delete_back()
        return ans

    def push_front(self, val):
        self.li.insert_front(val)
    def push_back(self, val):
        self.li.insert_back(val)

Q = Deque()
Q.push_front(3)
Q.push_front(6)
Q.push_front(4)
Q.push_front(8)
Q.push_back(-1)
Q.push_back(-2) # 8 4 6 3 -1 -2
print(Q.pop_front())
print(Q.pop_front()) # 6 3 -1 -2
Q.push_back(-3)
Q.push_back(-4) # 6 3 -1 -2 -3 -4
print(Q.pop_back())
print(Q.pop_back()) # 6 3 -1 -2
print(Q.pop_front())
print(Q.pop_front())
print(Q.pop_front())

# L = LinkedList()
# L.insert_back(5)
# L.insert_back(6)
# L.insert_back(7)
# L.insert_back(8)
# L.insert_front(3)
# L.insert_front(2)
# L.insert_front(1)
# print(L)
# L.delete_back()
# L.delete_back()
# L.delete_front()
# print(L)