Singly Linked List Implementation

-
In this post, you will see the implementation of a singly linked list. It is one of the main data structures in computer programming.

A singly linked list consists of nodes which are bound to each other with their "next" pointers.

A simple node is represented at least 2 fields. A "next" node pointer and a "data" field.
/*
 * node structure.
 */
struct node {
struct node *next;
int data;

};

Some of the basic methods of a linked list and node data structures are implemented below.

Create a Node Method:
/*
 * node_create()
 * Creates a node.
 */
struct node *node_create(int data)
{
    struct node *n = malloc(sizeof(struct node));
    if (!n) {
        printf("Unable to allocate memory for node\n");
        return NULL;
    }

    n->data = data;
    n->next = NULL;

    return n;

}

Free a Node Method:

/*
 * node_free()
 * Frees a node.
 */
void node_free(struct node *n)
{
    if (!n) {
        return;
    }

    free(n);

}

List Length Get Method:

/*
 * list_lenght_get()
 * Gets the length of a list.
 */
int list_lenght_get(struct node *list)
{
    int count = 0;

    while (list) {
        count++;
        list = list->next;
    }
    return count;

}

Add Head Method with Data:

/*
 * list_add_data_head()
 * Adds a node by data to the head of the linked list.
 */
void list_add_data_head(struct node **list, int data)
{
struct node *n = (struct node *)malloc(sizeof(struct node));
if (!n) {
printf("Unable to allocate memory for node\n");
return;
}

n->data = data;
n->next = *list;
*list = n;

}

Add Tail Method with Data:

/*
 * list_add_data_tail()
 * Adds a node by data to the tail of the linked list.
 */
void list_add_data_tail(struct node **list, int data)
{
struct node *nd = (struct node *)malloc(sizeof(struct node));
if (!nd) {
printf("Unable to allocate memory for node\n");
return;
}

nd->data = data;
nd->next = NULL;

if (!(*list)) {
*list = nd;
return;
}

struct node *n = *list;

while(n->next) {
n = n->next;
}

n->next = nd;

}

Add  a Node to Tail Method:

/*
 * list_add_node_tail()
 * Adds an allocated node to a linled list tail.
 */
void list_add_node_tail(struct node **list, struct node *n)
{
    struct node *curr = *list;

    if (!*list) {
        *list = n;
        return;
    }

    while (curr->next) {
        curr = curr->next;
    }

    curr->next = n;

}

Remove Node by Data:

/*
 * list_remove_node_by_data()
 * Remove a node by data from linked list.
 */
void list_remove_node_by_data(struct node **list, int data)
{
/*
* If list is empty, just return.
*/
if (!*list) {
printf("list is empty\n");
return;
}

/*
* curr is our list head.
*/
struct node *curr = *list;
struct node *tmp;

/*
* If there is multiple occurences at the head of the list,
* remove all of them.
* 1->1->1->5->6->null
*/
while (curr && (curr->data == data)) {
tmp = curr;
*list = curr->next;
curr = *list;
free(tmp);
}

/*
* Check the list. Did we remove all the nodes?
*/
if (!*list) {
printf("list is empty. All the occurences removed from the head\n");
return;
}

/*
* There are more nodes in the list. Check them as well.
* If we find more occurence, prev->next will be bound to curr->next.
*/
struct node *prev = curr;
curr = curr->next;

while (curr) {
if (curr->data == data) {
tmp = curr;
prev->next = curr->next;
curr = curr->next;
free(tmp);
continue;
}

prev = curr;
curr = curr->next;
}

}

Reverse List:

/*
 * list_reverse()
 * Reverses a linked list.
 */
void list_reverse(struct node **list)
{
struct node *prev = NULL;
struct node *curr = *list;
struct node *next_node = *list;

/*
* If list is empty, just return.
*/
if (!*list) {
printf("list is empty\n");
return;
}

while (curr) {
next_node = curr->next;
curr->next = prev;
prev = curr;
curr = next_node;
}
*list = prev;

}

Look Up a Data in the List:

