G2A Many GEOs
SHARE
TWEET

LockingLinkedList

Mouamle Apr 8th, 2020 137 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.concurrent.locks.Lock;
  2. import java.util.concurrent.locks.ReentrantLock;
  3.  
  4. /**
  5.  * Locking linked list allows it to be used by multiple threads without causing issues with concurrent modifications.
  6.  * This implementation uses locks to prevent other threads from using the list
  7.  * Locking has major performance drawbacks such as when a thread is accessing the list other threads that might wanna use it
  8.  * will end up waiting in line for the operations to be completed.
  9.  *
  10.  * @param <T> the type to be stored.
  11.  */
  12. public class LockingLinkedList<T> {
  13.  
  14.     private int size = 0;
  15.  
  16.     private Node<T> head;
  17.  
  18.     /**
  19.      * we use this lock at the beginning of a method call to make sure any other thread
  20.      * calling the method will have to wait for the one who called it before.
  21.      * <p>
  22.      * And at the end of the call to release the lock so the waiting thread can start executing the method
  23.      */
  24.     private final Lock lock = new ReentrantLock();
  25.  
  26.     /**
  27.      * Since this method has more than one return statement
  28.      * we would have to make sure we release the lock before every return statement
  29.      */
  30.     private boolean delete(T value) {
  31.         // Lock the method.
  32.         lock.lock();
  33.  
  34.         // Store head node
  35.         Node<T> prev = null;
  36.         Node<T> currNode = this.head;
  37.  
  38.         //
  39.         // CASE 1:
  40.         // If head node itself holds the key to be deleted
  41.  
  42.         if (currNode != null && value.equals(currNode.value)) {
  43.             this.head = currNode.next; // Changed head
  44.  
  45.             size--;
  46.  
  47.             // release the lock
  48.             lock.unlock();
  49.             return true;
  50.         }
  51.  
  52.         //
  53.         // CASE 2:
  54.         // If the key is somewhere other than at head
  55.         //
  56.  
  57.         // Search for the key to be deleted,
  58.         // keep track of the previous node
  59.         // as it is needed to change currNode.next
  60.         while (currNode != null && !value.equals(currNode.value)) {
  61.             // If currNode does not hold key
  62.             // continue to next node
  63.             prev = currNode;
  64.             currNode = currNode.next;
  65.         }
  66.  
  67.         // If the key was present, it should be at currNode
  68.         // Therefore the currNode shall not be null
  69.         if (currNode != null && prev != null) {
  70.             // Since the key is at currNode
  71.             // Unlink currNode from linked list
  72.             prev.next = currNode.next;
  73.  
  74.             size--;
  75.  
  76.             // release the lock
  77.             lock.unlock();
  78.             return true;
  79.         }
  80.  
  81.         //
  82.         // CASE 3: The key is not present
  83.         //
  84.  
  85.         // release the lock
  86.         lock.unlock();
  87.         return false;
  88.     }
  89.  
  90.     public void add(T value) {
  91.  
  92.         // lock the method
  93.         lock.lock();
  94.  
  95.         // Create a new node with given data
  96.         Node<T> newNode = new Node<>(value, null);
  97.  
  98.         // If the Linked List is empty,
  99.         // then make the new node as head
  100.         if (this.head == null) {
  101.             this.head = newNode;
  102.         } else {
  103.             // Else traverse till the last node
  104.             // and insert the newNode there
  105.             Node<T> last = this.head;
  106.             while (last.next != null) {
  107.                 last = last.next;
  108.             }
  109.  
  110.             // Insert the newNode at last node
  111.             last.next = newNode;
  112.         }
  113.         size++;
  114.  
  115.         // release the lock
  116.         lock.unlock();
  117.     }
  118.  
  119.     public int size() {
  120.         return size;
  121.     }
  122.  
  123.     public T head() {
  124.         return head.value;
  125.     }
  126.  
  127.     public T tail() {
  128.         Node<T> last = this.head;
  129.         while (last.next != null) {
  130.             last = last.next;
  131.         }
  132.  
  133.         return last.value;
  134.     }
  135.  
  136.     private static class Node<V> {
  137.  
  138.         V value;
  139.         Node<V> next;
  140.  
  141.         public Node(V value, Node<V> next) {
  142.             this.next = next;
  143.             this.value = value;
  144.         }
  145.  
  146.     }
  147.  
  148. }
RAW Paste Data
Ledger Nano X - The secure hardware wallet
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top