lista simplu inlantuita Data Structure

singly-linked-list.cpp

/*
Singly Linked List (Lista Simplu Inlantuita)    (Grafuri-reprezentare prin liste de adiacenta)
--------------------------------------------

Doubly Linked List

Circular Linked List 

node1(info, next) ---> node2(info, next)---> node3(info, next)---> ....->nodeN(info, NULL)

/\
||
HEAD
*/
#include <iostream>
#include <stdio.h>
#include <malloc.h>

//--> vector<int> vec(10) 

//push_back(arr[i])

/*
Operatii:
- creare
- stergere
- adaugare dupa node
- adaugare inainte de node
- reverse
- sortare
*/

typedef struct Element {

	int a,
	    b;
} Element;


typedef struct Node {
	
	   int data; //zona de informatii
	   struct Node *next;// zona de referinta catre nodul urmator

	   //struct Node *prev; //transformam in lista dublu inlantuita
} Node;

Node *head = NULL;//declaram o lista simplu inlantuita cu HEAD null, 

//pointer catre struct---> pentru accesare date membre ->

void addToLinkedList( int val ) {

     if( head == NULL ) {

           //se aloca spatiu in HEAP //este o zona in memorie pentru alocare dinamica
           Node *new_node = (Node*)malloc(sizeof(Node)); //aloci spatiu in HEAP pentru un Node si adresa de inceput a nodului se transmite 
           //daca nu converteste la Node* , malloc returneaza pointer catre void (void*)

           //new Node()
           //pointerului new_node

           new_node->data = val;

           new_node->next = NULL; //nullptr;

           head = new_node;

     } else {

     	Node *new_node = (Node*)malloc(sizeof(Node));

     	new_node->data = val;

     	new_node->next = head; //pointeaza catre HEAD

     	head = new_node;
     }

}

void displaySinglyLinkedList(Node *head) {

//printf("%p", head);

	 Node *c = head;//pastram adresa capului listei simplu inlantuite

	 while( c != NULL) {

              printf("%d ", c->data);
              c = c->next; //semnificatia este urmatoare: se deplaseaza la nodul urmator
	 }

}
// NodeA, NodeB, NodeC, NodeD, NodeE,next=NULL;
// c = head
// a->data
// c = c->next

/*
       node1(next=adresa nodului 2)
 
                  node2(next=adresa nodului 3)
   

   Node3(next=adresa NULL)
*/

//1 21 3 41 5 6 7 8 9 
//          c
//head
//c = head

//addAfterNode(41, 42);


//9 1 2 3 4 5 6 7 8

void addAfterNode(int afterNode, int val) {

	  Node *c = head;

	  while( c->data != afterNode ) c = c->next;//ne pozitionam pe elementul dupa care vrem sa inseram

	  //se creeaza un nou NOD alocat in HEAP
	  //operatorul NEW in c++ malloc in C
	  Node *new_node = (Node*)malloc(sizeof(Node));
	  //Node* new_node = new Node;

	  new_node->data = val;//completez zona de informatie 

       //fac legaturile intre cele doua noduri
	  new_node->next = c->next;

	  c->next = new_node;

	  //c->next in partea stanga a semnului egal are semnificatia de camp NEXT, completezi zona de referinta

	  //c->next in partea dreapta semnului egal are semnificatia de nod
}

void addBeforeNode(int beforeNode, int val) {


	   Node *c;//luam adresa capului liste Simplu Inlantuite

	   struct Node * new_node = (Node*)malloc(sizeof(Node));

	   //avem doua cazuri: primul in care nodul de inserat este inainte de capul listei inainte HEAD

        //cazul in care este inainte de HEAD
	   if(head->data == beforeNode) {
          
          new_node->data = val;
          new_node->next = head;  
	   	  head = new_node;

       //cazul cand este in interiorul liste dupa HEAD
	   } else {

	   	  c = head;

	   	  while(c->next->data != beforeNode) c = c->next;
	   	  

	   	  //c = reprezinta nodul precedent nodului dupa care inseram

	   	  new_node->data = val;

	   	  new_node->next = c->next;

	   	  c->next = new_node;

	   }
}

