There is a beautiful morning. It's snowing. And I decided to write one more article.
Today it will be just simple article where I would like to present my version how singly linked list can be reversed in C.
At first we need to define our list:
In this code the variable data is some data. In our case its type is INTEGER (int). The variable next is a pointer to next element.
So, now we need to write a function that will print our list:
Because some functions return result which we don't want to use and if we don't want to see any warnings in some compilers I think we need to suppress potential warnings. Because of that I created macro called UNUSED. It's just explicit cast to void type.
Now we need to write functions which will reverse our list. I will write two functions.
The first function gets pointer to list, reverses this list and after that returns new pointer, but argument of this function is still without changes.
The second function gets pointer to pointer to list, reverses this list and after that returns new pointer but as argument (not through return). In other words this function will change input argument.
Currently we have function for printing, two functions for reversing and struct which describes our list. And now we have to write main function. This function also has to create our list. I would like to tell that it's just example so I will not read return code of some functions and I will not handle any memory errors and read errno.
By the way I could be not use UNUSED macro because I use gcc compiler and it does not argue if I don't read return code of printf or pust functions.
So currently we are able to assemble all code parts in one program.
Let's compile our code:
Shall we check?
So today we wrote simple code that reverses singly linked list in C without temporary lists or arrays. It's just simple task however you can meet it when you try to pass any interview.
Have a nice day my friends! And Happy coming New Year! :)
At first we need to define our list:
1 2 3 4 | typedef struct list_s { int data; struct list_s* next; } list_t, *list_p, **list_pp; |
In this code the variable data is some data. In our case its type is INTEGER (int). The variable next is a pointer to next element.
So, now we need to write a function that will print our list:
1 2 3 4 5 6 7 | void print_list(list_p l) { while(l) { UNUSED(printf("%d ", l->data)); l = l->next; } UNUSED(puts("")); } |
Because some functions return result which we don't want to use and if we don't want to see any warnings in some compilers I think we need to suppress potential warnings. Because of that I created macro called UNUSED. It's just explicit cast to void type.
1 | #define UNUSED(x) (void) x
|
Now we need to write functions which will reverse our list. I will write two functions.
The first function gets pointer to list, reverses this list and after that returns new pointer, but argument of this function is still without changes.
1 2 3 4 5 6 7 8 9 10 11 12 | list_p reverse_list(list_p l) { list_p new_head = NULL; while(l) { list_p next = l->next; l->next = new_head; new_head = l; l = next; }; return new_head; } |
The second function gets pointer to pointer to list, reverses this list and after that returns new pointer but as argument (not through return). In other words this function will change input argument.
1 2 3 4 5 6 7 8 9 10 11 12 13 | void reverse_list_self(list_pp l) { list_p new_head = NULL; list_p lst = *l; while(lst) { list_p next_lst = lst->next; lst->next = new_head; new_head = lst; lst = next_lst; } *l = new_head; } |
Currently we have function for printing, two functions for reversing and struct which describes our list. And now we have to write main function. This function also has to create our list. I would like to tell that it's just example so I will not read return code of some functions and I will not handle any memory errors and read errno.
By the way I could be not use UNUSED macro because I use gcc compiler and it does not argue if I don't read return code of printf or pust functions.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | int main() { list_p list = NULL; /* Fill */ for(unsigned int i = 10; i > 0; --i) { list_p el = malloc(sizeof(*list)); el->data = i; el->next = list; list = el; } print_list(list); list = reverse_list(list); print_list(list); reverse_list_self(&list); print_list(list); return EXIT_SUCCESS; } |
So currently we are able to assemble all code parts in one program.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 | #include <stdlib.h> #include <stdio.h> #define UNUSED(x) (void) x typedef struct list_s { int data; struct list_s* next; } list_t, *list_p, **list_pp; static void print_list(list_p l); static list_p reverse_list(list_p l); static void reverse_list_self(list_pp l); int main() { list_p list = NULL; /* Fill */ for(unsigned int i = 10; i > 0; --i) { list_p el = malloc(sizeof(*list)); el->data = i; el->next = list; list = el; } print_list(list); list = reverse_list(list); print_list(list); reverse_list_self(&list); print_list(list); return EXIT_SUCCESS; } void print_list(list_p l) { while(l) { UNUSED(printf("%d ", l->data)); l = l->next; } UNUSED(puts("")); } list_p reverse_list(list_p l) { list_p new_head = NULL; while(l) { list_p next = l->next; l->next = new_head; new_head = l; l = next; }; return new_head; } void reverse_list_self(list_pp l) { list_p new_head = NULL; list_p lst = *l; while(lst) { list_p next_lst = lst->next; lst->next = new_head; new_head = lst; lst = next_lst; } *l = new_head; } /* * The end of the file */ |
Let's compile our code:
$ ls -lah total 4.0K drwxr-xr-x 2 bodro bodro 20 Dec 29 13:47 . drwxr-xr-x 5 bodro bodro 92 Oct 1 2021 .. -rw-r--r-- 1 bodro bodro 1.1K Oct 1 2021 main.c $ gcc -Wall -Wextra -Wpedantic -o main main.c $ ls -lah total 20K drwxr-xr-x 2 bodro bodro 32 Dec 29 13:48 . drwxr-xr-x 5 bodro bodro 92 Oct 1 2021 .. -rwxr-xr-x 1 bodro bodro 16K Dec 29 13:48 main -rw-r--r-- 1 bodro bodro 1.1K Oct 1 2021 main.c $ file main main: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=087a2c8d0fd1b8fee07a6b84806ae9698ae84424, for GNU/Linux 3.2.0, not stripped $ strip --strip-all main $ file main main: ELF 64-bit LSB pie executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, BuildID[sha1]=087a2c8d0fd1b8fee07a6b84806ae9698ae84424, for GNU/Linux 3.2.0, stripped $ ls -lah total 20K drwxr-xr-x 2 bodro bodro 32 Dec 29 13:49 . drwxr-xr-x 5 bodro bodro 92 Oct 1 2021 .. -rwxr-xr-x 1 bodro bodro 15K Dec 29 13:49 main -rw-r--r-- 1 bodro bodro 1.1K Oct 1 2021 main.c $As we can see it was compiled correctly.
Shall we check?
$ ./main 1 2 3 4 5 6 7 8 9 10 10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 $OK. I hope you understand that our code works. :)
So today we wrote simple code that reverses singly linked list in C without temporary lists or arrays. It's just simple task however you can meet it when you try to pass any interview.
Have a nice day my friends! And Happy coming New Year! :)
Best regards,
Vasiliy V. Bodrov aka Bodro,
the 29-th of December, 2023.
