Skip to content

Instantly share code, notes, and snippets.

@DCubix

DCubix/lde.c

Last active April 21, 2018 00:52
Show Gist options
  • Save DCubix/e6566aad92564607ef96fc775c1f0846 to your computer and use it in GitHub Desktop.
Save DCubix/e6566aad92564607ef96fc775c1f0846 to your computer and use it in GitHub Desktop.
Download ZIP
Lista Duplamente Encadeada
Raw
lde.c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct Node_t {
int value;
struct Node_t* next;
struct Node_t* prev;
} Node;
Node* node_new(int value) {
Node* node = (Node*) malloc(sizeof(Node));
node->value = value;
node->next = node->prev = NULL;
return node;
}
typedef struct DList_t {
Node* head;
Node* tail;
} DList;
DList* dlist_new() {
DList* list = (DList*) malloc(sizeof(DList));
list->head = list->tail = NULL;
return list;
}
void dlist_insert_head(DList* list, int value) {
Node* node = node_new(value);
if (list->head == NULL) {
list->head = list->tail = node;
} else {
node->next = list->head;
list->head->prev = node;
list->head = node;
}
}
void dlist_insert_tail(DList* list, int value) {
Node* node = node_new(value);
if (list->head == NULL) {
list->head = list->tail = node;
} else {
node->prev = list->tail;
list->tail->next = node;
list->tail = node;
}
}
void dlist_insert_sorted(DList* list, int value) {
Node* node = node_new(value);
if (list->head == NULL) {
list->head = list->tail = node;
} else {
Node* tmp = list->head;
// Encontra o nó, cujo valor é menor ou igual ao
// valor requisitado.
while (tmp->next != NULL && tmp->value <= value) {
tmp = tmp->next;
}
// Valor do nó atual é maior ou igual que o novo valor:
// Insere antes
if (tmp->value >= value) {
// 1.
// [2] [1] <-> [3] <-> [5
// 2.
// [1] - [2] - [3] <-> [5]
if (tmp->prev != NULL) {
// 3.
// [1] <-> [2] - [3] <-> [5]
tmp->prev->next = node;
node->prev = tmp->prev;
}
// 4.
// [1] <-> [2] <-> [3] <-> [5]
node->next = tmp;
tmp->prev = node;
if (tmp == list->head) {
list->head = node;
}
// Valor do nó atual é menor que o novo valor:
// Insere depois
} else if (tmp->value < value) {
if (tmp->next != NULL) {
tmp->next->prev = node;
node->next = tmp->next;
}
node->prev = tmp;
tmp->next = node;
if (tmp == list->head) {
list->head = node;
}
}
}
}
Node* dlist_find_node(DList* list, int value) {
if (list->head == NULL) return NULL;
if (list->head == list->tail) return list->head; // 1 elemento
Node* currH = list->head;
Node* currT = list->tail;
// Move os ponteiros Inicio e Fim até que um
// dos dois ache o valor requisitado.
// I============> <===========F
// [1] <-> [5] <-> [6] <-> [10] <-> [3] <-> [9]
while (currH != currT) {
if (currH != NULL && currH->value == value)
return currH;
else if (currH != NULL)
currH = currH->next;
if (currT != NULL && currT->value == value)
return currT;
else if (currT != NULL)
currT = currT->prev;
}
return NULL;
}
bool dlist_remove(DList* list, int value) {
Node* node = dlist_find_node(list, value);
if (node == NULL) return false;
if (node->prev == NULL) { // Remove do Inicio
Node* tmp = list->head;
list->head = list->head->next;
list->head->prev = NULL;
free(tmp);
return true;
} else if (node->next == NULL) { // Remove do Fim
Node* tmp = list->tail;
list->tail = list->tail->prev;
list->tail->next = NULL;
free(tmp);
return true;
} else {
Node* prev = node->prev;
Node* next = node->next;
prev->next = next;
next->prev = prev;
free(node);
return true;
}
return false;
}
bool dlist_find(DList* list, int value) {
return dlist_find_node(list, value) != NULL;
}
void dlist_print(DList* list) {
printf("[");
Node* curr = list->head;
while (curr != NULL) {
if (curr->next == NULL) {
printf("%d", curr->value);
} else {
printf("%d, ", curr->value);
}
curr = curr->next;
}
printf("]\n");
}
void dlist_clear(DList* list) {
Node* curr = list->tail;
while (curr != NULL) {
Node* prev = curr->prev;
free(curr);
curr = prev;
}
list->head = list->tail = NULL;
}
int main(int argc, char** argv) {
srand(time(NULL));
printf("=== Lista Duplamente Encadeada ===\n\n");
DList* list = dlist_new();
for (int i = 0; i < 50; i++) {
dlist_insert_sorted(list, rand() % 50);
}
printf("=== Insercao Ordenada ===\n");
dlist_print(list);
printf("=== Busca ===\n\tValor: ");
int val = -1;
scanf("%d", &val);
if (dlist_find(list, val)) {
printf("\t[ Valor Encontrado! ]\n");
} else {
printf("\t[ Valor Nao Encontrado! ]\n");
}
dlist_clear(list);
for (int i = 0; i < 10; i++) {
dlist_insert_tail(list, rand() % 10);
}
printf("=== Insercao ===\n");
dlist_print(list);
for (int i = 0; i < 10; i++) {
int rem = rand() % 10;
if (dlist_remove(list, rem)) {
printf("\tRemovido: %d\n", rem);
}
}
printf("=== Remocao ===\n");
dlist_print(list);
dlist_clear(list);
free(list);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment