Singly linked list implementation

Singly linked list implementation

The following is just the set of modules that constitute the basic data structure and its operations. This data structure is used to store and process information that frequently get modified and especially if the total memory requirement for the storage is completely unpredictable. The following example has a set of modules defined for singly linked list manipulation. Let me tell one common application of using a singly linked list: you may use it in huge servers where the number of application forms for a particular event that's going to be received is completely indeterminable and you would practically be wasting a lot of efficient space trying to over estimate the maximum requirement.         

So to put it simple, you may use linked list when you believe that you cannot determine the actual size of memory you would require to store something. The following shows a basic C implementation of linearly single-headed linked list which we may use to store any data. As default, I had defined "DataType" to be "int". The user may change it to any data type that's needed, but he would have to do slight alterations to functions like "Insert" and "DeleteElement" that requires a equality checking to be done. One method will be to check for the equality of the binary data (If a data structure is used) or to check a specific field's equality. I have examples showing both these implementations in the subsequent programs in this blog. Whenever we talk about ADT's we must note that there is no universally standard way to implement; the author of the program or the design has utmost freedom in creating his modules.

In this program, I had extensively used "typedef" to duplicate data-types to increase the readability of the source. I am more used to programming in C++ so, I would prefer a "BOOL" type to be defined. Hence I defined the 'BOOL' data type. As I had said in the comment, the more obvious choice would have been 'char' but 'int' usually takes its size based on the processor's architecture (i.e., it would take the size 64bit in a 64bit processor architecture and 32bit in a 32 bit processor architecture). This would prevent the extra conversion of  'char' or any other involved data-type to 'int' while processing the data (the processor first converts the size of the data to its "handy size" before applying the operations).

You might note that there are two functions for delete operation with one implementing position-vice delete and the other implementing element-vice delete; and you may find that both these operations run at O(N) which is considered to be really costly if N is unimaginable large (this kind of scenario more commonly arise in AI algorithms rather than in "record storage" algorithms, that store user data in servers; if the user data is bound to be accessed frequently, tree algorithm is used). If the delete operation that deletes the node by address is slightly modified to get the "previous node" as its input rather than the node to delete, then the deletion becomes O(1). I have written a position-vice insertion function (which runs at O(1) ) but I haven't written an element-vice insertion (which runs at O(N)) function which might be useful in many situations.

    
/*
    Single 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;
typedef struct NODE Node;
typedef Node* PtrNode;
typedef PtrNode List;
typedef PtrNode Position;
typedef int DataType; // this is a default data type

struct NODE{ // single link list node
    DataType data;
    PtrNode next;
};

PtrNode NewList() // returns the List's header
{
    PtrNode tempNode =  malloc(sizeof(Node));
    tempNode->next = NULL;
    return tempNode;
}
Position NewNode()
{
    // to do: add code to create the other parts of
    // the memory to be allocated.
    return malloc(sizeof(Node)); // for old compilers,
    // explicit type conversion like (Node) is needed to be
    //used.
}

void Delete(PtrNode 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 PrePos(List L, Position pos) /// finds previous position
{
    Position retPos = L;
    if(pos == retPos)
        return NULL;
    while (retPos->next != NULL)
        {
            if(retPos->next == pos)
                return retPos;
            retPos = retPos->next;
        }
    return NULL;

}

void DeleteNode(List L, Position pos)
{
    if(pos == NULL)
    {
        fprintf(stderr, "error: in function DeleteNode, value of pos is NULL");
        return;
    }
    PrePos(L, pos)->next = pos->next;
    Delete(pos);
}

void DeleteList(List L)
{
    PtrNode tempNode = L->next, tempNode2;
    while (tempNode != NULL)
    {
        tempNode2 = tempNode->next;
        Delete(tempNode);
        tempNode = tempNode2;
    }
    L->next = NULL;
}


// standard operations*******************************
BOOL IsLast(List L, Position pos)
{
    return (pos->next == NULL);
}
BOOL IsEmpty(List L)
{
    return (L->next == NULL);
}

void Insert ( List L, DataType data, Position pos)
{
    Position tempPos;
    tempPos = NewNode(); // 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;
    pos->next = tempPos;
}

Position FindPrevious(List L, DataType element) // by default, this function does not check for the
{                                   // header node which never gets initialised

    Position 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(List L, DataType data)
{
    Position tempPos = FindPrevious(L, data); // by all chances, this cannot delete the list
    PtrNode tempNode;
    if(IsLast(L, tempPos)) // element not found
            return;

    tempNode = tempPos->next;
    tempPos->next = tempNode->next;
    Delete(tempNode);

}

Position Find(List L, DataType element)
{
    Position 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 FindEnd(List L)
{

    Position tempPos=L;
    while(!IsLast(L, tempPos))
        tempPos = tempPos->next;
    return tempPos;
}
Position moveForward(Position pos)
{
    return pos->next;
}
DataType returnElement(Position pos)
{
    return pos->data;
}
//*****************************************************
void DisplayElement(DataType element)
{

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

    Position pos = L->next;
    if(pos == NULL)
        return;
    while (pos != NULL)
        {
            DisplayElement(pos->data);
            pos = pos->next;
        }
}

copyright (c) 2015 K Sreram.
About my blog