Linked List Class With Sort

From NAT, 7 Years ago, written in Java, viewed 744 times.
URL https://code.nat.moe/view/e14df2d7 Embed
Download Paste or View Raw
  1. public class linkedList<Type> {
  2.        
  3.     private theNode<Type> head;
  4.        
  5.     public linkedList () {
  6.         head = null;
  7.     }
  8.    
  9.     public boolean isEmpty () {
  10.         return head == null;
  11.     }
  12.  
  13.         public addStart (Type item) {
  14.                 head = new theNode<Type> (item, head);
  15.         }
  16.    
  17.     public Type removeStart () {
  18.         Type temp = getFirst();
  19.         head = head.next;
  20.         return temp;
  21.     }
  22.  
  23.         public addEnd (Type item) {
  24.                 if (head==null) addStart(item);
  25.                 else {
  26.                         theNode<Type> temp = head;
  27.                         while( temp.next != null ) temp=temp.next;
  28.                         temp.next = new theNode<Type> (item ,null);
  29.                 }
  30.         }
  31.  
  32.         public int searchElement (Type target) {
  33.                 theNode<Type> temp = head;
  34.                 int location=0;
  35.                 while( temp.next != target ) {
  36.                         location++;
  37.                         temp = temp.next;
  38.                 }
  39.         }
  40.  
  41.     public int getSize () {
  42.         theNode<Type> temp = head;
  43.         int size=0;
  44.         while( temp.next != null ) {
  45.             size++;
  46.             temp = temp.next;
  47.         }
  48.     }
  49.    
  50.     public Type getFirst () {
  51.         return head.data;
  52.     }
  53.  
  54.     public Type getData (int position) {
  55.         theNode<Type> temp = head;
  56.         for (int i=1; i<position; i++) temp = temp.next;
  57.         return temp.data;
  58.     }
  59.    
  60.     public void insert (Type key, Type toInsert) {
  61.         if (head == null) return;
  62.         if (head.data.equals(toInsert)) {
  63.             addStart(toInsert);
  64.             return;
  65.         }
  66.         theNode<Type> prev = null;
  67.         theNode<Type> current = head;
  68.         while (current != null && !current.data.equals(key)) {
  69.             prev = current;
  70.             current = current.next;
  71.         }
  72.         if (current != null) {
  73.             prev.next = new theNode<Type> (toInsert, current);
  74.         }
  75.     }
  76.  
  77.     public void exchange (Type tarKey, Type desKey) {
  78.         theNode<Type> current = head, last, beforeTar, beforeDes, tar, des;
  79.         while(current != null) {
  80.             if(current.data.equals(tarKey)) {
  81.                 beforeTar = last;
  82.                 tar = current;
  83.             } else {
  84.                 if(current.data.equals(desKey)) {
  85.                     beforeDes = last;
  86.                     des = current;
  87.                 }
  88.             }
  89.             last = current;
  90.             current = current.next;
  91.         }
  92.         des.next = beforeTar.next.next;
  93.         tar.next = beforeDes.next.next;
  94.         beforeTar.next = des;
  95.         beforeDes.next = tar;
  96.     }
  97.    
  98.     public void del (Type key) {
  99.         if (head.data.equals(key)) {
  100.             head = head.next;
  101.         }
  102.         theNode prev = null;
  103.         theNode current = head;
  104.         while (current != null && !current.data.equals(key)) {
  105.             prev = current;
  106.             current = current.next;
  107.         }
  108.         prev.next = current.next;
  109.     }
  110.    
  111.     public theNode<Type> sortList (theNode<Type> targetList) {
  112.         if(head == null || head.next == null) {
  113.             return;
  114.         }
  115.         int total = 0, midCounter = 0;
  116.         theNode<Type> temp = head,part1 = head,part2 = head,cuttingTemp = null;
  117.         while (temp != null) {
  118.             temp = temp.next;
  119.             total++;
  120.         }
  121.         int mid = total/2;
  122.         boolean alreadyCut = false;
  123.         while (part2 != null) {
  124.             midCounter++;
  125.             if (mid == midCounter) {
  126.                 cuttingTemp = part2.next;
  127.                 part2.next == null;
  128.                 alreadyCut = !alreadyCut;
  129.             }
  130.             if (alreadyCut) {
  131.                 part2 = cuttingTemp;
  132.             } else {
  133.                 part2 = part2.next;
  134.             }
  135.         }
  136.         theNode<Type> desList = mergeAndSortData (sortList (part1), sortList(cuttingTemp));
  137.     }
  138.    
  139.     public theNode<Type> mergeAndSortData (theNode<Type> desListPart1, theNode<Type> desListPart2) {
  140.         theNode<Type> thePart1 = desListPart1;
  141.         theNode<Type> thePart2 = desListPart2;
  142.         theNode<Type> theSortedHead = new theNode<Type> (100);
  143.         theNode<Type> thePartNew = theSortedHead;
  144.         while (thePart1 != null || thePart2 != null) {
  145.             if (thePart1 == null) {
  146.                 thePartNew.next = new theNode<Type> (thePart2.data);
  147.                 thePart2 = thePart2.next;
  148.                 thePartNew = thePartNew.next;
  149.             } else {
  150.                 if (thePart2 == null) {
  151.                     thePartNew.next = new theNode<Type> (thePart1.data);
  152.                     thePart1 = thePart1.next;
  153.                     thePartNew = thePartNew.next;
  154.                 } else {
  155.                     if (thePart1.data < thePart2.data) {
  156.                         thePartNew.next = new theNode<Type> (thePart1.data);
  157.                         thePart1 = thePart1.next;
  158.                         thePartNew = thePartNew.next;
  159.                     } else {
  160.                         if (thePart1.data == thePart2.data) {
  161.                             thePartNew.next = new theNode<Type> (thePart1.data);
  162.                             thePartNew.next.next = new theNode<Type> (thePart2.data);
  163.                             thePartNew = thePartNew.next.next;
  164.                             thePart1 = thePart1.next;
  165.                             thePart2 = thePart2.next;
  166.                         } else {
  167.                             thePartNew.next = new theNode<Type> (thePart2.data);
  168.                             thePart2 = thePart2.next;
  169.                             thePartNew = thePartNew.next;
  170.                         }
  171.                     }
  172.                 }
  173.             }
  174.         }
  175.         return theSortedHead.next;
  176.     }
  177.    
  178. }

Reply to "Linked List Class With Sort"

Here you can reply to the paste above

captcha