{"ScriptPreparationCode":"/**\r\n * Linked List base code courtesy Nicholas C Zakas. Additional methods are my own.\r\n */\r\nfunction LinkedList() {\r\n /**\r\n * Pointer to first item in the list.\r\n * @property _head\r\n * @type Object\r\n * @private\r\n */\r\n this._head = null;\r\n}\r\n\r\nfunction createNode(data, next) {\r\n return {\r\n data: data,\r\n next\r\n };\r\n}\r\n\r\nLinkedList.prototype = {\r\n //restore constructor\r\n constructor: LinkedList,\r\n\r\n /**\r\n * Appends some data to the end of the list. This method traverses\r\n * the existing list and places the value at the end in a new item.\r\n * @param {variant} data The data to add to the list.\r\n * @return {Void}\r\n * @method add\r\n */\r\n push: function(data) {\r\n //create a new item object, place data in\r\n var node = createNode(data);\r\n\r\n //used to traverse the structure\r\n var current;\r\n\r\n //special case: no items in the list yet\r\n if (this._head === null) {\r\n this._head = node;\r\n } else {\r\n current = this._head;\r\n\r\n while (current.next) {\r\n current = current.next;\r\n }\r\n\r\n current.next = node;\r\n }\r\n },\r\n\r\n /**\r\n * Like its array counterpart, unshift appends an item to the beginning of the list\r\n */\r\n unshift: function(data) {\r\n var node = createNode(data);\r\n\r\n //special case: no items in the list yet\r\n if (this._head === null) {\r\n this._head = node;\r\n } else {\r\n node.next = this._head;\r\n this._head = node;\r\n }\r\n },\r\n\r\n /**\r\n * Like its array counterpart, shift removes and returns the first item of the list\r\n */\r\n shift: function() {\r\n const node = this._head;\r\n this._head = this._head.next;\r\n return node;\r\n },\r\n\r\n /**\r\n * Retrieves the data in the given position in the list.\r\n * @param {int} index The zero-based index of the item whose value\r\n * should be returned.\r\n * @return {variant} The value in the \u0022data\u0022 portion of the given item\r\n * or null if the item doesn\u0027t exist.\r\n * @method item\r\n */\r\n item: function(index) {\r\n //check for out-of-bounds values\r\n if (index \u003E -1) {\r\n var current = this._head,\r\n i = 0;\r\n\r\n while (i\u002B\u002B \u003C index \u0026\u0026 current) {\r\n current = current.next;\r\n }\r\n\r\n return current ? current.data : null;\r\n } else {\r\n return null;\r\n }\r\n },\r\n\r\n /**\r\n * Removes the item from the given location in the list.\r\n * @param {int} index The zero-based index of the item to remove.\r\n * @return {variant} The data in the given position in the list or null if\r\n * the item doesn\u0027t exist.\r\n * @method remove\r\n */\r\n remove: function(index) {\r\n //check for out-of-bounds values\r\n if (index \u003E -1) {\r\n var current = this._head,\r\n previous,\r\n i = 0;\r\n\r\n //special case: removing first item\r\n if (index === 0) {\r\n this._head = current.next;\r\n } else {\r\n //find the right location\r\n while (i\u002B\u002B \u003C index) {\r\n previous = current;\r\n current = current.next;\r\n }\r\n\r\n //skip over the item to remove\r\n previous.next = current.next;\r\n }\r\n\r\n //return the value\r\n return current ? current.data : null;\r\n } else {\r\n return null;\r\n }\r\n }\r\n};\r\n","TestCases":[{"Name":"Linked List","Code":"var list = new LinkedList();\r\nvar x = 10000;\r\n\r\nwhile(x--) {\r\n list.unshift(x);\r\n}\r\n","IsDeferred":false},{"Name":"Array","Code":"var array = [];\r\nvar x = 0;\r\n\r\nwhile(x \u003C 10000) {\r\n array[x] = x;\r\n x\u002B\u002B\r\n}","IsDeferred":false}]}