From e5efa02c2746a4207251daf0173b4808dd087e89 Mon Sep 17 00:00:00 2001 From: leiyu3 Date: Tue, 13 Sep 2022 18:11:37 -0400 Subject: init --- .gitignore | 5 ++ Makefile | 16 +++++ liblinked_list.c | 179 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ linked_list.h | 22 +++++++ readme.md | 33 ++++++++++ 5 files changed, 255 insertions(+) create mode 100644 .gitignore create mode 100644 Makefile create mode 100644 liblinked_list.c create mode 100644 linked_list.h create mode 100644 readme.md diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..47c0732 --- /dev/null +++ b/.gitignore @@ -0,0 +1,5 @@ +a.out +linked_list_test* +*.a +*.o + diff --git a/Makefile b/Makefile new file mode 100644 index 0000000..9bf42df --- /dev/null +++ b/Makefile @@ -0,0 +1,16 @@ +CC=clang +CFLAGS=-Wall -g +BINS= linked_list.o liblinked_list.a linked_list_test +all: $(BINS) + +linked_list.o: linked_list.h liblinked_list.c + $(CC) $(CFLAGS) -c liblinked_list.c + +liblinked_list.a: liblinked_list.o + ar -cvq liblinked_list.a liblinked_list.o + +linked_list_test: linked_list_test.c liblinked_list.a + $(CC) $(CFLAGS) -o $@ $^ + +clean: + rm *.a *.o linked_list_test diff --git a/liblinked_list.c b/liblinked_list.c new file mode 100644 index 0000000..83689a5 --- /dev/null +++ b/liblinked_list.c @@ -0,0 +1,179 @@ +#include +#include +#include "linked_list.h" + +int count_ll(node* ptr){ + /* + Count the number of nodes in a linked list. + */ + // TODO:: What if there is 0 item in the linked list?? + int count = 0; + while (ptr != NULL){ + count++; + ptr = ptr->next; + } + return count; +} + +void prepend_ll(node **ptr, int value){ + /* + Add a node to the front of the linked list + */ + node* new = malloc(sizeof(node)); + new->value = value; + new->next = *ptr; + *ptr = new; + +} + +void append_ll(node* ptr, int value){ + /* + Add a node to the end of the linked list + */ + node* new = malloc(sizeof(node)); + new->value = value; + new->next = NULL; + while (ptr->next != NULL){ + ptr = ptr->next; + } + ptr->next = new; +} + +void print_ll(node* ptr){ + /* + Print out the linked list + */ + while (ptr != NULL){ + printf("%d", ptr->value); + ptr = ptr->next; + if (ptr == NULL){ + break; + } + printf(" - "); + } + printf("\n"); +} + +void free_ll(node* ptr){ + /* + Safely free all nodes inside linked list. + */ + node* next; + while (ptr->next != NULL){ + next = ptr->next; + free(ptr); + ptr = next; + } +} + +int update_node(node* ptr, int index, int value){ + /* + Update value of a node inside linked list + */ + // TODO:: What if the index is out of range? + + if (index >= count_ll(ptr)){ + // index out of range + return 1; + } + + int count = 0; + while (count < index){ + ptr = ptr->next; + count++; + } + + ptr->value = value; + return 0; +} + +int delete_node(node **ptr, int index){ + /* + Delete a node given the index + */ + + // TODO:: What if the node doesn't exist? + node* prev; + if (index == 0){ + prev = *ptr; + *ptr = (*ptr)->next; + free(prev); + return 0; + } + + node* root = *ptr; + for (int i = 0; i <= index; i++){ + if (i == index){ + prev->next = root->next; + free(root); + return 0; + } + prev = root; + root = root->next; + } + + printf("Node not found\n"); + exit(-1); +} + +int get_value(node *ptr, int index){ + /* + Get the value of a specific node given the index + */ + // TODO:: What if the index is out of range?? + + for (int i = 0; i < index; i++){ + ptr = ptr->next; + } + return ptr->value; + +} + +node* search_node(node *ptr, int value){ + /* + Search for a node given the value and returns it + */ + + while (1){ + if (ptr == NULL){ + fprintf(stderr, "Value doesn't exitst in linked list\n"); + exit(-1); + } + if (ptr->value == value){ + break; + } + ptr = ptr->next; + } + return ptr; +} + +void reverse_ll(node** ptr){ + node *prev, *cur, *next; + int n = count_ll(*ptr); + + if (n == 0){ + return; + } + + if (n == 1){ + return; + } + + prev = *ptr; + cur = prev->next; + next = cur->next; + prev->next = NULL; + + cur->next = prev; + + for (int i = 0; i < n-2; i++){ + prev = cur; + cur = next; + next = next->next; + cur->next = prev; + } + + + *ptr = cur; +} + diff --git a/linked_list.h b/linked_list.h new file mode 100644 index 0000000..1b2c3ca --- /dev/null +++ b/linked_list.h @@ -0,0 +1,22 @@ +#ifndef __LINKED_LIST_H__ +#define __LINKED_LIST_H__ + +typedef struct node node; +struct node{ + int value; + node* next; +}; + +int count_ll(node* ptr); +void prepend_ll(node **ptr, int value); +void append_ll(node* ptr, int value); +void print_ll(node* ptr); +void free_ll(node* ptr); +int update_node(node* ptr, int index, int value); +int delete_node(node **ptr, int index); +int get_value(node *ptr, int index); +node* search_node(node *ptr, int value); +void reverse_ll(node **ptr); + + +#endif diff --git a/readme.md b/readme.md new file mode 100644 index 0000000..c302e1b --- /dev/null +++ b/readme.md @@ -0,0 +1,33 @@ +# Linked List in C +This is a c library for linked list done as a learning project. + +The nodes stores integer values but can be switched to store any data you desire. + +Hopefully by viewing the source code you can learn how different operations on the linked list is implemented. + +# What has been implemented? + +First initialize your linked list like so: + +```c +node* ll = malloc(sizeof(node)); +ll->value = 1; +ll->next = NULL; +``` + +Then the following functions are available for you to interact with the linked list. + +These are the functions available in the header file. + +```c +int count_ll(node* ptr); +void prepend_ll(node **ptr, int value); +void append_ll(node* ptr, int value); +void print_ll(node* ptr); +void free_ll(node* ptr); +int update_node(node* ptr, int index, int value); +int delete_node(node **ptr, int index); +int get_value(node *ptr, int index); +node* search_node(node *ptr, int value); +void reverse_ll(node **ptr); +``` -- cgit v1.2.3