tejasomina

SinglyLinkedList.java

Oct 26th, 2020
809
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package datastructures;
  2.  
  3. public class SinglyLinkedList<E> {
  4.  
  5.     class Node {
  6.         E key;
  7.         Node next;
  8.  
  9.         Node(E k) {
  10.             key = k;
  11.         }
  12.  
  13.         Node() {
  14.         }
  15.     }
  16.  
  17.     Node head; // next points to first element
  18.     Node tail; // next points to last element
  19.  
  20.     SinglyLinkedList() {
  21.         head = new Node();
  22.         tail = new Node();
  23.     }
  24.  
  25.     void print() {
  26.         Node temp = head.next;
  27.         while (temp != null) {
  28.             System.out.print(temp.key + " ");
  29.             temp = temp.next;
  30.         }
  31.         System.out.println();
  32.     }
  33.  
  34.     int size() {
  35.         int s = 0;
  36.         Node temp = head.next;
  37.         while (temp != tail) {
  38.             temp = temp.next;
  39.             s++;
  40.         }
  41.         return s;
  42.     }
  43.  
  44.     //Add to front
  45.     void pushFront(E k) {
  46.         Node n = new Node(k);
  47.         n.next = head.next;
  48.         head.next = n;
  49.         if (tail.next == null) tail.next = n;
  50.     }
  51.  
  52.     //Return front item
  53.     E topFront() {
  54.         return head.next.key;
  55.     }
  56.  
  57.     //Remove from front
  58.     void popFront() {
  59.         assert !empty();
  60.         head.next = head.next.next;
  61.         if (empty()) tail.next = null;
  62.     }
  63.  
  64.     void pushBack(E k) {
  65.         Node n = new Node(k);
  66.         tail.next.next = n;
  67.         tail.next = n;
  68.         if (head.next == null) head.next = n;
  69.     }
  70.  
  71.     E topBack() {
  72.         return tail.next.key;
  73.     }
  74.  
  75.     void popBack() {
  76.         assert !empty();
  77.         Node temp = head.next;
  78.         while (temp.next != tail.next) temp = temp.next;
  79.         temp.next = null;
  80.         tail.next = temp;
  81.         if (empty()) head.next = null;
  82.     }
  83.  
  84.     boolean find(E k) {
  85.         Node temp = head.next;
  86.         while (temp != null) {
  87.             if (temp.key == k) return true;
  88.             temp = temp.next;
  89.         }
  90.         return false;
  91.     }
  92.  
  93.     void erase(E k) {
  94.         Node temp = head;
  95.         while (temp != null) {
  96.             if (temp.next.key == k) {
  97.                 temp.next = temp.next.next;
  98.                 return;
  99.             }
  100.             temp = temp.next;
  101.         }
  102.     }
  103.  
  104.     boolean empty() {
  105.         return (head.next == null);
  106.     }
  107.  
  108.     void addBefore(Node node, E k) {
  109.         Node n = new Node(k);
  110.         n.next = node;
  111.         Node temp = head;
  112.         while (temp != null) {
  113.             if (temp.next == node) {
  114.                 temp.next = n;
  115.                 return;
  116.             }
  117.             temp = temp.next;
  118.         }
  119.     }
  120.  
  121.     void addAfter(Node node, E k) {
  122.         Node n = new Node(k);
  123.         n.next = node.next;
  124.         node.next = n;
  125.         if (tail.next == node) tail.next = n;
  126.     }
  127.  
  128.     Node getNode(E k) {
  129.         assert find(k);
  130.         Node temp = head.next;
  131.         while (temp != null) {
  132.             if (temp.key == k) return temp;
  133.             temp = temp.next;
  134.         }
  135.         return null;
  136.     }
  137.  
  138.  
  139.     public static void main(String[] args) {
  140.         SinglyLinkedList<Integer> sl = new SinglyLinkedList();
  141.         sl.pushFront(23);
  142.         sl.pushFront(35);
  143.         sl.pushFront(63);
  144.         sl.pushBack(32);
  145.         sl.print();
  146.         sl.addBefore(sl.getNode(35), 68);
  147.         sl.addAfter(sl.getNode(23), 76);
  148.         sl.addBefore(sl.getNode(63), 86);
  149.         sl.addAfter(sl.getNode(32), 64);
  150.         sl.print();
  151.         sl.erase(68);
  152.         sl.print();
  153.     }
  154. }
  155.  
RAW Paste Data