singly-linked-list.c

singly-linked-list.c

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//
// Singly Linked List
//
// node1(data, next[0x231213])----> node2(data, next[])-->node3(data, next)---> node4--->NULL
//avem 2 campuri = data si next un camp de referinta care retine adresa urmatorului node

typedef struct Node {

	int data;//key

	struct Node *next;//reference to next node	
} Node;


/* CREATE a node */

Node *createNode(int value ) {


       //alocam spatiu in HEAP pentru un Node de lista simplu inlantuita
	//returnam adresa in pointerul n catre Node
       Node *n = (Node*)malloc(sizeof(Node)); 

       if(!n) {
       	 fprintf(stderr, "Err: malloc failed");
       	 exit(EXIT_FAILURE);
       }

       //daca alocarea a fost facuta cu success
       n->data = value;
       n->next = NULL;

       return n;
}

void addToFront(Node **head, int value) {

	 if(*head == NULL) return;

     Node *n = createNode( value );

     n->next = *head;

     *head = n;
     
};

//LINKED LIST >>>>>      node1[1, next] ===> node2 [2,next] ===> node3[ 3, next]  ===> node4 [4,next = NULL] 
                                                                  //c                    
void addToBack(Node **head, int value) {
 
     Node *n = createNode( value );//createNode(10)

     //daca lista este goala
     if(*head == NULL) {

     	*head = n;

     	return;
     }


     Node *c = *head;

     while(c->next != NULL) c = c->next;

     c->next = n;  //1 2 3 4 5 6 7 8...-> 10
     //                           c->next = n (10,)
}
/*
      c->next = completezi zona de referinta

      ... = c->next (apelezi adresa nodului,)
*/

bool isEmpty(Node *head) {

	return head == NULL;
}


//citeste valoarea de pe pozitia pos; returneaza false daca pos este invalid
bool getAt(Node * head, int pos, int *out) {


	  if(pos < 0) return false;


	  for(Node *c = head; c!=NULL, c=c->next;) {

          if(pos == 0) {

          	 *out = c->data;

          	 return true;
          }
	  }

	  return false;
}


//returneaza lungimea listei
int length(Node *head) {

	int count = 0;

    /*
	Node * c = head;
	while(c!=NULL) {
		count++;
		c = c->next;
	}
	*/

	for(Node *c = head; c != NULL; c = c->next) count++;

		return count;
}

//node1 ->>node2--->> node3

//insereaza pe pozitia po (0 = inceput, length = sfarsit) . returneaza false daca pos este invalid
bool insertAt(Node **head, int pos, int value) {

    if(pos < 0 || pos > length(*head)) { 
        
        printf("Positia nu se afla in lista.\n");
    	return false;
    }    	


    if(pos == 0) {

    	addToFront(head, value);

    	return true;
    }

    Node *c = *head;

    for(int i = 0; i < pos - 1; ++i) c = c->next;

    Node *n = createNode( value );

    n->next = c->next;

    c->next = n;

    return true;
}	


//returneaza positia primei aparitii sau -1 daca nu exista
int search(Node *head, int value) {

     int pos = 0;

     for(Node * c = head; c != NULL; c = c->next, pos++) {

     	if(c->data == value) return pos;
     }   

     return -1;
}


void freeList(Node **head) {

     Node *c = *head;

     while( c != NULL ) {

     	Node *next = c->next;

     	free( c );

     	c = next;
     } 

     *head = NULL;

}

void update(Node *head, int oldBalue, int newValue) {

 
}

void reverse(Node **head) {


}

void display(Node *head) {

     //pentru key = 8, lista nu mai este vida deci poate sa-l adauge dupa nodul care are key 3
	if(head == NULL) {

		printf("Lista este GOALA! {}");
		return;
	}

	for(Node *c = head; c != NULL; c = c->next) {

		printf("%d", c->data);

		if(c->next) printf(" -> ");
	}

	printf(" -> NULL\n");
}


bool removeFront(Node **head) {

     if(*head == NULL) {

     	  return false;
     }   

     Node *tmp = *head;

     *head = (*head)->next; 

     free(tmp); 

     return true;
}

//HEAD = [10,next=NULL]
//HEAD = [10,next=NULL] ---> [11,next=NULL]
bool removeBack(Node **head) {
      
      if(*head == NULL) return false;

      if((*head)->next == NULL) {

      	   free(*head);

      	   *head = NULL;//lista vida//

      	   return true;
          
      }   

      Node *c = *head;

      while(c->next->next != NULL) c = c->next;

      free(c->next);

      c->next = NULL;
      //node[41,next=NULL]
}


//sterge prima aparitie a valorii, retuneaza false daca nu exista
//1 2 3 4 -1 5 6 7 
 //     |____|
// 
bool removeNode(Node **head, int removeKey) {

    if(*head == NULL) return false;

    if((*head)->data == removeKey) return removeFront( head );

    Node *c = *head;

    while(c->next != NULL && c->next->data != removeKey) c = c->next;

    Node *temp = c->next;

    c->next = temp->next;

    free( temp );

    return true;
}


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

   Node *head = NULL; //lista este empty

   int keys[] = {3,8,15,22,30,41,50};

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

   //keys[0] = 3 ...va fi HEAD 

   for(int i = 0; i < n; ++i) addToBack(&head, keys[i]);

   printf("%s\n", "Lista initiala");
   
   display(head);	

   insertAt(&head, 4, -1);

   display(head);	

   //sterge primul nod din lista
   //nodul 3 se afla la adresa 0x043543
   //temp = 0x043543
   //*head = (*head)->next (0x4444)
   //free(temp)

   if(removeFront(&head)) printf("\nPrimul Nodul s-a sters\n");
   else printf("Lista este goala , nu exista primul nod");

   if(removeBack(&head)) printf("\nUltimul Nodul s-a sters\n");
   else printf("Lista este goala, nu exista ultimul nod.");


   if(removeNode(&head, 22)) printf("\nNodul s-a sters nodul cu key 22\n");
   else printf("Lista este goala, nu exista ultimul nod.");

   if(removeNode(&head,8)) printf("\nNodul s-a sters nodul cu key 8\n");
   else printf("Lista este goala, nu exista ultimul nod.");


   printf("\nLista cu cheile ramase\n");
   display(head);

   //Sterge toata LISTA
   freeList( &head );
   printf("S-a sters toata lista\n");
   display( head );
   printf("\n");

	return 0;
}

/*

int keys[] = {3,8,15,22,30,41,50};

HEAD = NULL

node[3,NULL]

node[8,adresa nodului cu key 3]

nodul acum cu info 8 este HEAD

1 2 3 4  -1  5 6 7 8
      c   N  

      c->next aflu nodul de informatie 5

      n->next = c->next
      c->next = n

typedef struct Node {
	
	int data;
	Node *next;
}

typedef struct {
	
	Node *first;
	Node *last;

} SSL_LIST;

void initList(SSL_LIST *list) {
	
    list->first = NULL;
    list->last = NULL;
}

bool isEmpty(SSL_LIST *list) {

	return list->first ==  NULL;
}

int length(SSL_LIST *list) {
	

	int count = 0;

	for(Node *c = list->first; c != NULL; c = c->next) count++;

	return count;
}

................Lista secventiala...................
*/