λ Stack list-based

======= Algorithm ======= <syntax js> function LinkedList() { this.first = null; } LinkedList.Node = function(data, next) { this.data = data; this.next = next; } LinkedList.prototype = { // Adds new data to the list at the start of the list. push: function(data) { var newFirst = new LinkedList.Node(data, this.first); this.first = newFirst; }, // Removes the first element from the list. pop: function(data) { var popped = this.first; if (popped) { this.first = this.first.next; } return popped? popped.data : null; } } </syntax> ======= Support ======= <syntax js> // Initial starting list. // Add hashes manually for now. list = new LinkedList(); list.push("A"); list.push("B"); list.push("C"); function preRun() { if (!(list instanceof LinkedList)) { // Copy the list from data - used for web-workers. var mylist = new LinkedList(); mylist.first = list.first; // Replace the global 'list' with the converted one. list = mylist; } } </syntax> ======= Tests ======= <syntax js> function testPush() { var s = new LinkedList(); s.push(1); s.push(2); s.push(3); assert(s.pop() === 3); assert(s.pop() === 2); assert(s.pop() === 1); assert(s.pop() === null, "End of stack."); }</syntax> ======= Options ======= <syntax js> { "title": "Stack list-based", "height": "330px", "preRunSource": true, "persistentGlobals": ["list"] } </syntax> ======= Visualisation ======= <syntax html> <html> <head> <script src="http://d3js.org/d3.v3.js"></script> <link rel="stylesheet" type="text/css" href="algorithms-lib/list.css"/> <script src="algorithms-lib/list.js"></script> <script> function setup() { svg = d3.select("#result") .append("svg") .attr("width", 348) .attr("height", 400) .append("g").attr("transform", "translate(10.5, 20.5)"); listVis = new ListVisualisation(svg); returnText = svg.append("text") .attr("dx", "0") .attr("dy", "40"); } var listNodesToDisplay = []; var newNodesToDisplay = []; var nodeIndex = 1; var nodeConstructor; function idNode(node) { if (node.constructor === nodeConstructor && !node.hasOwnProperty("id")) { node.id = nodeIndex++; return true; } return false; } function updateList(x, clean, duration) { var list = x.lookupInScope("list"); var listNodes = []; var node = list.first; while (node) { listNodes.push(node); if (newNodesToDisplay.indexOf(node)!==-1) { newNodesToDisplay.splice(newNodesToDisplay.indexOf(node),1); delete node.isnew; } node = node.next; } if (clean) { listNodesToDisplay = listNodes; newNodesToDisplay = []; } else { // merge listNodes with listNodesToDisplay var displayI = 0; for (var i=0; i<listNodes.length; i++) { var newDisplayI = listNodesToDisplay.indexOf(listNodes[i]) if (newDisplayI === -1) { listNodesToDisplay.splice(displayI, 0, listNodes[i]); displayI++; } else { displayI = newDisplayI+1; } } } var nodes = newNodesToDisplay.concat(listNodesToDisplay); // Position and ensure every node has an id. var nX = 30; var nNewX = 80; var nY = 100; for (var i=0; i<nodes.length; i++) { idNode(nodes[i]); if (nodes[i].isnew) { nodes[i].x = nNewX; nodes[i].y = 20; nNewX += 60; } else { nodes[i].x = nX; nodes[i].y = nY; nX += 60; if (nX > 300) { nX = 30; nY += 60; } } } listVis.nodesToDisplay = nodes; listVis.pointersToDisplay = [{value:list.first, name:"first", x:15, y:20, id:-1}]; if (clean) { listVis.clear(duration); timeout = setTimeout(function() { updateList(x, false, 1000); }, 1000); } else { listVis.update(duration); } } var poppedMarker = {}; function globals() { // Return a unique marker that enables to identify when popped has not been set. return {"popped": poppedMarker}; } var hasRun = false; var timeout; function update(n, x, isRunning, duration) { // Capture new nodes created. nodeConstructor = x.lookupInScope("LinkedList").Node; if (idNode(x.thisObject)) { if (newNodesToDisplay.indexOf(x.thisObject) === -1 && listNodesToDisplay.indexOf(x.thisObject) === -1) { newNodesToDisplay.push(x.thisObject); x.thisObject.isnew = true; } } updateList(x, false, duration); if (!isRunning && hasRun && !timeout) { timeout = setTimeout(function() { updateList(x, true, 1000); }, 2000); } else if (timeout) { window.clearTimeout(timeout); timeout = undefined; } hasRun = true; document.getElementById("addButton").disabled = isRunning; document.getElementById("removeButton").disabled = isRunning; var poppedValue = x.lookupInScope("popped"); svg.selectAll(".data").classed("selected", function(d) {return d===poppedValue;}); returnText.text(function() { var text = ""; if (poppedValue !== poppedMarker) { text = "Popped: "+ (poppedValue && typeof poppedValue === "object"? poppedValue.data : poppedValue); } return text; }); returnText.attr("transform", function() { var lastNodeY = listNodesToDisplay.length > 0? listNodesToDisplay[listNodesToDisplay.length-1].y : 100; return "translate(0," + (lastNodeY) +")"; }); } function pushNode() { var data = document.getElementById('input').value; data = data.replace(/"/g, '\\\"'); runScript("list.push(\""+ data +"\")"); } function popNode() { runScript("popped = list.pop()"); } window.onload = function() { setup(); }; </script> </head> <body style="height:480px"> <button id="addButton" onclick="pushNode()">Push</button><button id="removeButton" onclick="popNode()">Pop</button> <input id="input" value="7"><br><br> <div id=result> </div> </body> </html> </syntax>