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.
A dictionary
is a data structure that stores data as key-value pairs, such as the way a
phone book stores its data as names and phone numbers. When you look for a phone
number, you first search for the name, and when you find the name, the phone number
is found right next to the name. The key is the element you use to perform a search, and
the value is the result of the search.
The JavaScript Object class is designed to operate as a dictionary.