Double linked list implementation

Double linked list implementation

/*
    Double linked list general implementation :: with header node
*/

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

enum BOOL {FALSE, TRUE};
typedef int BOOL; // the more obvious choice would be char, but int is more
                  // time efficient as it uses a basic memory unit optimal for the
                  // particular processor design, by default

struct NODE_d;
typedef struct NODE_d Node_d;
typedef Node_d* PtrNode_d;
typedef PtrNode_d List_d;
typedef PtrNode_d Position_d;
typedef int DataType; // this is a default data type

struct NODE_d{ // single link list node
    DataType data;
    PtrNode_d next;
    PtrNode_d previous;
};
///{ ....................................................................
// function list
    PtrNode_d NewList_d();
    Position_d NewNode_d();
    void Delete_d(PtrNode_d node);
    Position_d PrePos_d(List_d L, Position_d pos);
    void DeleteNode_d(List_d L, Position_d pos);
    void DeleteList_d(List_d L);

// standard operations*******************************
    BOOL IsLast_d(List_d L, Position_d pos);
    BOOL IsFirst_d(List_d L, Position_d pos);
    BOOL IsEmpty_d(List_d L);
    void Insert_d ( List_d L, DataType data, Position_d pos);
    Position_d FindPrevious_d(List_d L, DataType element);
    void DeleteElement_d(List_d L, DataType data);
    Position_d Find_d(List_d L, DataType element);
    Position_d FindEnd_d(List_d L);
    Position_d moveForward_d(Position_d pos);
    DataType returnElement_d(Position_d pos);
//*****************************************************
    void DisplayElement_d(DataType element);
    void Display_d (List_d L);
    void DisplayReverse_d(List_d L);


///}...............................................

// vital ones>>>>>>>>>>>>>>>>>>>>>>>>>
PtrNode_d NewList_d() // returns the List's header
{
    PtrNode_d tempNode =  malloc(sizeof(Node_d));
    tempNode->next = NULL;
    tempNode->previous = NULL;
    return tempNode;
}
Position_d NewNode_d()
{
    // to do: add code to create the other parts of
    // the memory to be allocated.
    return malloc(sizeof(Node_d)); // for old compilers,
    // explicit type conversion like (Node) is needed to be
    //used.
}

void Delete_d(PtrNode_d node)
{
    // to do: add code to clear the other parts of
    // the dynamically allocated memory
    free(node);
}
//***************************************************
/*
* Basic single link list operations :: pointer implementation
*/
Position_d PrePos_d(List_d L, Position_d pos) /// finds previous position
{
    return pos->previous;
}

void DeleteNode_d(List_d L, Position_d pos)
{
    Position_d tempPos = PrePos_d(L, pos);
    if(pos == NULL)
    {
        fprintf(stderr, "error: in function DeleteNode, value of pos is NULL");
        return;
    }
    tempPos->next = pos->next;
    if(!IsLast_d(L, pos))
        pos->next->previous = tempPos;
    Delete_d(pos);
}

void DeleteList_d(List_d L)
{
    PtrNode_d tempNode = L->next, tempNode2;
    while (tempNode != NULL)
    {
        tempNode2 = tempNode->next;
        Delete_d(tempNode);
        tempNode = tempNode2;
    }
    L->next = NULL;
}


// standard operations*******************************
BOOL IsLast_d(List_d L, Position_d pos)
{
    return (pos->next == NULL);
}
BOOL IsFirst_d(List_d L, Position_d pos)
{
    return (pos->previous == L);
}
BOOL IsEmpty_d(List_d L)
{
    return (L->next == NULL);
}

void Insert_d ( List_d L, DataType data, Position_d pos)
{
    Position_d tempPos;
    tempPos = NewNode_d(); // creates and allocates memory space
    if(tempPos == NULL)
    {
        fprintf(stderr, "error: request for allocation of memory using function \"malloc\" rejected");
        return;
    }
    tempPos->data = data;
    tempPos->next = pos->next;
    tempPos->previous = pos;
    pos->next = tempPos;
    if(!IsLast_d(L, tempPos))
        tempPos->next->previous = tempPos;
}

Position_d FindPrevious_d(List_d L, DataType element) // by default, this function does not check for the
{                                   // header node which never gets initialised

    Position_d tempPos = L;
    while(tempPos->next != NULL && tempPos->next->data != element) /// searches for the first occurrence of value 'element'
        tempPos = tempPos->next;
    return tempPos; // returns the node preceding the node containing the value 'element'
}

void DeleteElement_d(List_d L, DataType data)
{
    Position_d tempPos = FindPrevious_d(L, data); // by all chances, this cannot delete the list
    PtrNode_d tempNode;
    if(IsLast_d(L, tempPos)) // element not found
            return;

    tempNode = tempPos->next;// without this step, the algorithm looses the data field
    // to be deleted
    tempPos->next = tempNode->next;
    if(!IsLast_d(L, tempNode))
        tempNode->next->previous = tempPos;
    Delete_d(tempNode);

}

Position_d Find_d(List_d L, DataType element)
{
    Position_d tempPos = L->next;
    while(tempPos!=NULL && tempPos->data!=element)
        tempPos = tempPos->next;
    return tempPos; // this return NULL by default when it fails to find the
                    // element
}
Position_d FindEnd_d(List_d L)
{

    Position_d tempPos=L;
    while(!IsLast_d(L, tempPos))
        tempPos = tempPos->next;
    return tempPos;
}
Position_d moveForward_d(Position_d pos)
{
    return pos->next;
}
DataType returnElement_d(Position_d pos)
{
    return pos->data;
}
//*****************************************************
void DisplayElement_d(DataType element)
{

    // to do: add display code here
    printf("%d\n", element);
}
void Display_d (List_d L)
{

    Position_d pos = L->next;
    if(IsEmpty_d(L))
        return;
    while (pos != NULL)
        {
            DisplayElement_d(pos->data);
            pos = pos->next;
        }
}
void DisplayReverse_d(List_d L)
{
    Position_d pos = FindEnd_d(L);
    if(IsEmpty_d(L))
        return; // return if the list is empty
    while (!IsFirst_d(L, pos)) // does not display the first record
    {
        DisplayElement_d(pos->data);
        pos = pos->previous;
    }
    DisplayElement_d(pos->data);
}


copyright (c) 2015 K Sreram.
About my blog