/*
 * list_data_look_up()
 * Look ups a node by a data inside the linked list.
 */
bool list_data_look_up(struct node *list, int data)
{
while (list) {
if (list->data == data) {
return true;
}

list = list->next;
}

return false;

}

Print List:

/*
 * list_print()
 * Prints linked list.
 */
void list_print(struct node *list)
{
if (!list) {
printf("list is empty, cannot print\n");
return;
}

struct node *n = list;

while (n) {
printf("%d->", n->data);
n = n->next;
}

printf("NULL\n");


}

 Test Code:

/*
 * Global list object.
 */
struct node *list = NULL;

/*
 * Test Code.
 */
int main(void)
{
printf("Creating link list\n");

list_add_data_head(&list, 1);
list_add_data_head(&list, 1);
list_add_data_tail(&list, 5);
list_add_data_tail(&list, 6);
list_add_data_tail(&list, 1);
list_add_data_tail(&list, 7);
list_add_data_tail(&list, 1);
list_add_data_tail(&list, 12);
list_add_data_tail(&list, 1);

list_print(list);

printf("\nLook up 3 in the list\n");
if (list_data_look_up(list, 3)) {
printf("Yes, list has 3\n");
} else {
printf("No, list does not have 3\n");
}

printf("\nLook up 5 in the list\n");
if (list_data_look_up(list, 5)) {
printf("Yes, list has 5\n");
} else {
printf("No, list does not have 5\n");
}

printf("\nRemove 1s from the list\n");
list_remove_node_by_data(&list, 1);

list_print(list);

printf("\nReverse list\n");
list_reverse(&list);
list_print(list);

return 0;

}

 Test Output:

Creating link list
1->1->5->6->1->7->1->12->1->NULL

Look up 3 in the list
No, list does not have 3

Look up 5 in the list
Yes, list has 5

Remove 1s from the list
5->6->7->12->NULL

Reverse list
12->7->6->5->NULL

 Source Download:

 https://github.com/sezginmurat/list_lib.git

Comments

Post a Comment

Popular posts from this blog

How to Use container_of in Linux Kernel Development

-
In this post, I will explain the usage of linux's container_of macro with a sample code. If you know address of a data structure's field, you can get the address of the instance of that data structure by using the container_of macro. This is the simplest explanation of this macro. Let's say you have a function called with a pointer parameter and you know that the pointer is pointing an address of a data structure field. struct my_object { int a; int b; } obj; function(&obj->b); If you want to access the other field "a" in the function, you need to use container_of macro. Let's see the below sample code and it's output to understand it easily. /* * my_object structure. */ struct my_object { int a; int b; int c; }; /* * container_test() * Test function for usage of container_of macro. * * This function is passed a pointer which points a field of * an allocated my_obj...
Read more

Notification Chains in Linux Kernel

-
Notification chains in Linux kernel is a mechanism for the subsystems being informed by the events generated by the other subsystems. In other words, if you are developing a new driver in Linux and you want to listen some events from other driver and handle these events in your own driver, you need to use the Linux's notification chains mechanism. As an example, if you develop a driver and this driver needs to be informed about the net device events such as net device UP, DOWN events, the driver needs to register itself to the net device notifications with the  register_netdevice_notifier function. Similarly, it unregisters itself with the unregister_netdevice_notifier function. These functions are provided by the net device subsystem. The APIs and the data structures of notification chains are defined in the include/linux/notifier.h and  kernel/notifier.c files under linux source code. In this post, I am going to explain how this notification chains mechanism wo...
Read more

Linux Dynamic Debugging

-
Image
In Linux programming, it is very important to debug your code by adding some debug messages to your code. By using the dynamic debug feature of Linux, you can enable these debug messages per file, per function and even per line.  This post will show you how to do this with a simple kernel loadable module implementation. First, you need compile your kernel with the CONFIG_DYNAMIC_DEBUG option. It is under " Kernel hacking " menu and prompt name is " E nable dynamic printk() support " as you see on the below screenshot. Sample Code: TBD Enable/Disable dynamic debug in the sample code: TBD
Read more