Python Linked List Queue

Question

I am trying to make a linked list queue in python and I cannot figure out how to return the size and the first item in the list...which seems pretty easy. I can insert and delete, but I cannot return the size or first item. Any thoughts??

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


class Queue(object):
  def __init__(self):
    """post: creates an empty FIFO queue"""
    self.length = 0
    self.head = None
    self.tail = None

  def enqueue(self, x):
    """post: adds x at back of queue"""
    newNode = Node(x)
    newNode.next = None
    if self.head == None:
      self.head = newNode
      self.tail = newNode
    else:
      self.tail.next = newNode
      newNode.previous = self.tail
      self.tail = newNode

  def dequeue (self):
    """pre: self.size() > 0
        post: removes and returns the front item"""
    item = self.head.item
    self.head = self.head.next 
    self.length = self.length - 1
    if self.length == 0:
      self.last = None
    return item

  def front(self):
    """pre: self.size() > 0
        post: returns first item in queue"""
    return item[0]

  def size(self):
    """post: returns the number of itemes in queue"""

Answer 1

_NodeLinked class is to create nodes:

  class _NodeLinked:
   # slots is memory efficient way to store the instance attributes
    __slots__ = '_element', '_next'
    def __init__(self, element, next):
        self._element = element
        self._next = next

 class QueuesLinked:
  # each instance being initialized an empty list
    def __init__(self):
        self._front = None
        self._rear = None
        self._size = 0

    def __len__(self):
        return self._size

    def isempty(self):
        return self._size == 0
   # adding a node to the end of the list
    def enqueue(self, e):
        newest = _NodeLinked(e, None)
        if self.isempty():
            self._front = newest
        else:
            self._rear._next = newest
        self._rear = newest
        self._size += 1
   # removing first node
    def dequeue(self):
        if self.isempty():
            print('Queue is empty')
            return
        e = self._front._element
        self._front = self._front._next
        self._size -= 1
        if self.isempty():
            self._rear = None
        return e

    def first(self):
        if self.isempty():
            print('Queue is empty')
            return
        return self._front._element

    def display(self):
        p = self._front
        while p:
            print(p._element,end=' <-- ')
            p = p._next
        print()

Answer 2

class Node: def init(self, data): self.data = data self.next = None

class Queue:

def __init__(self):
    self.front = None
    self.rear = None
    self.size = 0

def enQueue(self, data):
    temp = Node(data)
    if self.front == None:
        self.front = self.rear = temp
        self.size += 1 # get track of size
        return
    self.rear.next = temp
    self.rear = temp
    self.size += 1 

def deQueue(self):
    if self.front == None:
        return
    temp = self.front
    self.front = self.front.next
    if self.front == None:
        self.rear = None
    del temp
    self.size -= 1
    
def isEmpty(self): 
    return self.front == None

def getSize(self):
    return self.size

def getFront(self):
    if self.size > 0:
        return self.front.data
    else:
        return

def getRear(self):
    if self.size > 0:
        return self.rear.data
    else:
        return
    
def printQueue(self):
    queue = []
    curr = self.front
    while curr != None:
        queue.append(curr.data)
        curr = curr.next
    print(queue)

Answer 3

Your code in those two methods doesn't make any sense. How are you indexing into item? It's just a field of the Node class, not an array. Why didn't front() immediately lead you to thinking about head?

Surprisingly enough, the rest of your code seems okay. Here's what you need:

def front(self):
    return self.head.item

def size(self):
    return self.length

Also, you're not incrementing self.length in your enqueue() method.

The fact that you are having trouble with these should be a useful clue to you that you don't really understand the rest of the code. I've seen beginners often get mired in this trial-and-error approach, where you muck around with something until it works, usually starting with some code you got from somewhere. This leads to painfully brittle code, because your understanding is also brittle. This is not the way to write sensible code. At best it's a starting point for building your understanding - in which case, mucking around is exactly the right thing to do. Learn by experimentation and all that.

I recommend you read through the code you posted carefully and build a reasonably complete mental model of how it operates. Draw pictures or whatever helps you understand the pieces and the processes they implement. The depth of your mental model is a critical component of programming skill.

Also, you don't really need to go to all the trouble of writing these classes, other than as an exercise or something. Python lists already have methods that enable them to be used as queues.

Answer 4

Python lists already do what you're describing. Some examples:

# create a list
l = ['foo', 'bar']

# get the first item
print(l.pop(0))

# add an item
l.append(42)
print(l)

# get the size
print(len(l))

Answer 5

To efficiently be able to report the length of the linked list, you need to incriment it each time you add an element and decrement it each time you remove one. You're already doing the latter, but not the former.

So, just add self.length += 1 somewhere in your enqueue method, then size() can simple be return self.length

As for the first element in your queue, it will always be the item in the head node. So front() can be return self.head.item

Answer 6

First thing that jumps out at me is when you enqueue you need to increment the length of the list. size() should just need to return the length of the list once you've done that. And then to access the first item of the list you appear to be trying to use list syntax which your list does not support (at least in the code I can see). Instead return self.head