diff --git a/src/route/fib.cpp b/src/route/fib.cpp
index f61f6f4..4a82661 100644
--- a/src/route/fib.cpp
+++ b/src/route/fib.cpp
@@ -16,9 +16,6 @@
  *
  * You should have received a copy of the GNU General Public License along with
  * NLSR, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
- *
- * \author A K M Mahmudul Hoque <ahoque1@memphis.edu>
- *
  **/
 #include <list>
 #include <cmath>
@@ -72,7 +69,7 @@
                                                   m_table.end(),
                                                   bind(&fibEntryNameCompare, _1, name));
   if (it != m_table.end()) {
-    for (std::list<NextHop>::iterator nhit =
+    for (std::set<NextHop, NextHopComparator>::iterator nhit =
            (*it).getNexthopList().getNextHops().begin();
          nhit != (*it).getNexthopList().getNextHops().end(); nhit++) {
       //remove entry from NDN-FIB
@@ -110,8 +107,6 @@
                      ndn::nfd::ROUTE_FLAG_CAPTURE, 0);
     }
   }
-
-  entry.getNexthopList().sort();
 }
 
 void
@@ -156,9 +151,6 @@
 {
   _LOG_DEBUG("Fib::update called");
 
-  // Sort all of the next hops so lower cost hops are prioritized
-  allHops.sort();
-
   // Get the max possible faces which is the minumum of the configuration setting and
   // the length of the list of all next hops.
   unsigned int maxFaces = getNumberOfFacesForName(allHops);
@@ -239,7 +231,7 @@
        ++it) {
     _LOG_DEBUG("Cancelling Scheduled event. Name: " << it->getName());
     cancelScheduledExpiringEvent((*it).getExpiringEventId());
-    for (std::list<NextHop>::iterator nhit =
+    for (std::set<NextHop, NextHopComparator>::iterator nhit =
          (*it).getNexthopList().getNextHops().begin();
          nhit != (*it).getNexthopList().getNextHops().end(); nhit++) {
       //Remove entry from NDN-FIB
@@ -279,7 +271,7 @@
 Fib::removeHop(NexthopList& nl, const std::string& doNotRemoveHopFaceUri,
                const ndn::Name& name)
 {
-  for (std::list<NextHop>::iterator it = nl.getNextHops().begin();
+  for (std::set<NextHop, NextHopComparator>::iterator it = nl.getNextHops().begin();
        it != nl.getNextHops().end();   ++it) {
     if (it->getConnectingFaceUri() != doNotRemoveHopFaceUri) {
       //Remove FIB Entry from NDN-FIB
diff --git a/src/route/name-prefix-table-entry.cpp b/src/route/name-prefix-table-entry.cpp
index a9682ef..0306911 100644
--- a/src/route/name-prefix-table-entry.cpp
+++ b/src/route/name-prefix-table-entry.cpp
@@ -38,7 +38,7 @@
        it != m_rteList.end(); ++it)
   {
     // Add every next hop from each routing table entry to this entry's NHL.
-    for (std::list<NextHop>::iterator nhit =
+    for (std::set<NextHop, NextHopComparator>::iterator nhit =
            (*it).getNexthopList().getNextHops().begin();
          nhit != (*it).getNexthopList().getNextHops().end(); ++nhit)
     {
@@ -80,7 +80,7 @@
   else
   {
     (*it).getNexthopList().reset(); // reseting existing routing table's next hop
-    for (std::list<NextHop>::iterator nhit =
+    for (std::set<NextHop, NextHopComparator>::iterator nhit =
            rte.getNexthopList().getNextHops().begin();
          nhit != rte.getNexthopList().getNextHops().end(); ++nhit) {
       (*it).getNexthopList().addNextHop((*nhit));
diff --git a/src/route/name-prefix-table.cpp b/src/route/name-prefix-table.cpp
index e5199b0..5c18b77 100644
--- a/src/route/name-prefix-table.cpp
+++ b/src/route/name-prefix-table.cpp
@@ -53,7 +53,6 @@
     NamePrefixTableEntry entry(name);
     entry.addRoutingTableEntry(rte); // Add this RTE to this new NPT entry.
     entry.generateNhlfromRteList(); // Generate a list of next-hops from the RTE.
-    entry.getNexthopList().sort(); // Sort it.
 
     m_table.push_back(entry); // Add the new, completed entry into the main table.
 
@@ -68,8 +67,7 @@
     // Update the existing entry with the new RTE.
     it->addRoutingTableEntry(rte);
 
-    it->generateNhlfromRteList(); // Rebuild the list of next-hops
-    it->getNexthopList().sort(); // Sort it.
+    it->generateNhlfromRteList();
 
     // As above, inform the FIB of this fact.
     // We may possibly have a new best next-hop for this name prefix
@@ -122,7 +120,6 @@
     else {
       _LOG_TRACE(*it << " has other routing table entries; updating FIB with next hops");
       it->generateNhlfromRteList();
-      it->getNexthopList().sort();
 
       m_nlsr.getFib().update(name, it->getNexthopList());
     }
diff --git a/src/route/nexthop-list.cpp b/src/route/nexthop-list.cpp
index ed46b55..22046fd 100644
--- a/src/route/nexthop-list.cpp
+++ b/src/route/nexthop-list.cpp
@@ -19,8 +19,6 @@
  * NLSR, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
  **/
 
-#include <iostream>
-
 #include "common.hpp"
 #include "nexthop-list.hpp"
 #include "nexthop.hpp"
@@ -33,64 +31,37 @@
 using namespace std;
 
 static bool
-nexthopCompare(NextHop& nh1, NextHop& nh2)
+nexthopAddCompare(const NextHop& nh1, const NextHop& nh2)
 {
   return nh1.getConnectingFaceUri() == nh2.getConnectingFaceUri();
 }
 
 static bool
-nexthopRemoveCompare(NextHop& nh1, NextHop& nh2)
+nexthopRemoveCompare(const NextHop& nh1, const NextHop& nh2)
 {
   return (nh1.getConnectingFaceUri() == nh2.getConnectingFaceUri() &&
           nh1.getRouteCostAsAdjustedInteger() == nh2.getRouteCostAsAdjustedInteger()) ;
 }
 
-static bool
-nextHopSortingComparator(const NextHop& nh1, const NextHop& nh2)
-{
-  if (nh1.getRouteCostAsAdjustedInteger() < nh2.getRouteCostAsAdjustedInteger()) {
-    return true;
-  }
-  else if (nh1.getRouteCostAsAdjustedInteger() == nh2.getRouteCostAsAdjustedInteger()) {
-    return nh1.getConnectingFaceUri() < nh2.getConnectingFaceUri();
-  }
-  else {
-    return false;
-  }
-}
-
-/*!
-Add next hop to the Next Hop list
-If next hop is new it is added
-If next hop already exists in next
-hop list then updates the route
-cost with new next hop's route cost
-*/
-
 void
-NexthopList::addNextHop(NextHop& nh)
+NexthopList::addNextHop(const NextHop& nh)
 {
-  std::list<NextHop>::iterator it = std::find_if(m_nexthopList.begin(),
+  std::set<NextHop, NextHopComparator>::iterator it = std::find_if(m_nexthopList.begin(),
                                                  m_nexthopList.end(),
-                                                 ndn::bind(&nexthopCompare, _1, nh));
+                                                 ndn::bind(&nexthopAddCompare, _1, nh));
   if (it == m_nexthopList.end()) {
-    m_nexthopList.push_back(nh);
-    return;
+    m_nexthopList.insert(nh);
   }
-  if ((*it).getRouteCost() > nh.getRouteCost()) {
-    (*it).setRouteCost(nh.getRouteCost());
+  else if (it->getRouteCost() > nh.getRouteCost()) {
+    removeNextHop(*it);
+    m_nexthopList.insert(nh);
   }
 }
 
-/*!
-Remove a next hop only if both next hop face and route cost are same
-
-*/
-
 void
-NexthopList::removeNextHop(NextHop& nh)
+NexthopList::removeNextHop(const NextHop& nh)
 {
-  std::list<NextHop>::iterator it = std::find_if(m_nexthopList.begin(),
+  std::set<NextHop, NextHopComparator>::iterator it = std::find_if(m_nexthopList.begin(),
                                                  m_nexthopList.end(),
                                                  ndn::bind(&nexthopRemoveCompare, _1, nh));
   if (it != m_nexthopList.end()) {
@@ -99,17 +70,11 @@
 }
 
 void
-NexthopList::sort()
-{
-  m_nexthopList.sort(nextHopSortingComparator);
-}
-
-void
 NexthopList::writeLog()
 {
   int i = 1;
-  sort();
-  for (std::list<NextHop>::iterator it = m_nexthopList.begin();
+
+  for (std::set<NextHop, NextHopComparator>::iterator it = m_nexthopList.begin();
        it != m_nexthopList.end() ; it++, i++) {
     _LOG_DEBUG("Nexthop " << i << ": " << (*it).getConnectingFaceUri()
                << " Route Cost: " << (*it).getRouteCost());
diff --git a/src/route/nexthop-list.hpp b/src/route/nexthop-list.hpp
index 0c57ba3..77bd4e7 100644
--- a/src/route/nexthop-list.hpp
+++ b/src/route/nexthop-list.hpp
@@ -16,14 +16,11 @@
  *
  * You should have received a copy of the GNU General Public License along with
  * NLSR, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
- *
- * \author A K M Mahmudul Hoque <ahoque1@memphis.edu>
- *
  **/
 #ifndef NLSR_NEXTHOP_LIST_HPP
 #define NLSR_NEXTHOP_LIST_HPP
 
-#include <list>
+#include <set>
 #include <iostream>
 #include <boost/cstdint.hpp>
 
@@ -34,6 +31,21 @@
 
 namespace nlsr {
 
+struct NextHopComparator {
+  bool
+  operator() (const NextHop& nh1, const NextHop& nh2) const {
+    if (nh1.getRouteCostAsAdjustedInteger() < nh2.getRouteCostAsAdjustedInteger()) {
+      return true;
+    }
+    else if (nh1.getRouteCostAsAdjustedInteger() == nh2.getRouteCostAsAdjustedInteger()) {
+      return nh1.getConnectingFaceUri() < nh2.getConnectingFaceUri();
+    }
+    else {
+      return false;
+    }
+  }
+};
+
 class NexthopList
 {
 public:
@@ -45,7 +57,6 @@
   {
   }
 
-
   /*! \brief Adds a next hop to the list.
     \param nh The next hop.
 
@@ -54,18 +65,16 @@
     cost with new next hop's route cost
   */
   void
-  addNextHop(NextHop& nh);
+  addNextHop(const NextHop& nh);
 
-  /*! \brief Removes a next hop.
-    \param nh The next hop.
+  /*! \brief Remove a next hop from the Next Hop list
+      \param nh The NextHop we want to remove.
 
-    Remove a next hop only if both next hop face and route cost are same.
+    The next hop gets removed only if both next hop face and route cost are same.
   */
-  void
-  removeNextHop(NextHop& nh);
 
   void
-  sort();
+  removeNextHop(const NextHop& nh);
 
   size_t
   getSize()
@@ -79,14 +88,14 @@
     m_nexthopList.clear();
   }
 
-  std::list<NextHop>&
+  std::set<NextHop, NextHopComparator>&
   getNextHops()
   {
     return m_nexthopList;
   }
 
-  typedef std::list<NextHop>::iterator iterator;
-  typedef std::list<NextHop>::const_iterator const_iterator;
+  typedef std::set<NextHop, NextHopComparator>::iterator iterator;
+  typedef std::set<NextHop, NextHopComparator>::const_iterator const_iterator;
 
   iterator
   begin()
@@ -116,7 +125,7 @@
   writeLog();
 
 private:
-  std::list<NextHop> m_nexthopList;
+  std::set<NextHop, NextHopComparator> m_nexthopList;
 };
 
 } // namespace nlsr
diff --git a/src/route/nexthop.hpp b/src/route/nexthop.hpp
index 8c5ffd1..0aa5640 100644
--- a/src/route/nexthop.hpp
+++ b/src/route/nexthop.hpp
@@ -16,9 +16,6 @@
  *
  * You should have received a copy of the GNU General Public License along with
  * NLSR, e.g., in COPYING.md file.  If not, see <http://www.gnu.org/licenses/>.
- *
- * \author A K M Mahmudul Hoque <ahoque1@memphis.edu>
- *
  **/
 #ifndef NLSR_NEXTHOP_HPP
 #define NLSR_NEXTHOP_HPP
@@ -80,7 +77,7 @@
   }
 
   void
-  setRouteCost(double rc)
+  setRouteCost(const double rc)
   {
     m_routeCost = rc;
   }
diff --git a/tests/test-hyperbolic-calculator.cpp b/tests/test-hyperbolic-calculator.cpp
index 1d22028..664b006 100644
--- a/tests/test-hyperbolic-calculator.cpp
+++ b/tests/test-hyperbolic-calculator.cpp
@@ -152,7 +152,7 @@
   NexthopList& bHopList = entryB->getNexthopList();
   BOOST_REQUIRE_EQUAL(bHopList.getNextHops().size(), 2);
 
-  for (std::list<NextHop>::iterator it = bHopList.begin(); it != bHopList.end(); ++it) {
+  for (std::set<NextHop, NextHopComparator>::iterator it = bHopList.begin(); it != bHopList.end(); ++it) {
     std::string faceUri = it->getConnectingFaceUri();
     uint64_t cost = it->getRouteCostAsAdjustedInteger();
 
@@ -166,7 +166,7 @@
   NexthopList& cHopList = entryC->getNexthopList();
   BOOST_REQUIRE_EQUAL(cHopList.getNextHops().size(), 2);
 
-  for (std::list<NextHop>::iterator it = cHopList.begin(); it != cHopList.end(); ++it) {
+  for (std::set<NextHop, NextHopComparator>::iterator it = cHopList.begin(); it != cHopList.end(); ++it) {
     std::string faceUri = it->getConnectingFaceUri();
     uint64_t cost = it->getRouteCostAsAdjustedInteger();
 
diff --git a/tests/test-link-state-calculator.cpp b/tests/test-link-state-calculator.cpp
index 8cc00a7..e3a6b3e 100644
--- a/tests/test-link-state-calculator.cpp
+++ b/tests/test-link-state-calculator.cpp
@@ -244,7 +244,7 @@
   NexthopList& bHopList = entryB->getNexthopList();
   BOOST_REQUIRE_EQUAL(bHopList.getNextHops().size(), 1);
 
-  NextHop& nextHopForB = bHopList.getNextHops().front();
+  const NextHop& nextHopForB = *(bHopList.getNextHops().begin());
 
   BOOST_CHECK(nextHopForB.getConnectingFaceUri() == ROUTER_B_FACE &&
               nextHopForB.getRouteCostAsAdjustedInteger() == LINK_AB_COST);
@@ -256,7 +256,7 @@
   NexthopList& cHopList = entryC->getNexthopList();
   BOOST_REQUIRE_EQUAL(cHopList.getNextHops().size(), 1);
 
-  NextHop& nextHopForC = cHopList.getNextHops().front();
+  const NextHop& nextHopForC = *(cHopList.getNextHops().begin());
 
   BOOST_CHECK(nextHopForC.getConnectingFaceUri() == ROUTER_C_FACE &&
               nextHopForC.getRouteCostAsAdjustedInteger() == LINK_AC_COST);
diff --git a/tests/test-nexthop-list.cpp b/tests/test-nexthop-list.cpp
index 1ab18da..f4290ef 100644
--- a/tests/test-nexthop-list.cpp
+++ b/tests/test-nexthop-list.cpp
@@ -86,32 +86,77 @@
 
 BOOST_AUTO_TEST_CASE(TieBreaker)
 {
+  // equal-cost hops are sorted lexicographically
   NextHop hopA;
   hopA.setRouteCost(25);
-  hopA.setConnectingFaceUri("AAA");
+  hopA.setConnectingFaceUri("AAAZZ");
 
   NextHop hopZ;
   hopZ.setRouteCost(25);
-  hopZ.setConnectingFaceUri("ZZZ");
+  hopZ.setConnectingFaceUri("ZZA");
 
   NexthopList list;
   list.addNextHop(hopA);
   list.addNextHop(hopZ);
 
-  list.sort();
-
   NexthopList::iterator it = list.begin();
   BOOST_CHECK_EQUAL(it->getConnectingFaceUri(), hopA.getConnectingFaceUri());
 
   list.reset();
-
   list.addNextHop(hopZ);
   list.addNextHop(hopA);
 
-  list.sort();
-
   it = list.begin();
   BOOST_CHECK_EQUAL(it->getConnectingFaceUri(), hopA.getConnectingFaceUri());
+
+
+  // equal-cost and lexicographically equal hops are sorted by the length of their face uris
+  NextHop longUriHop;
+  longUriHop.setRouteCost(25);
+  longUriHop.setConnectingFaceUri("AAAAAA");
+
+  NextHop shortUriHop;
+  shortUriHop.setRouteCost(25);
+  shortUriHop.setConnectingFaceUri("AAA");
+
+  list.reset();
+  list.addNextHop(longUriHop);
+  list.addNextHop(shortUriHop);
+
+  it = list.begin();
+  BOOST_CHECK_EQUAL(it->getConnectingFaceUri(), shortUriHop.getConnectingFaceUri());
+}
+
+BOOST_AUTO_TEST_CASE(SortOnAddAndRemove)
+{
+  NexthopList list;
+
+  NextHop hopA("A", 10);
+  NextHop hopB("B", 5);
+  NextHop hopC("C", 25);
+
+  list.addNextHop(hopA);
+  list.addNextHop(hopB);
+  list.addNextHop(hopC);
+
+  BOOST_REQUIRE_EQUAL(list.getSize(), 3);
+
+  double lastCost = 0;
+  for (const auto& hop : list) {
+    BOOST_CHECK(hop.getRouteCost() > lastCost);
+    lastCost = hop.getRouteCost();
+  }
+
+  // removing a hop keep the list sorted
+  list.removeNextHop(hopA);
+
+  BOOST_REQUIRE_EQUAL(list.getSize(), 2);
+
+  lastCost = 0;
+  for (const auto& hop : list) {
+    BOOST_CHECK(hop.getRouteCost() > lastCost);
+    lastCost = hop.getRouteCost();
+  }
 }
 
 BOOST_AUTO_TEST_SUITE_END()