I have a linked list structure
struct node {
int data;
node next;
}
and a function
struct node *insert_sorted (struct node *nodes,
int d) {
// todo
}
I need to implement this so that, given a new piece of data, it constructs a new node and inserts into the linked list in sorted order.
The first thing I want to check inside of the insert_sorted function is whether nodes points to nothing or something. By that I don't mean checking whether the pointer is NULL, which I'm familiar with. I mean that I want to check whether the address nodes holds a node struct or not. I think if this were Java I might be able to write
if (nodes == null) {
...
}
but I don't think there is an analogous thing to do in C.
I know that I could try to manage the nodes pointer so that, if it is non-null then it always points to some struct. I'll probably end up doing this.
But I just want to know if there exists a more direct way of solving the issue. Is there any way to take a given non-null pointer and check whether it points to anything or not?
How to test a C pointer for whether it points to a struct
In short, you use your code for this. And logic. As far as the language can go you can not know nothing about it. A pointer is just a variable. It's contents: an address. It could the NULL, it could be a valid address, it could not even be initialized at all. After a free a pointer will still point to non-existing data...
I have a linked list structure
struct node {
int data;
node next;
}
You have not. This is just a struct for a node. A node is not a list, a list is not a node.
You can for sure name it LinkedList and write a correct program around that, with an actual linked list. But it is not an abstraction for a linked list. It seems to be just a node of a possible linked list of nodes that contains an int value inside each one.
A linked list is a --- possibly empty --- collection of nodes. And it has nothing to do with the data it lists. Each node by its turn contains (or points to) a single unit of data, usually said to be a record.
If your description does not show that your code will be more complicated, less useful and harder to test. You will need loose pointers to beginning of list, counters for size, sometimes pointers to the tail and so on. And code reuse will be complicated.
struct node *insert_sorted (struct node *nodes,
int d) {
// todo
}
The first thing I want to check inside of the insert_sorted function is whether nodes points to nothing or something. By that I don't mean checking whether the pointer is NULL, which I'm familiar with. I mean that I want to check whether the address nodes holds a node struct or not. I think if this were Java I might be able to write
Well, java has no notion of pointers. You can check if a thing is or it is not constructed.
One way to see the problem here is to consider that you want to insert data into a list. It should not even exist the notion of a node to begin with. The abstraction here is not good. Consider
int so_insert ( int data, List* list);
It could take the value and insert into the list. Return 0 if ok, or a negative status number for an error.
insert_sorted as a name may be a bit over: once you have the notion of order you can have only one insert. A second sort criteria would ruin the order for the first one anyway.
These are possible node AND list:
typedef struct st_node
{ struct st_node* prev; // links
struct st_node* next;
int data; // data
} Node;
typedef struct
{
size_t size;
Node* tail;
Node* head;
} List; // a (possibly empty) list of nodes
Node here is in fact a node, List is a list and have the essential metadata: head, tail and size.
Some operations on List:
List* so_create();
List* so_destroy(List*);
int so_insert(int, List*);
int so_push_back(int, List*);
int so_push_front(int, List*);
int so_print(List*, const char* msg);
int so_sort(List*);
// helper for multi insert
int so_multi_insert(
List* list, const unsigned N, ...);
In general we would have a compare function to implement the sorting criteria, and a pointer to it could be in the list. Also the node would point to and not contain a data record. But this is only an example.
About the operations:
push_back and push_front are the C++ names for inserting at tail and head of the listinsert uses ascending order heresort function is also implementedmulti_insert is also hereprint accepts an optional title to help avoid the classical many printf calls in testing#include "List.h"
int main(void)
{
size_t N = 10;
List* my_list = so_create();
srand(240627);
for (int i = 0; i < N; i += 1)
so_push_back(rand() % 1000, my_list);
so_print(my_list, "\nelements back-inserted\n");
for (int i = 0; i < N; i += 1)
so_push_front(rand() % 1000, my_list);
so_print(my_list, "\n elements inserted at front\n");
so_sort(my_list);
so_print(my_list, "\nList is now sorted\n");
so_multi_insert(my_list, 4, -1, -2, -3, -4);
so_push_front(-5, my_list);
so_push_back(-6, my_list);
so_print(my_list, "\n(-6..-1) inserted\n");
so_sort(my_list);
so_print(my_list, "\nList is again sorted\n");
so_destroy(my_list);
return 0;
}
This one calls many of the functions to insert data at front and back and then sort the list.
list created
elements back-inserted
#10 elements in list.
head element: 161
tail element: 413
161 31 680 991 329 746 705 839 886 413
[-----]
elements inserted at front
#20 elements in list.
head element: 491
tail element: 413
491 269 901 863 944 886 243 318 81 682 161 31 680 991 329 746 705 839 886 413
[-----]
List is now sorted
#20 elements in list.
head element: 31
tail element: 991
31 81 161 243 269 318 329 413 491 680 682 705 746 839 863 886 886 901 944 991
[-----]
(-6..-1) inserted
#26 elements in list.
head element: -5
tail element: -6
-5 -4 -3 -2 -1 31 81 161 243 269 318 329 413 491 680 682 705 746 839 863 886 886 901 944 991 -6
[-----]
List is again sorted
#26 elements in list.
head element: -6
tail element: 991
-6 -5 -4 -3 -2 -1 31 81 161 243 269 318 329 413 491 680 682 705 746 839 863 886 886 901 944 991
[-----]
list deleted
#include "List.h"
#include <stdlib.h>
int main(void)
{
List* my_list = so_create();
srand(240628);
// here use use insert to test ordering
const int N = 20;
for (int i = 0; i < N; i += 1)
so_insert(rand()%1000, my_list);
so_print(my_list, "\nsorted\n");
so_destroy(my_list);
return 0;
}
This one just calls insert to insert some data, print and delete the list.
list created
sorted
#20 elements in list.
head element: 21
tail element: 913
21 100 125 164 248 265 282 286 310 534 558 629 673 689 777 779 817 876 912 913
[-----]
list deleted
List.h#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct st_node
{ struct st_node* prev; // links
struct st_node* next;
int data; // data
} Node;
typedef struct
{
size_t size;
Node* tail;
Node* head;
} List; // a (possibly empty) list of nodes
List* so_create();
List* so_destroy(List*);
int so_insert(int, List*);
int so_push_back(int, List*);
int so_push_front(int, List*);
int so_print(List*, const char* msg);
int so_sort(List*);
// helper for multi insert
int so_multi_insert(
List* list, const unsigned N, ...);
List.c#include "List.h"
// helper to sort
Node* so_locate_at(List*, size_t);
List* so_create()
{
List* list = malloc(sizeof(List));
if (list == NULL) return NULL;
list->head = NULL;
list->tail = NULL;
list->size = 0;
fprintf(stderr, "list created\n");
return list;
}
List* so_destroy(List* del)
{
if (del == NULL) return NULL; // no list
for (size_t i = 0; i < del->size; i += 1)
{ // delete nodes, 1 by 1
Node* save = del->head->next;
free(del->head);
del->head = save;
};
free(del); // delete list
fprintf(stderr, "list deleted\n");
return NULL;
}
int so_insert(int item, List* list)
{
int result = so_push_back(item, list);
if (result != 0) return result; // could not insert...
if (list->size == 1) return 0; // was the 1st
// at least 2
Node* p = list->tail;
for (size_t i = 0; i < list->size - 1; i += 1)
{
if (p->data >= p->prev->data)
{
p = p->prev;
continue;
};
// swap the nodes
int save = p->data;
p->data = p->prev->data;
p->prev->data = save;
p = p->prev;
}
return 0;
}
// return a pointer to the node at position 'pos'
// or 'NULL'. 'pos'starts at 0
Node* so_locate_at(List* list, size_t pos)
{
if (list == NULL) return NULL;
if (list->size < 1 + pos) return NULL;
Node* nd = list->head;
for (size_t i = 0; i < pos; i += 1) nd = nd->next;
return nd;
}
// insert all words in the list, sorted
int so_multi_insert(List* list, const unsigned N, ...)
{
if (list == NULL) return -1;
va_list args;
va_start(args, N);
for (size_t i = 0; i < N; i += 1)
so_insert(va_arg(args, int), list);
va_end(args);
return 0;
}
// inserts 'item' at the tail of the list
int so_push_back(int item, List* list)
{
if (list == NULL) return -1; // no list
Node* node = (Node*)malloc(sizeof(Node));
if (node == NULL) return -2; // no alloc
node->data = item;
if (list->size == 0) // first node
{
node->next = NULL;
node->prev = NULL;
list->size = 1;
list->head = node;
list->tail = node;
return 0; // 1st node
};
node->next = NULL;
node->prev = list->tail;
list->tail->next = node;
list->tail = node;
list->size += 1;
return 0;
}
// inserts 'Item' at the head of the list
int so_push_front(int item, List* list)
{
if (list == NULL) return -1; // no list
Node* node = (Node*)malloc(sizeof(Node));
if (node == NULL) return -2; // no alloc
node->data = item;
if (list->size == 0)
{
node->next = NULL;
node->prev = NULL;
list->size = 1;
list->head = node;
list->tail = node;
return 0; // 1st node
};
node->prev = NULL;
node->next = list->head;
list->head->prev = node;
list->head = node;
list->size += 1;
return 0;
}
int so_print(List* list, const char* msg)
{
if (list == NULL)
{
fprintf(stderr, "No valid list!\n");
return 0;
}
if (list->size == 0) return 0;
if (msg != NULL) printf("%s", msg);
printf(
"\
#%llu elements in list.\n\
head element: %d\n\
tail element: %d\n\n",
list->size, list->head->data, list->tail->data);
Node* p = list->head;
for (size_t i = 0; i < list->size; i += 1)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n\n[-----]\n\n");
return 0;
}
int so_sort(List* list)
{
if (list == NULL) return -1;
if (list->size < 2) return -2;
Node* p = list->tail;
for (Node* q = list->tail; q != list->head; q = q->prev)
for (Node* p = q->prev; p != NULL; p = p->prev)
if (q->data < p->data)
{ // swap the nodes
int save = p->data;
p->data = q->data;
q->data = save;
};
return 0;
}
insertHere insert is very simple, since we have in fact a List data structure and the operations are isolated:
int so_insert(int item, List* list)
{
int result = so_push_back(item, list);
if (result != 0) return result; // could not insert...
if (list->size == 1) return 0; // was the 1st
// at least 2
Node* p = list->tail;
for (size_t i = 0; i < list->size - 1; i += 1)
{
if (p->data >= p->prev->data)
{
p = p->prev;
continue;
};
// swap the nodes
int save = p->data;
p->data = p->prev->data;
p->prev->data = save;
p = p->prev;
}
return 0;
}
The new node is just appended at the end and then goes down to their position in a single loop.
sortAn insertion at head or tail will destroy the ordering, so a sort function is needed. Here is a simple one:
int so_sort(List* list)
{
if (list == NULL) return -1;
if (list->size < 2) return -2;
Node* p = list->tail;
for (Node* q = list->tail; q != list->head; q = q->prev)
for (Node* p = q->prev; p != NULL; p = p->prev)
if (q->data < p->data)
{ // swap the nodes
int save = p->data;
p->data = q->data;
q->data = save;
};
return 0;
}
It is a simple implementation of insertion sort.