//stergerea unui nod din Linked List

//free( adresa ptr ) //delete in c++

//LRU Cache Dublu inlantuita
void removeNode( int delNode ) {

   Node *ptr;


   //daca nodul este capul listei

   if( head->data == delNode ) {

   	   ptr = head;

   	   head = head->next;

   	   free( ptr );

   } else {

   	  Node*c = head;

   	  //ne pozitionam pe nodul de dinaintea nodului pe care vrem sa-l stergem si facem legatura intre 

   	  //A X C D

   	  //c

   	  while(c->next->data != delNode) c = c->next;

   	  //am gasit nodul de dinaintea nodului de sters si facem link-ul

   	  ptr = c->next; //nodul de sters
      
      //facem link
   	  c->next = ptr->next;//completezi zona de referinta a nodului

   	  free( ptr );//stergere nod efectiv

   }
}


Node* reverse(Node *head ) {
 
 std::cout<<"HEAD = "<<head->next<<"\n";
 std::cout<<"next HEAD = "<<head->next->next<<"\n";

      Node *curr = head, 

           *next, 

           *prev = NULL; //two pointers

      while( curr ) {

      	  next = curr->next;

      	  curr->next = prev;

      	  prev = curr;

      	  curr = next;
      }

      return prev;//adresa noului cap de lista

}
//12-> 11-> 10 ->91-> 8-> 71-> 6 ->53-> 4-> 3-> 22 ->1

//1->22-> 3-> 4 ->53-> 6-> 71->  8->  91->  10->  11->  12 ->NULL

//1 -> 21 ->  3 ->  41 -> 5 ->  6 -> 7 -> 8->  9 
//HEAD
//1 <- 21
                                              //HEAD
//          c


int main(int argc, char const *argv[])
{

	int arr[] = {1,22,3,4,53,6,71,8,91,10,11,12};

	//1 head
	//2(next=adresa nodului 1) head
	//3 (next=adresa nodului 2) head
	////.....


	int n = sizeof(arr) / sizeof(arr[0]);

	//addToLinkedList(arr[0])
	//addToLinkedList(arr[1])
	//1 --> 2

    for(int i = 0; i < n; ++i) addToLinkedList( arr[ i ] );

    printf("\n----------------\n");  
   	displaySinglyLinkedList( head );
   	printf("\n----------------\n");

    printf("\nAdaugare nodul de informatie 41 dupa un nodul de informatie 8!\n");
    //adaugare dupa nodul de informatie 5, adaugi nodul de informatie 41
    //addAfterNode(8, 41);

    //displaySinglyLinkedList( head );

printf("\n----------------\n");

//printf("Adaugare inainte de nodul informatie 12 dupa un nodul de informatie 88!\n");
    //Adaugare inainte de nodul informatie 1 dupa un nodul de informatie 88!
    //addBeforeNode(12, 88);

    //displaySinglyLinkedList( head );

//Element *el = (Element*)malloc(sizeof(Element));
//Element *el;//pointer catre struct Element
//Element *el = new Element;//creeaza in HEAP o zona pentru struct Element si adresa de inceput a blocului se transfer variabilei pointer "el"
//el->a = 1;
//el->b = 2;
//printf("%d %d", el->a, el->b);

    //printf("\n----------------\n");
    //printf("---------Stergere---");
    //printf("\n----------------\n");

    //std::cout<<"Nod de sters: \n";
    //int node_de_sters;
    //std::cin>>node_de_sters; 
    //removeNode( node_de_sters );

    //displaySinglyLinkedList(head);

    head = reverse(head);

    displaySinglyLinkedList(head);
	return 0;
}