Core JavaScript

Sorting a Circular Linked List

This JavaScript Reference section displays the code for an example program that shows how to sort a circular linked list in JavaScript.

SortCircularLinkedList.html

<!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>

SortCircularLinkedList.js

// 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);
}
 

Output

 
 

© 2007–2024 XoaX.net LLC. All rights reserved.