Hej wam, napisałem wreszcie działającą listę łączoną, program działa, wyniki są sprawdzone w mainie. Mam w planach ogarnąć cmocka do unit testów. Co sądzicie o tym, żeby sprawdzać w funkcjach pop_front
i pop_back
czy lista jest pusta? Jaką wartość powinna w tym przypadku otrzymać zmienna data
?
Kodzik:
main.c
#include <stdio.h>
#include "linked_list.h"
int main(void) {
printf("initializing list");
struct linked_list *list = ll_new();
ll_push_back(&list, 2);
ll_push_back(&list, 3);
printf("data after ll_push_bash:\n");
ll_print(list);
int data;
ll_pop_back(&list, &data);
ll_pop_back(&list, &data);
printf("data after 2x ll_pop_back: data=%d\n", data);
ll_print(list);
ll_push_front(&list, 3);
ll_push_front(&list, 4);
printf("data after ll_push_front:\n");
ll_print(list);
ll_pop_front(&list, &data);
ll_pop_front(&list, &data);
ll_print(list);
printf("data after 2x ll_pop_front: %d\n", data);
printf("inserting data into list:\n");
ll_push_front(&list, 1);
ll_push_front(&list, 2);
ll_push_back(&list, 3);
ll_print(list);
if (ll_contains(list, 3) > -1) {
printf("list contains element 3\n");
}
int idx = ll_find(list, 1);
if (idx > -1) {
printf("list contains element 1 at position %d\n", idx);
}
ll_destroy(list);
return 0;
}
linked_list.h
#ifndef LINKED_LIST_H
#define LINKED_LIST_H
#include <stdlib.h>
struct ll_node {
int data;
struct ll_node *prev;
struct ll_node *next;
};
struct linked_list {
struct ll_node *head;
struct ll_node *tail;
size_t size;
};
struct linked_list *ll_new(void);
int ll_destroy(struct linked_list *list);
int ll_push_back(struct linked_list **list, int data);
int ll_pop_back(struct linked_list **list, int *data);
int ll_push_front(struct linked_list **list, int data);
int ll_pop_front(struct linked_list **list, int *data);
int ll_find(struct linked_list *list, int data);
int ll_contains(struct linked_list *list, int data);
int ll_print(struct linked_list *list);
#endif //LINKED_LIST_H
linked_list.c
#include <stdio.h>
#include <stdlib.h>
#include "linked_list.h"
struct linked_list *ll_new(void) {
struct linked_list *list = malloc(sizeof(struct linked_list));
if (list == NULL) {
return NULL;
}
list->head = NULL;
list->tail = NULL;
list->size = 0;
return list;
}
int ll_destroy(struct linked_list *list) {
if (list == NULL) {
return -1;
}
if (list->head != NULL) {
struct ll_node *node = list->head;
while (node->next != NULL) {
node = node->next;
free(node->prev);
}
free(node);
}
free(list);
return 0;
}
int ll_push_back(struct linked_list **list, int data) {
if (list == NULL || *list == NULL) {
return -1;
}
struct ll_node *node = malloc(sizeof(struct ll_node));
if (node == NULL) {
return -1;
}
node->prev = (*list)->tail;
node->next = NULL;
node->data = data;
if ((*list)->size == 0) {
(*list)->head = node;
(*list)->tail = node;
} else {
(*list)->tail->next = node;
(*list)->tail = (*list)->tail->next;
}
++((*list)->size);
return 0;
}
int ll_pop_back(struct linked_list **list, int *data) {
if (list == NULL || *list == NULL) {
return -1;
}
if (data != NULL) {
*data = (*list)->tail->data;
}
if ((*list)->size > 1) {
struct ll_node *prev = (*list)->tail->prev;
free((*list)->tail);
(*list)->tail = prev;
(*list)->tail->next = NULL;
} else {
free((*list)->tail);
(*list)->tail = NULL;
(*list)->head = NULL;
}
--((*list)->size);
return 0;
}
int ll_push_front(struct linked_list **list, int data) {
if (list == NULL || *list == NULL) {
return -1;
}
struct ll_node *node = malloc(sizeof(struct ll_node));
node->data = data;
node->prev = NULL;
if ((*list)->size == 0) {
node->next = NULL;
(*list)->tail = node;
} else {
node->next = (*list)->head;
}
(*list)->head = node;
++((*list)->size);
return 0;
}
int ll_pop_front(struct linked_list **list, int *data) {
if (list == NULL || *list == NULL) {
return -1;
}
if (data != NULL) {
*data = (*list)->head->data;
}
if ((*list)->size > 1) {
struct ll_node *next = (*list)->head->next;
(*list)->head = next;
free((*list)->head->prev);
(*list)->head->prev = NULL;
} else {
free((*list)->head);
(*list)->head = NULL;
(*list)->tail = NULL;
}
--((*list)->size);
return 0;
}
int ll_find(struct linked_list *list, int data) {
int offset = 0;
struct ll_node *node = list->head;
while (node->next != NULL) {
if (node->data == data) {
return offset;
}
++offset;
node = node->next;
}
return -1;
}
int ll_contains(struct linked_list *list, int data) {
return ll_find(list, data) >= 0;
}
int ll_print(struct linked_list *list) {
if (list == NULL) {
return -1;
}
if (list->head == NULL) {
printf("list is empty\n");
return 0;
}
int n = 0;
struct ll_node *node = list->head;
while (node != NULL) {
printf("linked list node %d: %d\n", n, node->data);
node = node->next;
++n;
}
return 0;
}
lester29