I come from a C++ background, and I recently got into C, and one of the first things I made was a double linked list since I though it would be good practice for me with pointers and memory allocation. It isn't too complex though, it's just with some basic functions.
Here's the overview of my list:
#include <stdlib.h>
#include <stdio.h>
typedef struct Node
{
int val;
struct Node* prev;
struct Node* next;
} Node;
typedef struct
{
int length;
Node* head;
Node* tail;
} double_list;
double_list* create_list(); // constructor
void destroy_list(double_list* const list); // destructor
void insert_pos(double_list* const list, int index, int val);
void insert_front(double_list* const list, int val);
void insert_back(double_list* const list, int val);
void remove_pos(double_list* const list, int index);
void remove_front(double_list* const list);
void remove_back(double_list* const list);
void sort_list(double_list* const list); // selection sort
void reverse_list(double_list* const list);
It just has basic insertion and removal, as well as a constructor, destructor, sort, and reverse functions.
Here's the actual definition for the functions:
#include <stdlib.h>
#include <stdio.h>
typedef struct Node
{
int val;
struct Node* prev;
struct Node* next;
} Node;
typedef struct
{
int length;
Node* head;
Node* tail;
} double_list;
double_list* create_list()
{
double_list* list = malloc(sizeof(*list));
list->length = 0;
list->head = NULL;
list->tail = NULL;
return list;
}
void destroy_list(double_list* const list)
{
list->length = 0;
Node* node_ptr = list->head;
while (node_ptr != NULL)
{
node_ptr = node_ptr->next;
free(list->head);
list->head = node_ptr;
}
}
void insert_pos(double_list* const list, int index, int val)
{
if (index < 0 || index > list->length)
return;
list->length += 1;
if (list->head == NULL)
{
list->head = malloc(sizeof(*(list->head)));
list->head->val = val;
list->head->prev = NULL;
list->head->next = NULL;
list->tail = list->head;
return;
}
if (index == 0)
{
Node* new_node = malloc(sizeof(*new_node));
new_node->val = val;
new_node->prev = NULL;
new_node->next = list->head;
list->head->prev = new_node;
list->head = new_node;
return;
}
if (index == list->length - 1)
{
Node* new_node = malloc(sizeof(*new_node));
new_node->val = val;
new_node->prev = list->tail;
new_node->next = NULL;
list->tail->next = new_node;
list->tail = new_node;
return;
}
Node* node_ptr = list->head;
for (int a = 0; a < index; ++a)
node_ptr = node_ptr->next;
Node* new_node = malloc(sizeof(*new_node));
new_node->val = val;
new_node->next = node_ptr;
new_node->prev = node_ptr->prev;
node_ptr->prev->next = new_node;
node_ptr->prev = new_node;
}
void insert_front(double_list* const list, int val)
{
insert_pos(list, 0, val);
}
void insert_back(double_list* const list, int val)
{
insert_pos(list, list->length, val);
}
void remove_pos(double_list* const list, int index)
{
if (index < 0 || index >= list->length)
return;
list->length -= 1;
if (index == 0)
{
Node* node_ptr = list->head;
list->head = list->head->next;
list->head->prev = NULL;
free(node_ptr);
return;
}
if (index == list->length)
{
Node* node_ptr = list->tail;
list->tail = list->tail->prev;
list->tail->next = NULL;
free(node_ptr);
return;
}
Node* node_ptr = list->head;
for (int a = 0; a < index; ++a)
node_ptr = node_ptr->next;
node_ptr->prev->next = node_ptr->next;
node_ptr->next->prev = node_ptr->prev;
free(node_ptr);
}
void remove_front(double_list* const list)
{
remove_pos(list, 0);
}
void remove_back(double_list* const list)
{
remove_pos(list, list->length - 1);
}
void sort_list(double_list* const list)
{
Node* index_ptr = list->head;
Node* small_ptr = list->head;
Node* node_ptr = list->head;
while (index_ptr->next != NULL)
{
while (node_ptr != NULL)
{
if (node_ptr->val < small_ptr->val)
small_ptr = node_ptr;
node_ptr = node_ptr->next;
}
int hold = index_ptr->val;
index_ptr->val = small_ptr->val;
small_ptr->val = hold;
index_ptr = index_ptr->next;
node_ptr = index_ptr;
small_ptr = index_ptr;
}
}
void reverse_list(double_list* const list)
{
Node* node_ptr = list->head;
list->head = list->tail;
list->tail = node_ptr;
while (node_ptr != NULL)
{
Node* temp = node_ptr->prev;
node_ptr->prev = node_ptr->next;
node_ptr->next = temp;
node_ptr = node_ptr->prev;
}
}
And here's a small sample of how my list would be used:
double_list* list = create_list();
insert_back(list, 1);
insert_back(list, 2);
insert_back(list, 3);
sort_list(list);
destroy_list(list);
My main area's of concern are:
Are the constructor and destructor doing their job properly? Is the destructor leaking memory, and is there a better way to do the constructor?
Are the
remove()
andinsert()
functions efficient? Is there a better way to do that, like making a more genericremove()
function so I don't have to have special test cases for index of 0 and stuff like that?Are the
sort()
andreverse()
functions okay at least? I know selection sort isn't the best algorithm to use. And is thereverse()
function implemented correctly? Is there a better way to reverse the list?
Sorry I'm being a little too broad with my question. I can edit it to focus on a more specific question if needed.
Thanks
insert_pos
[anddelete_pos
] at the point where you actually traverse the list using thenext
pointer ... Since your list has alength
, you could check forindex > (list->length / 2)
and if that's true, traverse [backwards] fromlist->tail
using theprev
link \$\endgroup\$