DLL_version2

dll.c

 //    Doubly Linked List
//                                 list->first->prev = NEWNODE
 //    NEWNODE[key, next, prev] [key, next, prev] ---> [key, next, prev] --->> .... --->> [key, next, prev] next= null
 //                         |      ^           ^
 //                         |      |           |
 //                         -------------------
//                   +------------+

/// 1 2 3 4 5 6 7
//  -------------> print
//  <-------------
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//************** STRUCTS ********************/
typedef struct _DLL_NODE {

	int key;
	struct _DLL_NODE *next; //succesor
	struct _DLL_NODE *prev; //predecesor

} DLL_NODE;

typedef struct {

	int key;
	DLL_NODE *first;
	DLL_NODE *last;

} DL_LIST;

//************** CREATE ********************/

//create NODE
static DLL_NODE *dll_create_node(int value) {

       DLL_NODE *node = NULL;

       node = (DLL_NODE*)malloc(sizeof(DLL_NODE));

       if(node == NULL) {

        fprintf(stderr, "%s\n", "Err: malloc failed");

       	exit(EXIT_FAILURE);
       }

       memset(node, 0, sizeof(DLL_NODE));//next = prev = NULL;

       node->key = value;

       return node;
}

//CREATE Double Linked List
DL_LIST *dll_create( void ) {

	   DL_LIST *list = NULL;


	   list = (DL_LIST*)malloc(sizeof(DL_LIST));

       if(list == NULL) {

        fprintf(stderr, "%s\n", "Err: malloc failed");

       	exit(EXIT_FAILURE);
       }

       memset(list, 0, sizeof(DL_LIST)); //first = last = NULL

	 return list;
}

/************** INSERT ***************/

void dll_insert_first(DL_LIST *list, int givenKey) {


	 DLL_NODE *node = dll_create_node( givenKey );

	 if(list->first == NULL) { //daca lista este vida atunci node este si first si last
	 	list->first = node;
	 	list->last = node;
	 } else {
	 	//daca lista nu este vida
	 	node->next= list->first;
	 	//nod nou si intra in fata
	 	list->first->prev = node;
	 	list->first = node;
	 }
}

void dll_insert_last(DL_LIST *list, int givenKey) {

    DLL_NODE *node = dll_create_node( givenKey );

	if(list->first == NULL) { //daca lista este vida atunci node este si first si last

	 	list->first = node;
	 	list->last = node;

	 } else {

	 	node->prev = list->last;
	 	list->last->next = node;
	 	list->last = node;
	 }

}

void dll_print_forward(const DL_LIST* list) {


        if(list->first == NULL) {

        	printf("Lista este GOALA! {}\n");

        	return;
        }

        printf("NULL <- ");

        for(DLL_NODE *p = list->first; p != NULL; p = p->next) {

            printf("%d", p->key);

            if(p->next) printf(" <-> ");
        }

        printf(" -> NULL\n");

}


