Databases
StackOverflow2013
Postsdbo
POQueue performance wise which is better implementation - Array or Linked list
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POQueue performance wise which is better implementation - Array or Linked list
    primarykey
    data
    text
    <p>Which way gives the faster enqueueing and dequeuing when I have to insert very few elements, Is array better than a linked list?</p> <p>I need to insert few element and I have to remove and read that removed element from queue. If it is array I may have to modify the indexes every time I remove an element. Inserting and deleting may happen simultaneously also. </p> <p>Which one is better from below case?</p> <pre><code>typedef struct{ mylist list; struct mylistQ *next; }mylistQ; </code></pre> <p><strong>Array Code</strong> </p> <pre><code> static mylist myListQ[QUEUESIZE+1]; int qLast = 0; void enqueue_element(mylist qItem) { myListQ[qLast] = qItem; qLast++; } mylist dequeue_element() { retryq: if(qLast &gt;0) { mylist qReturn = myListQ[0]; int i; for (i = 0; i &lt; qLast - 1; i++){ myListQ[i] = myListQ[i + 1]; } qLast--; return qReturn; } else { goto retryq; } } </code></pre> <p><strong>Linked List</strong> </p> <pre><code> int qLast = 0; mylistQ *headElement = NULL; mylistQ *tailElement = NULL; void enqueue_element(mylist *List) { mylistQ *newnode; newnode=(mylistQ*)av_malloc(sizeof(mylistQ)); newnode-&gt;next=NULL; newnode-&gt;list=*List; qLast++; if(headElement==NULL &amp;&amp; tailElement==NULL) { headElement=newnode; tailElement=newnode; } else { tailElement-&gt;next=newnode; tailElement=newnode; } } mylist dequeue_element() { mylistQ *delnode; /* Node to be deleted */ mylist Dellist; if(headElement==NULL &amp;&amp; tailElement==NULL){ LOg( "Queue is empty to delete any element"); } else { Log("In dequeue_picture queue is not empty"); delnode=headElement; headElement=headElement-&gt;next; if (!headElement){ tailElement=NULL; } Dellist = delnode-&gt;list; av_free(delnode); qLast--; } return Dellist; } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USAnil Arrabole
    1. USAnil Arrabole
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POQueue performance wise which is better implementation - Array or Linked list
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POQueue performance wise which is better implementation - Array or Linked list
      1. USkosii
      1. VTFavorite
    3. VO
      singulars
      1. POQueue performance wise which is better implementation - Array or Linked list
      1. This table or related slice is empty.
      1. VTUpMod
    1. COCPU cache locality is king. An array is *very* hard to beat.
      singulars
      1. POQueue performance wise which is better implementation - Array or Linked list
      1. USHans Passant
    2. CO@Hans: Arrays are hard to beat, unless you need to resize them, or they get too big for your cache lines. Linked lists of sensibly sized arrays are pretty great though.
      singulars
      1. POQueue performance wise which is better implementation - Array or Linked list
      1. USnmichaels
    3. COSeconding nmichaels. If you want it to be fast for small and large queues, a linked-list of arrays is best.
      singulars
      1. POQueue performance wise which is better implementation - Array or Linked list
      1. USTobu
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload