Doubly Linked List

doubly-link-list.java

public class DoublyLinkedList {

     static class Node {

          int data;
          Node next;
          Node prev;

          Node(int data) {
               this.data = data;
               this.next = null;
               this.prev = null;
          }
     }

     Node head = null;

     // node <->
     // head = null
     // addToLinkedList(1)  -> node1(prev=NULL, 1, next=NULL)
     // addToLinkedList(33) -> node2(prev=NULL, 33, next=node1) <-> node1(prev=node2, 1, next=NULL)
     // addToLinkedList(12) -> node3(prev=NULL, 12, next=node2) <-> node2(prev=node3, 33, next=node1) <-> node1(prev=node2, 1, next=NULL)

     // 12 <-> 33 <-> 1
     void addToLinkedList(int val) {

          Node newNode = new Node(val);

          // primul element
          if (head == null) {

               head = newNode;

          // restul elementelor
          } else {

               newNode.next = head;  // noul node pointeaza catre head
               head.prev = newNode;  // head-ul vechi pointeaza inapoi catre noul node
               head = newNode;       // facem head noul node
          }
     }

     // 1 5 6 7 8 10
     // HEAD
     //         c
     void addAfterNode(int afterNode, int value) {

          Node c = head;

          while (c != null && c.data != afterNode) {
               c = c.next;
          }

          if (c == null) {
               System.out.println("Nodul cu info value nu este in lista d. in");
               return;
          }

          Node newNode = new Node(value);

          newNode.next = c.next;   // noul node pointeaza catre succesorul lui c
          newNode.prev = c;        // noul node pointeaza inapoi catre c

          if (c.next != null) {
               c.next.prev = newNode; // succesorul lui c pointeaza inapoi catre noul node
          }

          c.next = newNode;        // c pointeaza catre noul node
     }

     // node1 <-> node2 <-> node3 <-> node4
     //                               c
     void addBeforeNode(int beforeNode, int value) {

          Node newNode = new Node(value);

          // cazul 1: adaugam inainte de HEAD
          if (head != null && head.data == beforeNode) {

               newNode.next = head;
               head.prev = newNode;
               head = newNode;
               return;
          }

          // cazul 2: nodul cautat este in interior
          Node c = head;

          while (c != null && c.next != null && c.next.data != beforeNode) {
               c = c.next;
          }

          if (c == null || c.next == null) {
               System.out.println("Nodul nu este gasit");
               return;
          }

          // 1 <-> 2 <-> 3 <-> 4 -> NEWNODE <-> 5 <-> 6
          // integrare

          newNode.next = c.next;   // noul node pointeaza catre c.next
          newNode.prev = c;        // noul node pointeaza inapoi catre c

          if (c.next != null) {
               c.next.prev = newNode; // succesorul pointeaza inapoi catre noul node
          }

          c.next = newNode;        // c pointeaza catre noul node
     }

     // 1 2 3 4 5
     // HEAD = HEAD.next
     // 2 3 4 5
     void removeNode(int delNode) {

          if (head == null) {
               System.out.println("Lista este goala");
               return;
          }

          // cazul 1: nodul de sters este HEAD
          if (head.data == delNode) {
               head = head.next;
               if (head != null) {
                    head.prev = null; // noul head nu mai are precedent
               }
               return;
          }

          // cazul 2: nodul de sters este in interiorul listei
          Node c = head;

          while (c.next != null && c.next.data != delNode) {
               c = c.next;
          }

          if (c.next == null) {
               System.out.println("Nodul cu valoare delNode nu exista");
               return;
          }

          // sarim peste nodul de sters
          Node nodeToDelete = c.next;
          c.next = nodeToDelete.next;

          if (nodeToDelete.next != null) {
               nodeToDelete.next.prev = c; // succesorul nodului sters pointeaza inapoi catre c
          }
     }

     /*
       1 <-> 2 <-> 3 <-> 4 <-> 5
       curr.next = null
       curr.next = prev
       curr.prev = next
       HEAD
       1 -> 2 -> 3 -> 4 -> 5 HEAD  (inainte)
       5 -> 4 -> 3 -> 2 -> 1 HEAD  (dupa reverse)
     */
     Node reverse() {

          Node curr = head;
          Node temp = null;

          while (curr != null) {

               temp = curr.prev;        // salvam prev-ul
               curr.prev = curr.next;   // prev devine next
               curr.next = temp;        // next devine fostul prev
               curr = curr.prev;        // avansam (fostul next)
          }

          // noul head este ultimul nod vizitat inainte de a iesi din while
          if (temp != null) {
               head = temp.prev;
          }

          return head;
     }

     void sort() {

          if (head == null || head.next == null) return;

          boolean swapped;

          do {

               swapped = false;

               Node c = head;

               while (c.next != null) {

                    if (c.data > c.next.data) {

                         int temp = c.data;
                         c.data = c.next.data;
                         c.next.data = temp;

                         swapped = true;
                    }

                    c = c.next;
               }

          } while (swapped); // repeta cat timp avem swapp-uri
     }

     void display() {

          Node c = head;

          while (c != null) {

               System.out.print(c.data);

               if (c.next != null) System.out.print(" <-> ");

               c = c.next;
          }

          System.out.println("");
     }

     // afisare inversa (de la coada la cap) - bonus pentru lista dublu inlantuita
     void displayReverse() {

          Node c = head;

          if (c == null) {
               System.out.println("");
               return;
          }

          // mergem pana la coada
          while (c.next != null) {
               c = c.next;
          }

          // parcurgem inapoi folosind prev
          while (c != null) {

               System.out.print(c.data);

               if (c.prev != null) System.out.print(" <-> ");

               c = c.prev;
          }

          System.out.println("");
     }

     public static void main(String[] args) {

          DoublyLinkedList list = new DoublyLinkedList();

          int[] arr = {1, 22, 3, 4, 53, 6, 7, 8, 10, 101, 53};

          for (int val : arr) {
               list.addToLinkedList(val);
          }

          // afisare lista
          list.display();

          System.out.println("Adaugare dupa NODE");
          list.addAfterNode(53, 11);
          list.display();

          System.out.println("Adaugare inainte NODE");
          list.addBeforeNode(1, -1);
          list.display();

          System.out.println("STERGERE NODE: ");
          list.removeNode(6);
          list.display();

          System.out.println("\nLista Sortata: ");
          list.sort();
          list.display();

          System.out.println("AFISARE INVERSA (fara reverse): ");
          list.displayReverse();

          System.out.println("REVERSE: ");
          Node c = list.reverse();

          while (c != null) {
               System.out.print(c.data + " ");
               c = c.next;
          }

          System.out.println("");
     }
}