void dll_print_backward(const DL_LIST* list) {


        if(list->first == NULL) {

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

        printf("NULL <- ");

        for(DLL_NODE *p = list->last; p != NULL; p = p->prev) {

            printf("%d", p->key);

            if(p->prev) printf(" <-> ");
        }

        printf(" -> NULL\n");

}


/*returneaza adresa nodului cu cheia givenKey , sau NULL daca nu exista*/
DLL_NODE *dll_search(const DL_LIST *list, int givenKey) {

  DLL_NODE *crt_node = list->first;

	while(crt_node != NULL) {

		 if(givenKey == crt_node->key) return crt_node;

		 crt_node = crt_node->next;
	}

	return NULL;
}

/*insereaza givenKey dupa nodul cu cheia afterKEy (nu face nimic daca nu exista)*/
void dll_insert_after_key(DL_LIST *list, int afterKey, int givenKey) {

      // 1 2 q(key=3, next, prev] <---[node=XX,next, prev]---> 4 5 6 7

	     DLL_NODE *q = dll_search( list, afterKey );

			 if(q == NULL) return; /*cheia nu exista */

			 DLL_NODE *node = dll_create_node( givenKey );

      node->prev = q;

      node->next = q->next;

			if(q->next != NULL) q->next->prev = node;

			q->next = node;

			if(q == list->last) list->last = node; //am inserat dupa ultimul node;

}

  // 1 2 3 4 5 6 7
	// beforekey = 4
	// q = adresa
	// q->next = nodul cu key 5
	//q ->prev = nodedul cu key 3
	//q->prev se refera la nodul cu key = 2
void dll_insert_before_key(DL_LIST *list, int beforeKey, int givenKey) {

	   DLL_NODE *q = dll_search(list, beforeKey);

		 if(q == NULL) return;

     DLL_NODE *node = dll_create_node( givenKey );

		 node->next = q;

		 node->prev = q->prev;

	   if(q->prev != NULL) q->prev->next = node;

		 else
		     list->first = node; //am inserat inainte de primul

		 q->prev = node;
}

/*sterge nodul p (presupunem ca p apartine liste )*/
// 1 2 3 <-4--> 5 6 7
//         P
// p
// p->next->next
// p->next->prev

// p->prev->next
// p->prev->prev
//       FREE

//       FREE

static void dll_delete_node(DL_LIST *list, DLL_NODE *p) {

        if(p->prev != NULL)

					  p->prev->next = p->next;
        else
					  list->first = p->next;

				if(p->next != NULL)

				     p->next->prev = p->prev;
				else

					  list->last = p->prev;

				free( p );//FREE SPACE HEAP MEMORY
}

void dll_delete_first( DL_LIST *list ) {

     if(list->first == NULL) return; //LISTA vida

		 dll_delete_node(list, list->first);
}

void dll_delete_last(DL_LIST *list) {

     if(list->last == NULL) return; //inseamna ca este lista vida

		 dll_delete_node(list, list->last);
}

void dll_delete_key(DL_LIST *list, int givenKey) {

       DLL_NODE *p = dll_search( list, givenKey );//returneaza adresa nodului care are key givenKey

			 if(p == NULL) return; //cheia nu exista in DLL

			 dll_delete_node(list, p);
}

/*
1 2 3 4 5 5 5 6 7 5 5

removeKey = 5
1 2 3 4 6 7
//removeKey = 5
reverse()
delete_all_keys()

/*
       DLL_NODE *p = lirst->FIRST
			 while(p != NULL) {
			     DLL_NODE *next = p->next;//salvezi inainte de FREE
					 if(p->key == givenKey) dll_delete_node(list, p);
					 p = next;


		   }
*/

void dll_clear(DL_LIST *list) {

	while(list->first != NULL) dll_delete_first(list);
}

void dll_destroy(DL_LIST **list) {

	  if(*list == NULL) return;

		dll_clear(*list);

		free(*list);

		*list = NULL;
}

int main(int argc, char const *argv[])
{
    DL_LIST *list = dll_create();
    //inserari
    dll_insert_last(list, 4);
    dll_insert_last(list, 1);
    dll_insert_last(list, 31);
    dll_insert_last(list, 13);
    dll_insert_last(list, 35);
		printf("Show: \n");
    dll_print_forward(list);
        dll_print_backward(list);

				//dll_insert_after_key(list, 35, 1111);
				dll_insert_before_key(list, 35, 99);

				printf("Show: \n");
				dll_print_forward(list);
						dll_print_backward(list);



						dll_delete_first(list);

						printf("Show after REMOVE FIRST: \n");
						dll_print_forward(list);
								dll_print_backward(list);

           dll_delete_last(list);
								printf("Show before REMOVE LAST: \n");
								dll_print_forward(list);
										dll_print_backward(list);

                   int nodeRemove = 13;
										dll_delete_key(list, nodeRemove);
												 printf("Show Doubly Linked List after removed key %d: \n", nodeRemove);
												 dll_print_forward(list);
														 dll_print_backward(list);

                             printf("\nFREE MEMORY DLL\n");
														 dll_destroy(&list);
	return 0;
}