Answered! please discuss the differences between the array implementation and the linked list implementation of queues.list…

Expert Answer

A queue may be implemented in most languages using arrays. The primary limitation of this implementation is that the resulting queue has a limited capacity.

To implement a queue in an array, three instance variables are required:

• An array of objects of the type to be stored in the queue. The size of this array is equal to the maximum number of items that will be stored in the queue.
• An integer that keeps track of the number of items in the queue (this variable will be called rear).
• An integer that keeps track of the maximum number of items that can be placed in the queue.

  class AQueue
  {
     Object data[];
     int maxItems,
         rear;
  }
  

To implement a queue in a linked structure, a Node class is needed …

class Node
{
   Object data;
   Node next;
   
   public Node(Object newData)
   {
      data = newData;
      next = null;
   }
}

Differences between the array implementation and the linked list implementation of queues:

• The ArrayList is part of the Collections Framework. It is a List that is built on top of an array. It provides methods to add to the list (thereby changing the size), as well as to obtain an iterator, and to remove elements, sort elements, and perform searches. Basically, it saves you from having to write that code when using an array.
• The LinkedList is also a List. It essentially provides the same methods as the ArrayList, except the underlying data structure uses objects that contain references to other objects to form a list. This is “similar” to the concept other languages call “pointers” (but not quite the same).
• Linked List and Array List both implement List Interface but how they work internally is where the differences lies. Main difference between ArrayList and LinkedList is that ArrayList is implemented using re sizable array while LinkedList is implemented using doubly LinkedList.
• LinkedList is a suitable collection than ArrayList.
• Since Array is an index based data-structure searching or getting element from Array with index is pretty fast. Array provides O(1) performance for get(index) method but remove is costly in ArrayList as you need to rearrange all elements. On the Other hand LinkedList doesn’t provide Random or index based access and you need to iterate over linked list to retrieve any element which is of order O(n).
• Insertions are easy and fast in LinkedList as compared to ArrayList because there is no risk of resizing array and copying content to new array if array gets full which makes adding into ArrayList of O(n) in worst case, while adding is O(1) operation in LinkedList in Java.
• LinkedList has more memory overhead than ArrayList because in ArrayList each index only holds actual object (data) but in case of LinkedList each node holds both data and address of next and previous node.

Advantages of Linked list implementation:

• Linked lists are a dynamic data structure, allocating the needed memory while the program is running.
• Insertion and deletion node operations are easily implemented in a linked list.
• Linear data structures such as stacks and queues are easily executed with a linked list.
• They can reduce access time and may expand in real time without memory overhead.

Disdvantages of Linked list implementation:

• They have a tendency to use more memory due to pointers requiring extra storage space.
• Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access.
• Nodes are stored incontiguously, greatly increasing the time required to access individual elements within the list.
• Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards^[1] and while doubly linked lists are somewhat easier to read, memory is wasted in allocating space for a back pointer.

Examples of Array implementation Linked list implementation:

Array Code:

static mylist myListQ[QUEUESIZE+1];
int qLast = 0;

void enqueue_element(mylist qItem)
{
        myListQ[qLast] = qItem;
    qLast++;
}

mylist dequeue_element()
{
 retryq:
   if(qLast >0) {
    mylist qReturn = myListQ[0];  
    int i;
    for (i = 0; i < qLast - 1; i++){
        myListQ[i] = myListQ[i + 1];
    }
    qLast--; 
    return qReturn;
     }
   else {
    goto retryq;
    }
}

Linked List Code:

int qLast = 0;

mylistQ *headElement = NULL;   
mylistQ *tailElement = NULL;     

void enqueue_element(mylist *List)
{
    mylistQ *newnode;      
    newnode=(mylistQ*)av_malloc(sizeof(mylistQ));
    newnode->next=NULL;
    newnode->list=*List;
    qLast++;
    if(headElement==NULL && tailElement==NULL)
    {
        headElement=newnode;
        tailElement=newnode;
    }
    else
    {
        tailElement->next=newnode;
        tailElement=newnode;
    }
 }

mylist dequeue_element()
{
    mylistQ *delnode;      /* Node to be deleted */
    mylist Dellist;
    if(headElement==NULL && tailElement==NULL){
        LOg( "Queue is empty to delete any element");
        }
    else
    {
       Log("In dequeue_picture queue is not empty");
        delnode=headElement;
        headElement=headElement->next;
    if (!headElement){
        tailElement=NULL;
    }
        Dellist = delnode->list;
        av_free(delnode);
    qLast--;
    }
        return Dellist;
}