Queues
The two primary operations involving queues are inserting a new element into a queue
and removing an element from a queue. The insertion operation is called enqueue, and
the removal operation is called dequeue. The enqueue operation inserts a new element
at the end of a queue, and the dequeue operation removes an element from the front of
a queue. Example:
enqueue(a,arr) result [a]
enqueue(b,arr) result [a,b]
enqueue(c,arr) result [a,b,c]
enqueue(d,arr) result [a,b,c,d]
enqueue(e,arr) result [a,b,c,d,e]
dequeue(operateOnDequeuedFunc) [b,c,d,e]
dequeue(operateOnDequeuedFunc) [c,d,e]
dequeue(operateOnDequeuedFunc) [d,e]
dequeue(operateOnDequeuedFunc) [e]
dequeue(operateOnDequeuedFunc) []
Some uses of queues
Simulations: since queue operates in a natural order, meaning the first thing that happens is
the first thing to be resolved. It is good for simulating events happening on a timeline.
For example the browsers event queue:
User is clicking on things, creating Javascript tasks that are added to the event loop queue.
These tasks need to be resolved in the order the user made them happen, in order to reflect the real nature of the timeline of the event, and resolve the users interaction propely.
There is also the Dance Party simulation used to demonstrate queues:
REFER TO: Data structures and algorithms with javascript -> Chapter:5
Sorting data with queues (radix sort):
Priority Queues
Shortcomings of Arrays
* In many languages arrays are fixed in size, making it hard to add new elements to the array.
* Deleting elements from an array demand changing the position of all elements in an array, same with deletion.
* In Javascript arrays are less eficient since they are really array like objects, unlike in languages like Javas or C++.
* Linked lists can be useful whenever a one dimensional array is needed, unless random access is needed
Insertion to a linked list
Insertion to a linked lists a very simple procedure.
You basically travel down the next properties of the linked list, and when you reach the node that you looking for (to insert an adjacent object after) you simply reference the its next property to the new object, and you reference the new objects next property to the previously linked object, to the object the was linked to its parent.
Removing a node from the list
To remove a node from the list, you need to traverse the list until you find it.
The you have to do 2 things:
1) point the next attribute of the previous node to the node after the node you want to remove.
2) point the removed node's next property to NULL
Doubly Linked Lists
Traversing a linked list from one end to the other is easy, but to traverse the link back to the start will need that each node has a reference to the the previous node, usually using a property called parent.
* deletion - do delete a node form a doubly linked list you need to do 4 things:
1) change the previous nodes next property to point to the node after the removed node.
2) change the parent property, on the node after the removed node, to point to previous node (now the parent)
3) change the removed nodes parent to NULL
4) change the removed nodes next property to null.
Circularly linked list
A linked list has a Header object which is the first object of the list, in a Circularly Linked List the last node's next property does not point to NULL, but rather back to the Header node
Why circularly linked list - if you want to be abale to traverse back in a linked list but you do not want the over head of creating a doubly linked node for each link, a circular linked list can enable geting back to the start of the list easily by just traversing to the end of it once.
