SinglyLinkedList Data Structure

SinglyLinkedList.java

/*

Array = 

int a 

Data Structures
---------------
Singly Linked List (Liste Simplu Inlantuite)
Double Linked List (Dublu)
Circular Linked List (Circulare)
Graph
Stack
Queue
Tree

Reprezentare grafuri prin liste de adiacenta (lista simplu inlantuita sau matricea de adiacenta)

1 1 1 1 
0 0 0 1 
1 1 1 1
1 1 0 0 

LRU Cache = get si put (System Design Job Interview) //lista dublu inlantuita

node1(info, next) 

info = zona de informatii
next = zona de referinta (tine minte adresa urmatorului Node din Linked List)

Ox231312
node1(info, next) ---> 
HEAD


            Ox231332
            node2(info, next) --->                    Ox2313343x2
                                                    node3(info, next)  ----> node3(info, next = NULL) LAST


node1(info, next=adresa node2) ---> node2(info, next= adresa node3) ---> node3(info, next=adresa node 4) ---> node4(info, next=NULL)  LAST

int c/c++
struct Node {
	
     int info;
     struct Node* next;
     Node(int v):info(v), next(nullptr){}
}

struct Node *head = NULL;//nullptr

in java?

HEAD              

- adaugare X

- stergere (node1 -> node2 ---> node3 ---->node4)
                          ptr = node3
- adaugare dupa un node (node1 -> node2 ---> nodeX --->node3 ---->node4)X

- adaugare inainte de un nodeX

- sortare --

- reverse --

- search --

1 2 3 4 5
reverse

6 7 17 8 94 54
remove(17)


1 2 3 4 -1
sortare


*/


public class SinglyLinkedList {

     static class Node {

     	  int data;
     	  Node next;

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

     Node head = null;

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

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

     	   Node newNode = new Node( val );

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

     	   	  head = newNode;
     	   	  //lista nu este vida

     	   //restul numerelor din array	  
     	   } else {

               newNode.next = head; //noul node pointeaza catre head

               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;
          }    
          //c = nodul de informatie 7, dupa care vreau sa adaug valoarea val

          if(c == null) {

          	System.out.println("Nodul cu info value nu este in lista s. in");
          	return;
          } 

          Node newNode = new Node( value );

          newNode.next = c.next;

          c.next = newNode;//0x123131
     }
     //1 2 3 4 5 6 7      newNODE  8
     //            c(next)
     //c.next in stanga semnului egal inseamna ca vei completa adresa de referinta a nodului c
     //c.next in dreapta semnului egal inseamna chiar nodul de la acea referinta

     //node1->node2->node3->node4
     //                     c

     void addBeforeNode(int beforeNode, int value) {

          Node newNode = new Node(value);   

          //cazul 1. in care adauga inainte de HEAD
          if(head != null && head.data == beforeNode) {

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

          //cazul 2. nodul cautat este inainte

          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 7 8 9
          //integrare

          //c = nodul precedent
          newNode.next = c.next;
          c.next = newNode;

     }
     /// node1, node2, node3,node4
     //  HEAD
     //  1 2 3 4
     // 0


     //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;
          	   return;
          } 

          //cazul 2: nodul de sters este in interiorul liste
          //ne pozitionam pe nodul precedent nodului de sters
          Node c = head;

          //HEAD = 1 2 3 4 5 6 7 8          
          //               c(inf,next) = c(next,next) 

          //legatura dintre c de informatie 5 si nodul de informatie 7
          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;
          }

          c.next = c.next.next; //sarim peste nodul de sters
     }

     /*
       1 -> 2 -> 3 -> 4 -> 5
       curr.next = null
       curr.next = prev
       HEAD  
       1 <- 2 <- 3 <- 4 <- 5 HEAD

     */

     Node reverse() {

          Node curr = head;

          Node prev = null;

          Node next; 
          while(curr != null) {

              next = curr.next; //salvam
              curr.next = prev;
              prev = curr;
              curr = next;

          }

          return prev;

     }

     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; //pastram adresa capului listei simplu inlantuite

     	  while(c != null) {

     	  	   System.out.print(c.data + " ");

               c = c.next;
     	  } 

     	  System.out.println("");
     }       

     public static void main(String[] args) {

          SinglyLinkedList list = new SinglyLinkedList();
         
          int[] arr = {1, 22, 3, 4, 53, 6, 7, 8, 10, 101, 53};

          //1 2 3 5 7

          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("REVERSE: ");
          Node c = list.reverse();
          
          while( c != null ) {

                 System.out.print(c.data + " ");

                 c = c.next;
          }
          //1 2 3 4 5 6 7
          // 
          
     }  
}

/*
multimi, grupuri, inele, corpuri, spatii vectoriale ----> limbajul formal pentru c++/java
*/