Well, I'm a complete newbie to linked lists but just yesterday I wrote something like this. I needed a linked list where I can remove any element at any time without breaking the chain. I didn't find any example for this so I wrote it myself. It works but if somebody finds an error (something that could be done more efficient or something like that), please tell me. Here it is:
Code:
/* This is the structure (replace "user" with "node" or whatever you want) */
typedef struct _user {
int some_data;
struct _user *next, *prev;
} user;
/* Global pointers to point to first and last element */
user *first_user = NULL, *last_user = NULL;
/* The function to add a new user and return a pointer to this user */
user *add_user()
{
user *new_user;
if (last_user != NULL) {
last_user->next = (user*) malloc (sizeof (user));
new_user = last_user->next;
new_user->next = NULL;
new_user->prev = last_user;
last_user = new_user;
} else {
new_user = (user *) malloc (sizeof (user));
first_user = new_user; last_user = new_user;
new_user->next = NULL; new_user->prev = NULL;
}
return new_user;
}
/* The function to delete a node and fix the chain (just use with remove_user(pointer_to_node); */
void remove_user(user *current_user)
{
user *prev_user, *next_user;
prev_user = current_user->prev;
next_user = current_user->next;
if (current_user == first_user) {
/* first in line so make next one the first in line if exists */
if (next_user != NULL) {
first_user = next_user;
next_user->prev = NULL;
} else {
first_user = NULL;
last_user = NULL;
}
} else {
/* not first in line so connect prev to next */
if (next_user != NULL) {
prev_user->next = next_user;
next_user->prev = prev_user;
} else {
prev_user->next = NULL;
last_user = prev_user;
}
}
free (current_user);
}
What this allows you is to add a new node at any time to the end of the list with add_user() and remove it later with remove_user().
I use this in threads to create a node for this thread and return a pointer in myuser and later delete this node when the thread exits, like this:
Code:
user *myuser;
myuser = add_user();
/* do some stuff with myuser until finished */
remove_user(myuser);
If you would want to get and/or delete the second node in line, you could do it like this:
Code:
int i = 0;
user *current_user;
user *second_user;
current_user = first_user;
while (current_user != NULL) {
i++;
if (i == 2) {
second_user = current_user;
break;
}
current_user = current_user->next;
}
if (second_user != NULL)
remove_user(second_user);
Hope this helps.
