Circularly linked list implementation

Circularly linked list implementation

/*
* circularly linked list
* By K Sreram
*/

/*
Usually, we use the expression (pos->next == NULL) to determine if the node is the last one.
But here, we check if (pos->next == L->next) to check if the position had headed back to the
starting position. There is no NULL link in any of the nodes, but there is a NULL pointer in the
variable L->previous, where a term preceding the header node is undefined.

for delete, if(!IsLast_dc(L, pos))
        pos->next->previous = tempPos; is not needed. pos->next->previous = tempPos; is alone needed
There will be now issue of accessing a NULL pointer
*/
#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_dc;
typedef struct NODE_dc Node_dc;
typedef Node_dc* PtrNode_dc;
typedef PtrNode_dc List_dc;
typedef PtrNode_dc Position_dc;
typedef int DataType; // this is a default data type

struct NODE_dc{ // single link list node
    DataType data;
    PtrNode_dc next;
    PtrNode_dc previous;
};
///{ ....................................................................
// function list
    PtrNode_dc NewList_dc();
    Position_dc NewNode_dc();
    void Delete_dc(PtrNode_dc node);
    Position_dc PrePos_dc(List_dc L, Position_dc pos);
    void DeleteNode_dc(List_dc L, Position_dc pos);
    void DeleteList_dc(List_dc L);

// standard operations*******************************
    BOOL IsLast_dc(List_dc L, Position_dc pos);
    BOOL IsFirst_dc(List_dc L, Position_dc pos);
    BOOL IsEmpty_dc(List_dc L);
    void Insert_dc ( List_dc L, DataType data, Position_dc pos);
    Position_dc FindPrevious_dc(List_dc L, DataType element);
    void DeleteElement_dc(List_dc L, DataType data);
    Position_dc Find_dc(List_dc L, DataType element);
    Position_dc FindEnd_dc(List_dc L);
    Position_dc moveForward_dc(Position_dc pos);
    DataType returnElement_dc(Position_dc pos);
//*****************************************************
    void DisplayElement_dc(DataType element);
    void Display_dc (List_dc L);
    void DisplayReverse_dc(List_dc L);


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

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

void Delete_dc(PtrNode_dc 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_dc PrePos_dc(List_dc L, Position_dc pos) /// finds previous position
{
    return pos->previous;
}

void DeleteNode_dc(List_dc L, Position_dc pos)
{
    if(pos == NULL)
    {
        fprintf(stderr, "error: in function DeleteNode, value of pos is NULL");
        return;
    }
    if(pos->next == pos) //i.e., previous position is equal to itself. this shows that there is only one node in the list
        {
            Delete_dc(L->next);
            L->next = NULL;
            return;
        }
    if(L->next == pos)
        L->next = pos->next;
    pos->previous->next = pos->next;
    pos->next->previous = pos->previous;
    Delete_dc(pos);
}

void DeleteList_dc(List_dc L)
{
    PtrNode_dc tempNode = L->next, tempNode2;
    L->next->previous->next = NULL;// converts a circular list to a linear list
    while (tempNode != NULL)
    {
        tempNode2 = tempNode->next;
        Delete_dc(tempNode);
        tempNode = tempNode2;
    }
    L->next = NULL;
}


// standard operations*******************************
BOOL IsLast_dc(List_dc L, Position_dc pos)
{
    return (pos->next == L->next); // circular list links back to the first node and not the header
}
BOOL IsFirst_dc(List_dc L, Position_dc pos)
{
    return (pos->previous == L->next->previous); //L->next->previous likes the node preceding the node in the start position
}
BOOL IsEmpty_dc(List_dc L)
{
    return (L->next == NULL); // holds good even here
}

void Insert_dc ( List_dc L, DataType data, Position_dc pos)
{
    Position_dc tempPos;
    tempPos = NewNode_dc(); // creates and allocates memory space
    if(tempPos == NULL)
    {
        fprintf(stderr, "error: request for allocation of memory using function \"malloc\" rejected");
        return;
    }

    tempPos->data = data;
    if(IsEmpty_dc(L))// a special case is required when the list is empty
    {
        L->next = tempPos;
        tempPos->previous = tempPos->next = tempPos; // the node does not connects back to the header
        return;
    }
    tempPos->next = pos->next;
    tempPos->previous = pos->next->previous; ///NOTE: I had done a mistake here while I was programming
                                             /// pos->next->previous is not the same as pos->next if pos is L!!!
                                             /// so be careful; you may use pos = L like pos->next->previous
                                             /// this implementation does not have a link back to the header.
                                             /// Even by accident if we pass on the parameter L for pos,
                                             /// the operation pos->next->previous screens it out. After applying this
                                             /// operation, if pos was the header node it gets eliminated. If it was an
                                             /// ordinary node, there is no difference.
    pos->next = pos->next->previous->next = tempPos;//pos->next belongs to the header node, whereas, pos->next->previous->next
                    // belongs to the preceding node. So both the variables should be assigned the address of tempPos
    tempPos->next->previous = tempPos;
}

Position_dc FindPrevious_dc(List_dc L, DataType element) // by default, this function does not check for the
{              // header node which never gets initialised
    Position_dc pos = Find_dc(L, element);
    if(pos == NULL)
        return NULL;
    else
        return pos->previous;
}

void DeleteElement_dc(List_dc L, DataType data)
{
    Position_dc pos = Find_dc(L, data);
    if(pos == NULL) return;
    if(pos->next == pos)
        {
            Delete_dc(L->next);
            L->next = NULL;
            return;
        }
    if(L->next == pos)
        L->next = pos->next;
    pos->previous->next = pos->next;
    pos->next->previous = pos->previous;
    Delete_dc(pos);

}

Position_dc Find_dc(List_dc L, DataType element) // same as FindPrevious, but this returns the node containing the value itself
{
    Position_dc tempPos = L->next;
    while( L->next->previous != tempPos)
    {
        if(tempPos->data == element)
            return tempPos;
        tempPos = tempPos->next;
    }
    if(tempPos->data == element)
        return tempPos;
    return NULL;
}
Position_dc FindEnd_dc(List_dc L)
{
   return L->next->previous;
}
Position_dc moveForward_dc(Position_dc pos)
{
    return pos->next;
}
DataType returnElement_dc(Position_dc pos)
{
    return pos->data;
}
//*****************************************************
void DisplayElement_dc(DataType element)
{

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

    Position_dc pos = L;
    if(IsEmpty_dc(L))
        return;
    do{
            pos = pos->next;
            DisplayElement_dc(pos->data);
        }while (!IsLast_dc(L, pos));
}
void DisplayReverse_dc(List_dc L)
{
    Position_dc pos = FindEnd_dc(L);
    if(IsEmpty_dc(L))
        return; // return if the list is empty
    do
    {
        DisplayElement_dc(pos->data);
        pos = pos->previous;
    }while (!IsFirst_dc(L, pos));
    DisplayElement_dc(pos->data);
}



copyright (c) 2015 K Sreram.
About my blog