List - newell-romario/DSA GitHub Wiki

A double linked list is a linear data structure where the node contains a previous and next pointer. The previous pointer as its name implies points to the previous node in the list and the next pointer points to the next node in the list. This setup is advantageous because it allows us to traverse the list in any direction (forward/reverse) and remove a node at any position in the list i.e. we’re no longer restricted to insertion and deletion only at the front/rear of the list. A double linked list offers more functions than the single linked list. In a double linked list we’re able to insert at front, insert at back, remove at back, remove at front, insert after position p, insert before position p, remove node at position p and get node at position p.

Our double linked list implementation can be accessed by including the header file r2_list.h.

Representation

We represent the double linked list using the structure:

struct r2_list{
        struct r2_listnode *front;/*first node in list*/
        struct r2_listnode *rear;/*last node in list*/
        r2_int64 lsize;/*number of elements in list*/
        r2_cmp cmp;/*A comparison callback function*/
        r2_cpy cpy;/*A callback function to copy values*/
        r2_fd  fd;/*A callback function that release memory*/
}; 

The fields front, rear and lsize should not be accessed or modified.

Creation

struct r2_list *list = r2_create_list(cmp, cpy, fd); 

Destruction

r2_destroy_list(list);

Insertion

/*Inserting at the front of the list*/
r2_list_insert_at_front(list, data);

/*Inserting at the end of the list*/
r2_list_insert_at_back(list, data); 

/*Get the 5th node in the list*/
struct r2_listnode *pos= r2_listnode_at(list, 5);

/*Inserting a new node after the 5th position*/
r2_list_insert_after(list, pos, data);

/*Inserting a new node before the 5th position*/
r2_list_insert_before(list, pos, data);

A successful insertion operation returns TRUE.

Deletion

/*Deleting the first element in the list*/
r2_list_delete_at_front(list);

/*Deleting the last element in the list*/
r2_list_delete_at_back(list);

/*Get the 5th node in the list*/
struct r2_listnode *pos= r2_listnode_at(list, 5); 

/*Removes this node from the list*/
r2_list_delete(list, pos);

A successful deletion operations returns TRUE.

Position

/*Get the first node in the list*/
struct r2_listnode *pos = r2_listnode_first(list);

/*Getting the last node*/
struct r2_listnode *pos =  r2_listnode_last(list);

/*Getting the first node using at*/
struct r2_listnode *pos = r2_listnode_at(list, 1); 

/*Get the 5th node in the list*/
struct r2_listnode *pos = r2_listnode_at(list, 5);