Thinking In Objects: Doubly Linked Lists

            The goal of last week’s lab was to find a more efficient implementation of a queue. A queue designed using python’s lists is generally slow due to the shifting behaviour of ".pop(0)" or ".insert(0,item)". When an item is inserted or removed at the front of a list, all the items must be reassigned and then shifted up or down. My TA was trying to get me to think of an implementation that would avoid this behaviour. More specifically, make a queue design where I would only need to know the first and last items. However, I could not think of an efficient way to apply this in python. In other words, I did not have my object oriented programming cap on. Near the end of the lab, my TA hinted towards using objects that recognize which item was before and after them. However, the lab was over and I did not get to employ my solution. I had heard of linked lists before, but had never implemented one, or really figured out what they were. What my TA was hinting at sounded like a linked list! When I got home, I googled “linked list”, and decided to design queue using a doubly linked list design. I have posted my code below.

My queue design is modelled after the queue from  lab 2. Integers can be added and removed(“popped”). The queue removes items in a first in, first out manner. Every item in the linked list is a Node object. 

Node objects have three variables:

 - A reference to the object before it

 - A reference to the object after it

 - The data of the Node