This JavaScript Reference section displays the code for an example program that shows how to sort a circular linked list in JavaScript.
<!DOCTYPE html> <html> <head> <title>XoaX.net's Javascript</title> <script type="text/javascript" src="SortCircularLinkedList.js"></script> </head> <body onload="fnInitialization()"> <p id="idOutput"></p> </body> </html>
// The Link Constructor function CLink(qData) { this.mqData = qData; this.mqpNext = this; } // The Circular Linked List Constructor function CCircularLinkedList() { this.mqpTail = null; this.mfnInsertAtHead = function(qData) { var qNewLink = new CLink(qData); if (!this.mfnIsEmpty()) { qNewLink.mqpNext = this.mqpTail.mqpNext; this.mqpTail.mqpNext = qNewLink; } else { this.mqpTail = qNewLink; } } this.mfnInsertAtTail = function(qData) { var qNewLink = new CLink(qData); if (!this.mfnIsEmpty()) { qNewLink.mqpNext = this.mqpTail.mqpNext; this.mqpTail.mqpNext = qNewLink; } this.mqpTail = qNewLink; } this.mfnRemoveAtHead = function() { if (this.mfnIsEmpty()) { return false; } else if (this.mqpTail.mqpNext == this.mqpTail) { this.mqpTail = null; } else { this.mqpTail.mqpNext = this.mqpTail.mqpNext.mqpNext; } return true; } this.mfnIsEmpty = function() { return (this.mqpTail == null); } this.mfnHead = function() { return (this.mfnIsEmpty() ? null : this.mqpTail.mqpNext); } this.mfSwapNextTwo = function(qpNode) { var qSwap = qpNode.mqpNext.mqpNext; // If the tail node was swapped, we need change the tail. if (qSwap == this.mqpTail) { this.mqpTail = qpNode.mqpNext; } qpNode.mqpNext.mqpNext = qpNode.mqpNext.mqpNext.mqpNext; qSwap.mqpNext = qpNode.mqpNext; qpNode.mqpNext = qSwap; } } // The Iterator Constructor - for stepping through the linked list function CIterator(qNode) { this.mqpCurr = qNode; this.mfnForward = function() { return (this.mqpCurr = this.mqpCurr.mqpNext); } } function fnInitialization() { var saTribes = ["Reuben", "Simeon", "Levi", "Judah", "Issachar", "Zebulun", "Dan", "Naphtali", "Gad", "Asher", "Joseph", "Benjamin"]; var qpPrint = document.getElementById("idOutput"); qpPrint.innerHTML = ""; var qCircularLinkedList = new CCircularLinkedList(); // Print the tribes in the order of the array entries. for(var sCurrTribe of saTribes){ qpPrint.innerHTML += sCurrTribe + "<br />"; qCircularLinkedList.mfnInsertAtTail(sCurrTribe); } qpPrint.innerHTML += "---------------------------------------------<br />"; // Perform a bubblesort to sort the list var qIterator = new CIterator(qCircularLinkedList.mqpTail.mqpNext); var qLastNode = qCircularLinkedList.mqpTail; var bMadeSwap = true; // We only want to sort while swaps are being made. // A sorted list will only require one loop. while (bMadeSwap) { qIterator.mqpCurr = qCircularLinkedList.mqpTail; bMadeSwap = false; do { var qFirstComp = qIterator.mqpCurr.mqpNext; // localeCompare: -1 --> ordered, 0 --> equal, 1 --> out of order if (qFirstComp.mqData.localeCompare(qFirstComp.mqpNext.mqData) == 1) { // Swap the links that are out of order qCircularLinkedList.mfSwapNextTwo(qIterator.mqpCurr); bMadeSwap = true; // If the last node was swapped, we need to adjust it. if (qLastNode == qIterator.mqpCurr.mqpNext) { qLastNode = qLastNode.mqpNext; } } qIterator.mfnForward(); } while (qIterator.mqpCurr.mqpNext != qLastNode); // Reduce the length that we need to sort by one. qLastNode = qIterator.mqpCurr; } // Print the entries of the list in order. They should be sorted now. qIterator.mqpCurr = qCircularLinkedList.mqpTail.mqpNext; do { qpPrint.innerHTML += qIterator.mqpCurr.mqData + "<br />"; qIterator.mfnForward(); } while (qIterator.mqpCurr != qCircularLinkedList.mqpTail.mqpNext); }
© 20072024 XoaX.net LLC. All rights reserved.