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
No comments:
Post a Comment