-
I have a two pointer head and new. I have created one node in function
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node* next;
};
void ADD ( struct node *head, int value)
{
struct node * new = malloc(sizeof(*new));
if(new != NULL )
{
new -> data = value;
new -> next = NULL;
}
}
int main ()
{
struct node * head = NULL;
ADD(&head,4);
return 0;
}
new pointer point to current node in function. I want head pointer to point current node.
How the head ponter will change in function ?
-
Pass a pointer to the head variable to add() - make its type node**.
void add(struct node **head, int value) {
...
new->data = value;
new->next = *head;
*head = new;
}
Surprisingly, your main is already right, which means that the code that you posted wouldn't compile.
-
Pass a pointer to the head variable to add() - make its type node**.
Surprisingly, your main is already right, which means that the code that you posted wouldn't compile.
What does this line means ?
new->next = *head;
What happen in this situation ?
new->next = head;
-
In add(), head is a pointer to a pointer to a node. So *head is simply the pointer to a node pointed to by head.
In this example, head is a pointer to the head variable in main, so *head is the head variable in main.
What happen in this situation ?
new->next = head;
Nothing useful, try it ;)
-
I have a two pointer head and new. I have created one node in function
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node* next;
};
void ADD ( struct node *head, int value)
{
<===============================================>
struct node * new = malloc(sizeof(*new));
<===============================================>
if(new != NULL )
{
new -> data = value;
new -> next = NULL;
}
}
int main ()
{
struct node * head = NULL;
ADD(&head,4);
return 0;
}
new pointer point to current node in function. I want head pointer to point current node.
How the head ponter will change in function ?
It seems to me that you are only allocating a pointer to the struct, not an instance of the struct itself. Check how the sample code allocates a new item.
Here is some sample code https://www.tutorialspoint.com/data_structures_algorithms/linked_list_program_in_c.htm (https://www.tutorialspoint.com/data_structures_algorithms/linked_list_program_in_c.htm)
This stuff is all over the Internet and some of it might actually work.
-
struct node * new = malloc(sizeof(*new));
It seems to me that you are only allocating a pointer to the struct, not an instance of the struct itself.
No, malloc(sizeof *new) allocates enough memory for the struct pointed to by new.
If it were malloc(sizeof new) then it would only allocate enough for the pointer.
-
Consider the following example program:
#include <stdlib.h>
#include <stdio.h>
struct node
{
struct node *next;
int data;
};
struct node *node_new(int data)
{
struct node *n;
n = malloc(sizeof *n);
if (!n) {
fprintf(stderr, "node_new(): Out of memory.\n");
exit(EXIT_FAILURE);
}
n->next = NULL;
n->data = data;
return n;
}
void node_prepend(struct node **list, int data)
{
struct node *n;
if (!list) {
fprintf(stderr, "node_prepend(): NULL list pointer!\n");
exit(EXIT_FAILURE);
}
n = node_new(data);
n->next = *list;
*list = n;
}
void node_append(struct node **list, int data)
{
struct node *n;
if (!list) {
fprintf(stderr, "node_append(): NULL list pointer!\n");
exit(EXIT_FAILURE);
}
n = node_new(data);
if (*list) {
struct node *last = *list;
while (last->next)
last = last->next;
last->next = n;
} else {
/* List is empty. */
*list = n;
}
}
void node_printall(struct node *all, FILE *out)
{
if (out) {
const char *sep = "";
while (all) {
fprintf(out, "%s%d", sep, all->data);
all = all->next;
sep = ", ";
}
fprintf(out, "\n");
fflush(out);
}
}
void node_freeall(struct node **list)
{
if (list) {
struct node *next = *list;
*list = NULL;
while (next) {
struct node *n = next;
next = next->next;
n->next = NULL;
n->data = 0;
free(n);
}
}
}
int main(void)
{
struct node *mylist = NULL;
node_append(&mylist, 1);
node_append(&mylist, 2);
node_prepend(&mylist, 3);
node_append(&mylist, 4);
node_prepend(&mylist, 5);
node_prepend(&mylist, 6);
node_printall(mylist, stdout);
node_freeall(&mylist);
mylist = NULL;
return EXIT_SUCCESS;
}
Now, compare the node_prepend() and node_append() functions. The former prepends the new data to the list, whereas the latter appends the data to the list. Because both functions may modify the pointer to the first element in the list, they need to be passed a pointer to the pointer to the first element in the list.
The node_freeall() function also takes the pointer to the pointer to the first element in the list, because it frees each element in the list.
Because the node_printall() function only traverses the list without modifying anything, it takes a pointer to the first element in the list as a parameter.
-
If I am not mistaken this line de-referenced pointer head assign its value
new->next = *head;
here is head pointer modified by assigning value of new
*head = new;
-
If I am not mistaken this line de-referenced pointer head assign its value
new->next = *head;
here is head pointer modified by assigning value of new
*head = new;
Yes, in a function that takes a parameter struct node **head, which is a pointer to the pointer to the first element in the list.
Then, head is a pointer to the pointer to the first element in the list,
and *head is the pointer to the first element in the list.
Within the function, modifying head is not visible to the caller (because in C, we pass variables by value). But, modifying *head is. The idea, of course, is that the caller will pass a pointer to the variable it uses to point to the first element in the list, i.e. &mylist for head .
Put another way, if we have created node new to be inserted as the new first element in the list, we do
/* Hang off the original list from the new element, */
new->next = *head;
/* and update the pointer to the first element to point to the new element. */
*head = new;
When appending to the end of the list, we have two cases: If the list is empty, *head == NULL, and we set the pointer to the first element to point to the new element, *head = new;. Otherwise, the list is not empty, and it must have a last element; the one that has ->next == NULL. When we find that, we set that ->next = new.
-
Here is my code
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node* next;
};
void ADD ( struct node **head, int value)
{
struct node * new = malloc(sizeof(*new));
if(new != NULL )
{
new->data = value;
new->next = *head;
*head = new;
}
}
int main ()
{
struct node * head = NULL;
ADD(&head, 1);
printf(" Node 1 Data = %d \n", head -> data);
printf(" Node 1 Data = %p \n", &head -> data);
printf(" Node 1 next = %p \n", head -> next);
ADD(&head, 2);
printf(" Node 2 Data = %d \n", head -> data);
printf(" Node 2 Data = %p \n", &head -> data);
printf(" Node 2 next = %p \n", head -> next);
ADD(&head, 3);
printf(" Node 3 Data = %d \n", head -> data);
printf(" Node 3 Data = %p \n", &head -> data);
printf(" Node 3 next = %p \n", head -> next);
return 0;
}
Node 1 Data = 1
Node 1 Data = 00DB0D18
Node 1 next = 00000000
Node 2 Data = 2
Node 2 Data = 00DB0D48
Node 2 next = 00DB0D18
Node 3 Data = 3
Node 3 Data = 00DB0D58
Node 3 next = 00DB0D48
I see that pointer of current node point to the previous node but I want it to point the address of next node
How to point to address of next node in list
-
Of course all this is pretty "textbook" stuff. I haven't implemented dynamic lists in that way in ages. While this is certainly correct and flexible, this kind of implementation is - in general - pretty inefficient cache-wise.
Interestingly, I think the Linux kernel source code is full of those linked lists. But it mostly uses custom allocators AFAIK, so the cache issues can be mitigated, while if you use general-purpose allocators such as malloc(), things can get nasty pretty fast.
-
Consider a function pop() that detaches and returns a pointer to the first element in the list:
struct node *pop(struct node **list)
{
struct node *first;
/* Safety check, will not trigger in normal code */
if (list == NULL)
return NULL;
/* If the list is empty, return NULL. */
if (*list == NULL)
return NULL;
/* Detach the first element in the list: */
first = *list; /* Keep track of the original first element, */
*list = first->next; /* advance the list to start at the second element, */
first->next = NULL; /* and isolate the originally first element from the list. */
/* Return the now detached, originally first element in the list. */
return first;
}
The caller does need to free the popped element. If you just wish to discard the first element in the list, you can safely always do free(pop(&mylist));, because free(NULL); does nothing (and is safe to do).
The above is exactly equivalent to
struct node *pop(struct node **list)
{
struct node *first;
if (!list)
return NULL;
if (!*list)
return NULL;
first = *list;
*list = (*list)->next;
first->next = NULL;
return first;
}
in case you wonder.
Please also note how important descriptive comments are to the maintenance and understanding of the code.
Because I myself did not learn this when I learned to program on my own, I am still struggling with this. Do not repeat my mistake!
Learn to write comments that describe your intent as a programmer; to describe what you intend the code to do.
Writing comments that describe what the code does –– like "increment x by 5" –– are less than useless, because as programmers, we can read the code itself, we do not need to read that twice. (This means that the second comment, "If the list is empty, return NULL", is borderline; if I had written it as "If *list is NULL, return NULL", it would definitely be useless and annoying comment. Consider the difference between those two wordings, to see what I mean.)
It is the higher, more concept-level things, that the comments should describe.
I haven't implemented dynamic lists in that way in ages. While this is certainly correct and flexible, this kind of implementation is - in general - pretty inefficient cache-wise.
Yes, but this is a necessary step to grok (https://en.wikipedia.org/wiki/Grok) this stuff before one can advance to the cache-efficient and dedicated dynamic allocator stuff.
That is, I personally consider this thread as an example of how one would go about learning this stuff in C down to the "intuitive" level (where one uses these structures, even if they have their downsides, without much cognitive effort or worries), before advancing to the more interesting, more complicated dynamic memory stuff: step by step, one step at a time.
You certainly wouldn't want to tell someone who wasn't yet completely familiar with this kind of pointery stuff in C to implement and use their own specialized dynamic memory allocators, would you? :D
(Although, I must admit a good book on data structures in C –– see old threads in this sub-forum! –– would probably benefit OP more than this thread.)
Some of the actually real-world useful data structures, like binary heaps (https://en.wikipedia.org/wiki/Binary_heap), specifically min- and max-heaps implemented as an array, do not necessarily use pointers at all internally; but to make use of them, you end up needing to grok how pointers work in C anyway. (That is, do not expect that to be "easier" than any pointer stuff: it looks deceptively simple, but the rules of how to implement it a way that works reliably with other code, is not simple. There are lots and lots of implementation choices, but only a small subset of them work together well as a whole!)
My favourite example of this is a min-heap of event timestamps, to implement timeouts or timed events. Each element in the binary heap contains only a timestamp of the event, and a pointer or index to the event slot in an array or list of events. Each event slot contains a pointer or index back to the element; the two are linked bidirectionally to each other. As the heap is a min-heap, the root always contains the next event to occur. When it occurs, it is removed from the heap, and the event slot updated to indicate the event has elapsed. When the heap is modified, elements are percolated towards the root, and their links in the event slot updated to match.
I use that in real-world code, especially in systems programming (daemons and services written in C in a full blown OS like Linux or Windows), with a dedicated thread handling the timeout stuff. It runs only very rarely, most of the time waiting for the next event or an event cancelation/addition, and does not use much resources (CPU or memory) to do what it does; so it is a very, very efficient way to do it. On POSIXy systems, it can even interrupt blocking I/O calls in specific threads (delivering an internal POSIX signal).
However, the way the event in the heap and in the heap slot are two-way linked to each other, does mean one has to be very, very careful to make sure they remain consistent. The fact that they also need to be thread-safe, makes for a lot of options in locking options, some of them "interesting". (I do not actually know of a way to do this locklessly in a multithreaded environment). That "interesting" means that while some of the options look perfectly fine in a separate exercise or unit test, in real life use they cause a cascade of increasingly undesirable neighboring code. The simplest one, a single mutually exclusive lock (mutex) governing access to both the heap and the event slot list/array, works surprisingly well; anything more fine-grained needs a lot of applied experience to actually turn out better in real world work loads.
(Why binary min-heap for this? As Mark Allen Weiss shows in Algorithm Analysis and Data Structures in C (https://www.amazon.com/Data-Structures-Algorithm-Analysis-2nd/dp/0201498405), for uniformly random keys (timestamps), the number of percolation events (moving a heap entry towards or outwards from the root, level by level) on average is approximately e ≃ 2.718 per key addition or deletion, with an absolute maximum of log2N events for N existing entries in the heap. This makes it a very efficient choice. It also shows how important algorithm analysis is when choosing algorithms. Yet, unless you have the necessary skills to implement those algorithms in C, the analysis part is useless to you. The two –– implementing and analysis ––, should in my opinion, be developed almost in tandem, starting on the more mathematical analysis part as soon as one can implement all the basic abstract data structures in C.)
-
Algorithm Analysis and Data Structures in C
Sluuurp, I have a copy of this book in my shelf!
- Algorithms in C, Parts 1-4+5 in Bundle: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms by Robert Sedgewick, Hardcover
- Introduction to Algorithms, 3rd Edition MIT Press, by Thomas H. Cormen, Hardcover
Both hardcover premium version, perhaps a bit snob, but these books are worth to have, and they are worth the books face beautiful view of themselves on the shelf :D
-
I haven't implemented dynamic lists in that way in ages. While this is certainly correct and flexible, this kind of implementation is - in general - pretty inefficient cache-wise.
Yes, but this is a necessary step to grok (https://en.wikipedia.org/wiki/Grok) this stuff before one can advance to the cache-efficient and dedicated dynamic allocator stuff.
Of course! That's why I said "textbook". It's definitely needed as a learning step.
Just mentioned this, because I've actually seen many "experienced" developers still using this kind of structure mindlessly, not being aware of its shortcomings. And unfortunately, more "advanced" approaches that are more efficient/cache-friendly/... are often *not* taught at universities (except maybe in the most advanced courses), so unless one takes advanced CS courses, or one is otherwise interested in the topic and constantly learning (which should be the general case for engineers, but far from being that common), that may elude many people entirely.
For a short introduction to the matter, less experienced people can watch this:
https://www.youtube.com/watch?v=DyG9S9nAlUM (https://www.youtube.com/watch?v=DyG9S9nAlUM)
(the OP can watch it of course, but not before having mastered the concept of linked lists first! ;D )
-
A side track:
I recalled that when I first started learning about pointers in C, I wondered why the "handle" to the list was the same type as the pointers to individual list elements. That does not have to be the case, it just is the simplest case. Here is an example of a case where the handle does differ.
If one wants to both prepend and append to a singly-linked list efficiently, it makes sense to maintain a pointer to both the first and the last elements in the list. For example,
#include <stdlib.h>
#include <stdio.h>
struct list_item {
struct list_item *next;
int data;
};
struct list {
struct list_item *head; /* Or "first" */
struct list_item *tail; /* Or "last" */
};
#define LIST_INIT { NULL, NULL }
To declare a list variable, it is useful to initialize it to NULL pointers, which is what the LIST_INIT macro intends to help with:
struct list my_list = LIST_INIT; /* my_list is now an empty list. */
The common helper functions, for initializing a list (in case you want to do struct list my_list; list_init(&my_list); instead of the above, for any reason), allocating a new list item, and freeing an entire list, are for example
static void list_init(struct list *handle)
{
/* Safety check; could also be an assert() */
if (!handle) {
fprintf(stderr, "list_init(): NULL handle!\n");
exit(EXIT_FAILURE);
}
handle->head = NULL;
handle->tail = NULL;
}
static struct list_item *list_item_new(int data)
{
struct list_item *item;
item = malloc(sizeof *item);
if (!item) {
fprintf(stderr, "list_item_new(): Out of memory.\n");
exit(EXIT_FAILURE);
}
item->next = NULL;
item->data = data;
return item;
}
static void list_free(struct list *handle)
{
struct list_item *curr, *next;
if (!handle)
return;
next = handle->head;
handle->head = NULL;
handle->tail = NULL;
while (next) {
curr = next;
next = next->next;
/* 'Poison' list item to help detect use-after-free bugs. */
curr->next = NULL;
curr->data = 0;
free(curr);
}
}
In case you are wondering, I am naming the types and functions using pattern library_type_action, with list as the "library" name, list and list_item as the "type" names, and init, new, and free as "actions". Because C does not have namespaces (any way specify which library or header file a function name or type refers to), some variant of this kind of naming style is used to keep library-like function and type names from colliding with others.
Because the list is singly linked, it is very efficient to insert a new element at the beginning of the list, and to remove the element from the beginning of the list. Because we also have a pointer to the last element in the list, we can also insert an element to the end of the list. (To remove the element at the end of the list, however, we do need to traverse the entire list to find the element just before the last element, so that will stay inefficient/slow.)
static void list_push(struct list *handle, struct list_item *item)
{
/* Safety checks; could also be assert()s */
if (!handle) {
fprintf(stderr, "list_prepend(): NULL handle!\n");
exit(EXIT_FAILURE);
}
if (!item) {
fprintf(stderr, "list_prepend(): NULL list item!\n");
exit(EXIT_FAILURE);
}
if (!(handle->head)) {
item->next = NULL;
handle->head = item;
handle->tail = item;
} else {
item->next = handle->head;
handle->head = item;
}
}
static struct list_item *list_pop(struct list *handle)
{
struct list_item *item;
/* Safety check; could also be an assert() */
if (!handle) {
fprintf(stderr, "list_init(): NULL handle!\n");
exit(EXIT_FAILURE);
}
item = handle->head;
if (item) {
handle->head = item->next;
if (!handle->head)
handle->tail = NULL;
item->next = NULL;
}
return item;
}
static void list_append(struct list *handle, struct list_item *item)
{
/* Safety checks; could also be assert()s */
if (!handle) {
fprintf(stderr, "list_prepend(): NULL handle!\n");
exit(EXIT_FAILURE);
}
if (!item) {
fprintf(stderr, "list_prepend(): NULL list item!\n");
exit(EXIT_FAILURE);
}
if (!(handle->head)) {
item->next = NULL;
handle->head = item;
handle->tail = item;
} else {
item->next = NULL;
handle->tail->next = item;
handle->tail = item;
}
}
static struct list_item *list_trim(struct list *handle)
{
struct list_item *item, *prev;
/* Safety check; could also be an assert() */
if (!handle) {
fprintf(stderr, "list_init(): NULL handle!\n");
exit(EXIT_FAILURE);
}
item = handle->head;
/* List empty? */
if (!item)
return NULL;
prev = NULL;
/* Find the last item in the list, with prev being the previous item. */
while (item->next) {
prev = item;
item = item->next;
}
/* Only one item in the list? */
if (!prev) {
handle->head = NULL;
handle->tail = NULL;
return item;
}
/* Detach the item from the list. */
handle->tail = prev;
prev->next = NULL;
return item;
}
If we tie this together in an example program which again can print out the list structure in Graphviz DOT format,
static void list_dot(struct list *handle, FILE *out, const char *handle_name)
{
struct list_item *curr, *prev;
/* Safety checks; could also be assert()s */
if (!handle) {
fprintf(stderr, "list_dot(): NULL list handle!\n");
exit(EXIT_FAILURE);
}
if (!handle_name) {
fprintf(stderr, "list_dot(): NULL list handle name!\n");
exit(EXIT_FAILURE);
}
/* In order to make output optional easily in an application,
we allow out==NULL to indicate no output is wanted. */
if (!out)
return;
fprintf(out, "digraph {\n");
fprintf(out, " \"0\" [ shape=\"rect\", label=\"%s\" ];\n", handle_name);
/* Describe each list item first, then the edge to that list item. */
prev = NULL;
curr = handle->head;
while (curr) {
fprintf(out, " \"%p\" [ shape=\"oval\", label=\"%d\" ];\n", (void *)curr, curr->data);
if (prev)
fprintf(out, " \"%p\" -> \"%p\";\n", (void *)prev, (void *)curr);
prev = curr;
curr = curr->next;
}
/* Describe the head and tail edges last. */
fprintf(out, " \"0\" -> \"%p\" [ taillabel=\"head\" ];\n", (void *)(handle->head));
fprintf(out, " \"0\" -> \"%p\" [ taillabel=\"tail\" ];\n", (void *)(handle->tail));
fprintf(out, "}\n");
fflush(out);
}
int main(void)
{
struct list my_list = LIST_INIT;
list_push(&my_list, list_item_new(1));
list_push(&my_list, list_item_new(2));
list_push(&my_list, list_item_new(3));
list_dot(&my_list, stdout, "my_list");
list_free(&my_list);
return EXIT_SUCCESS;
}
the output is something like
[ my_list ]
head tail
│ │
3 │
╲ │
2 │
╲│
1 │
with all lines actually being arrows pointing down, if you use dot to display the output. As I use Linux, I use
gcc -Wall -Wextra -Wno-unused-function -O2 example.c -o ex && ./ex | dot -Tx11
to compile, run, and display the graph in one commmand.
If we append a list_append(&my_list, list_item_new(4)); in main(), just before list_dot(&my_list, stdout); line, we get
[ my_list ]
head tail
│ │
3 │
╲ │
2 │
╲ │
1 │
╲│
4
and so on.
-
A side track:
I recalled that when I first started learning about pointers in C, I wondered why the "handle" to the list was the same type as the pointers to individual list elements. That does not have to be the case, it just is the simplest case.
It doesn't have to, of course. But it has benefits (and pitfalls): any of the list element is itself a list. The recursive nature of this structure lends itself well to recursive algorithms and formal proofing.
You can absolutely do things differently. For efficiency reasons (except in maybe very particular cases), I often implement lists and trees with "arrays".
Then, unless the list is purely sequential or the tree is a pure binary tree, the "handle" contains an index to the root element, and each element indices to the children if needed. That can be a very effective structure cache-wise.
-
For efficiency reasons (except in maybe very particular cases), I often implement lists and trees with "arrays".
Yep. In molecular dynamics simulations, when a separate list of neighboring particles is maintained, it is usually one or more Verlet lists (https://en.wikipedia.org/wiki/Verlet_list). It is particularly useful with force field models (that chemists use to model proteins and such), where you have not only pairwise interactions, but also each unique triplet and quartet too; you reiterate over the same sublists quite a lot. The array form helps a lot with cache behaviour, due to data locality.
One of the more interesting data structures, and a related simple exercise, is to create a maze (an array where each cell can have a horizontal and/or a vertical wall at one side), and a disjoint-set data structure with a node per maze cell, to quickly find out if each cell in the maze is reachable from every other cell; and when not, how many such disjoint zones there are in the maze. This also works as a step into maze-solving and shortest-path algorithms, which are fun and interesting. The array form is much faster than the pointer/forest form.
For visualization of these, I recommend either SVG (if only generating visualization images), or the NetPBM (https://en.wikipedia.org/wiki/Netpbm) P6 (binary) image format (which is easy to write, read, and modify); I've shown example functions to read and write PPM P6 files in C in this post here (https://www.eevblog.com/forum/programming/generating-beautiful-fractals/msg3835088/#msg3835088).
The SVG output is particularly fun if you want to experiment with non-rectangular cells, like triangular or hexagonal lattices, or even irregular meshes using say a Delaunay triangulation of a set of more or less uniformly random points. Since SVG is just text (XML), they are easy to emit from a program, and one can use any browser to view the images. Here's an example of something closely related (and only 7k in file size, too):
(https://www.nominal-animal.net/answers/digit-grid.svg)
-
shortest-path algorithms
also good for { path-planning, feasible planning, optimal planning, forward search, backward search, bidirectional search, value iteration, logic-based planning, STRIPS, plan graph, planning as satisfiability } , maybe also for { Polygonal, polyhedral, and semi-algebraic models Rigid-body kinematic trees and nonrigid transformations }.
I don't have the budget to play with micro-robotics, but it looks like I won a kit from Lynxmotion, something like a 4-degree-of-freedom robotic arm, like this (https://www.robotshop.com/eu/en/lynxmotion-al5d-4-degrees-of-freedom-robotic-arm-combo-kit-no-software.html) one, of course with the cheapest set of motors, because you cannot be too lucky ;D
Anyway, cheap or not, it doesn't matter, I think this will offer a good opportunity to play with reverse cinematic and some of the above algorithms.
That data-structure is very useful :o :o :o