doubly_linked_list.c File Reference

Implementation of Doubly linked list More...

#include <stdio.h>
#include <stdlib.h>

Include dependency graph for doubly_linked_list.c:

Data Structures
struct	list
	Doubly linked list struct. More...

Typedefs
typedef struct list	List
	Doubly linked list struct.

Functions
List *	create (double value)
	Create list function, a new list containing one node will be created. More...
List *	insert (List *list, double value, int pos)
	Insertion by position into the list function. More...
List *	delete (List *list, int pos)
	Deletion by position into the list function. More...
int	search (List *list, double value)
	Search value into the list function. More...
void	print (List *list)
	Print list function. More...
void	example ()
	Example function. More...
int	main ()
	Main function. More...

Detailed Description

Implementation of Doubly linked list

A doubly linked list is a data structure with a sequence of components called nodes. Within that nodes there are three elements: a value recorded, a pointer to the next node, and a pointer to the previous node.

In this implementation, the functions of creating the list, inserting by position, deleting by position, searching for value, printing the list, and an example of how the list works were coded.

Author

Gabriel Mota Bromonschenkel Lima

Function Documentation

create()

List * create

(

double

value

)

Create list function, a new list containing one node will be created.

Parameters

value

a value to be saved into the first list node

Returns

new_list the list created

{
    List *new_list = (List *)malloc(sizeof(List));
    new_list->value = value;
    new_list->next = NULL;
    new_list->prev = NULL;
    return new_list;
}

delete()

List * delete	(	List *	list,
		int	pos
	)

Deletion by position into the list function.

Parameters

list	a doubly linked List
pos	a position into the list for value Deletion

Returns

list the input list with deleted values or the same list

{
    // list NULL case
    if (list == NULL)
        return list;
 
    // position existing case
    if (pos > 0)
    {
        List *cpy = list, *tmp = cpy;
        int flag = 1, index = 1, size = 0;
 
        while (tmp != NULL)
        {
            size++;
            tmp = tmp->next;
        }
 
        // first position case
        if (pos == 1)
        {
            if (size == 1)
                return NULL;
            cpy = cpy->next;
            cpy->prev = NULL;
            return cpy;
        }
 
        // position existing in list range case
        if (size + 2 > pos)
        {
            while (cpy->next != NULL && index < pos)
            {
                flag++;
                index++;
                cpy = cpy->next;
            }
 
            if (flag == pos)
            {
                // position into list with no poiting for NULL
                if (cpy->next != NULL)
                {
                    cpy->prev->next = cpy->next;
                    cpy->next->prev = cpy->prev;
                }
 
                // last position case
                else
                    cpy->prev->next = NULL;
            }
        }
        return list;
    }
}

example()

void example

(

)

Example function.

Returns

void

{
    List *my_list = NULL;
    double node_value = 0;
    int searching;
 
    my_list = create(node_value);
    my_list = insert(my_list, 3, 1);
    my_list = insert(my_list, 5, 3);
    my_list = insert(my_list, 10, 3);
    my_list = insert(my_list, 20, 3);
 
    print(my_list);
    searching = search(my_list, 20);
    printf("\n%d\n", searching);
 
    my_list = delete (my_list, 1);
    my_list = delete (my_list, 1);
    my_list = delete (my_list, 1);
    my_list = delete (my_list, 1);
 
    print(my_list);
    searching = search(my_list, 20);
    printf("\n%d\n", searching);
}

Here is the call graph for this function:

insert()

List * insert	(	List *	list,
		double	value,
		int	pos
	)

Insertion by position into the list function.

Parameters

list	a doubly linked List
value	a value to be inserted into the list
pos	a position into the list for value insertion

Returns

list the input list with a node more or the same list

{
    // list NULL case
    if (list == NULL)
    {
        list = create(value);
        return list;
    }
 
    // position existing case
    if (pos > 0)
    {
        List *cpy = list, *tmp = cpy;
        int flag = 1, index = 1, size = 0;
 
        while (tmp != NULL)
        {
            size++;
            tmp = tmp->next;
        }
 
        // first position case
        if (pos == 1)
        {
            List *new_node = create(value);
            new_node->next = cpy;
            cpy->prev = new_node;
            list = new_node;
            return list;
        }
 
        // position existing in list range case
        if (size + 2 > pos)
        {
            while (cpy->next != NULL && index < pos)
            {
                flag++;
                index++;
                cpy = cpy->next;
            }
 
            List *new_node = (List *)malloc(sizeof(List));
            new_node->value = value;
 
            // position into list with no poiting for NULL
            if (flag == pos)
            {
                cpy->prev->next = new_node;
                new_node->next = cpy;
                new_node->prev = cpy->prev;
                cpy->prev = new_node;
            }
 
            // last position case
            if (flag < pos)
            {
                new_node->next = cpy->next;
                new_node->prev = cpy;
                cpy->next = new_node;
            }
        }
        return list;
    }
}

Here is the call graph for this function:

main()

int main

(

void

)

Main function.

Returns

0 on exit

{
    // examples for better understanding
    example();
    // code here
    return 0;
}

Here is the call graph for this function:

print()

void print

(

List *

list

)

Print list function.

Parameters

list	a doubly linked List

Returns

void

{
    if (list != NULL)
    {
        printf("%f\t", list->value);
        print(list->next);
    }
}

search()

int search	(	List *	list,
		double	value
	)

Search value into the list function.

Parameters

list	a doubly linked list
value	a value to be looked for into the list

Returns

1 if the looked up value exists

0 if the looked up value doesn't exist

{
    if (list == NULL)
        return 0;
    if (list->value == value)
        return 1;
    search(list->next, value);
}