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