From ec3079e3f4a0124c744ec7e5b7a3fe78d2bbca77 Mon Sep 17 00:00:00 2001 From: oskar Date: Fri, 10 May 2024 23:41:25 +0200 Subject: Implemented doubly linked list, fixed issued with singly linked list. Added some nicer visualization for both of them. --- Makefile | 31 +++++++++++++++++++++++ d_linkedlist.c | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ linked | Bin 18320 -> 0 bytes linked.c | 56 ------------------------------------------ s_linkedlist.c | 64 ++++++++++++++++++++++++++++++++++++++++++++++++ test/Makefile | 6 +++++ 6 files changed, 177 insertions(+), 56 deletions(-) create mode 100644 Makefile create mode 100644 d_linkedlist.c delete mode 100755 linked delete mode 100644 linked.c create mode 100644 s_linkedlist.c create mode 100644 test/Makefile diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..ec5930a --- /dev/null +++ b/Makefile @@ -0,0 +1,31 @@ +CC=egcc +CFLAGS_TESTBIN=-O3 -Wfatal-errors -Wall -Werror -Wextra -g -Wpedantic -std=c99 +CFLAGS=-O3 -flto -march=native -DNDEBUG -fomit-frame-pointer -s -std=gnu99 +TARGET1=s_linkedlist +TARGET2=d_linkedlist +TESTTARGET1=s_linkedlist-t +TESTTARGET2=d_linkedlist-t +INSTALL_DIRECTORY=/usr/local/bin +MAKEFLAGS += -s +SRCSL=s_linkedlist.c +SRCDL=d_linkedlist.c + +all: release +clean: + rm -f $(TARGET1) $(TARGET2) + rm -f test/$(TESTTARGET1) test/$(TESTTARGET2) + +tests: + + $(CC) $(CFLAGS_TESTBIN) $(SRCSL) -o test/$(TESTTARGET1) + $(CC) $(CFLAGS_TESTBIN) $(SRCDL) -o test/$(TESTTARGET2) + echo "$(TESTTARGET) is done." + +release: + + $(CC) $(CFLAGS) $(SRCSL) -o $(TARGET1) + $(CC) $(CFLAGS) $(SRCDL) -o $(TARGET2) + + + + diff --git a/d_linkedlist.c b/d_linkedlist.c new file mode 100644 index 0000000..025bbb9 --- /dev/null +++ b/d_linkedlist.c @@ -0,0 +1,76 @@ +#include +#include +#include +#include +#include +#include +#include + +// Singly linked list demo + +struct waster { + int gg; + struct waster *prev; + struct waster *next; +}; + +struct waster *newnode () { + + struct waster *new = malloc(sizeof(struct waster)); + return new; +} + +struct waster *llist (uint64_t count) { + + struct waster *wr1 = malloc(sizeof(struct waster)); + struct waster *head = wr1; + wr1->gg = 0; // Data for first node + wr1->prev = NULL; // There is no previous node + wr1->next = newnode(); // Make new node, next points to it + struct waster *prv = wr1; // Make prv point to current node + wr1 = wr1->next; // Make wr1 point to next node + + + for (uint64_t i = 1 ; i < count ; i++) { // Actual loop starts + + wr1->gg = i; // Data for 2nd node + wr1->prev = prv; // make prev point to prv = wr1 = last node + if (i == count-1) { + wr1->next = NULL; + } else { + wr1->next = newnode(); // Make next node, next points to it + } + prv = wr1; // prv points to current node + wr1 = wr1->next; // Make wr1 point to the next node + + } + + wr1 = NULL; + return head; +} + +void freellist(struct waster *wr1) { + //printf("freelist \n"); + struct waster *save; + while (wr1 != NULL) { + save = wr1; + wr1 = wr1->next; + free(save); + } +} + +int main () { + + struct waster *wr1 = llist(20); + struct waster *p; + for (p = wr1 ; p != NULL ; p = p->next) { + void *prev = (void*)p->prev; + void *next = (void*)p->next; + printf("\n------%p----------",(void *)p); + printf("\ndata: %d\nprev: %p\nnext: %p\n", p->gg, prev, next); + printf("-----------------------------\n"); + } + + freellist(wr1); + return 0; +} diff --git a/linked b/linked deleted file mode 100755 index cbbae44..0000000 Binary files a/linked and /dev/null differ diff --git a/linked.c b/linked.c deleted file mode 100644 index 8f47a41..0000000 --- a/linked.c +++ /dev/null @@ -1,56 +0,0 @@ -#include -#include -#include -#include -#include -#include -#include - -struct waster { - int gg; - struct waster *next; -}; - -void *newnode () { - - struct waster *new = malloc(sizeof(struct waster)); - return new; -} - -struct waster *llist (uint64_t count) { - - struct waster *wr1 = malloc(sizeof(struct waster)); - struct waster *head = wr1; - for (uint64_t i = 0 ; i < count ; i++) { - - wr1->gg = i; - wr1->next = newnode(); // Make new node and assign address of the new node to the current one - wr1 = wr1->next; // Make save point to the next node - - } - - wr1->next = NULL; - return head; -} - -void freellist(struct waster *wr1) { - //printf("freelist \n"); - struct waster *save; - while (wr1 != NULL) { - save = wr1; - wr1 = wr1->next; - free(save); - } -} - -int main () { - - struct waster *wr1 = llist(10); - struct waster *p; - for (p = wr1 ; p->next != NULL ; p = p->next) { - printf("%d\n", p->gg); - } - - freellist(wr1); - return 0; -} \ No newline at end of file diff --git a/s_linkedlist.c b/s_linkedlist.c new file mode 100644 index 0000000..761a262 --- /dev/null +++ b/s_linkedlist.c @@ -0,0 +1,64 @@ +#include +#include +#include +#include +#include +#include +#include + +// Singly linked list demo + +struct waster { + int gg; + struct waster *next; +}; + +struct waster *newnode () { + + struct waster *new = malloc(sizeof(struct waster)); + return new; +} + +struct waster *llist (uint64_t count) { + + struct waster *wr1 = malloc(sizeof(struct waster)); + struct waster *head = wr1; + for (uint64_t i = 0 ; i < count ; i++) { + + wr1->gg = i; + if (i == count-1) { + wr1->next = NULL; + } else { + wr1->next = newnode(); // Make new node and assign address of the new node to the current one + } + wr1 = wr1->next; // Make save point to the next node + + } + + wr1 = NULL; + return head; +} + +void freellist(struct waster *wr1) { + //printf("freelist \n"); + struct waster *save; + while (wr1 != NULL) { + save = wr1; + wr1 = wr1->next; + free(save); + } +} + +int main () { + + struct waster *wr1 = llist(20); + struct waster *p; + for (p = wr1 ; p != NULL ; p = p->next) { + printf("\n------%p----------", (void*)p); + printf("\ndata: %d\nnext: %p\n", p->gg, (void*)p->next); + printf("-----------------------------\n"); + } + printf("\nHEAD: %p\n", (void*)wr1); + freellist(wr1); + return 0; +} diff --git a/test/Makefile b/test/Makefile new file mode 100644 index 0000000..48a5814 --- /dev/null +++ b/test/Makefile @@ -0,0 +1,6 @@ +all: release +clean: + cd .. && make clean + +release: + cd .. && make tests -- cgit v1.2.3