Cursor Implementation of LinkedList BSc Diploma Project
Cursor Implementation of LinkedList BSc Diploma Project:
We have seen various types of linked list implementation C Programs like Stack and Linear Queue, Circular Queue.
In this post lets see about C Program for Cursor Implementation of Linked List.
This Cursor Implementation of LinkedList : BSc Diploma Project can be improved somehow to be done as mini project by B.E (B.Tech) students.
When will the cursor Implementation is used?
The pointers are not supported by some languages like BASIC and FORTRAN.
But those languages also have to use linked lists. In such cases we use a new method called cursor implementation of linked list.
What is the cursor implementation ?
- It is a new method to make use of linked list in the situations which don’t support pointers.
- Already, we know that there are two important features of pointers of linked list which enable them to be implemented in linked list. They are:
1. Each cell of a linked list contains a pointer that refers the address of the next cell of the list.
2. A cell of the linked list can be included into the list by calling malloc() and a cell can be released by calling free().
- Using cursor implementation, we can perform above said two features of pointers.
- The first feature :
Storing address of next cell, can be performed using global array of structure called Cursor Space Array.
For any cell of the array, its address is hold by the array index.
- The second feature:
Using malloc() and free() cells in the cursor space array can be performed using a list, freelist.
- Freelist: Freelist is a list of cells. The list has the first cell, 0 as a header.
Program for Cursor Implementation of linked List :Algorithm:
- The Cursor Implementation of Linked List is straightforward.
- It consists of a freelist with a header node.
- To perform malloc() operation, the first element after the header is removed from the freelist.
- To perform free() operation, a cell is added at the front of the freelist.
Declaration for cursor implementation of linked list:
#ifndef _Cursor _H
typedef int PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;
List MakeEmpty (List L);
int IsEmpty(const List L);
int IsLast (const Position P, const List L);
Position Find (ElementType X, const List L);
void delete (ElementType X, List L);
Position FindPrevious (ElementType X, List L);
void Insert(ElementType X, List L, Position P);
void DeleteList (List L);
Position Header (List L);
Position First(List L);
Position successor(Position P);
ElementType Retrive (Position P);
- Here the structure of list L is Node with element and position Next contains address.
- Here we declare operations insert, delete, find previous, find position, CursorAlloc and CursorFree.
- Before seeing operations of Cursor Implementation, lets see the structure cursor space.
Slot Element Next
0 – 2
1 b 3
2 header 4
3 – 0
4 a 1
- The above shown is a sample cursor space having index as Slot, element as Element and address of the next element as Next.
void Insert(ElementType X, List L, Position P)
CursorSpace [Temp].Element = X;
CursorSpace [Temp.Next] = CursorSpace [P] . Next;
CursorSpace [P].Next = Temp;
- To insert a cell, first create a temporary cell using cursoralloc().
- Then insert the element X in that cell.
- The next field having address of next cell.
void Delete(ElementType X, List L)
Temp = CursorSpace[P].Next;
CursorSpace[P].Next = CursorSpace [Temp] .Next;
- Find the previous of position to be deleted.
- If so, then create a position temp, that is to be deleted.
- Point the next of previous to the next of next of temp.
- Free the temp using CursorFree().
- Here we are using FindPrevious and is Last() functions.
C Program for Cursor Implementation of LinkedList BSc Diploma Project:
- Lets create curslist.h header file at first.
- It creates a structure node which create the functions as follows
- Initialize cursor,
- CursorAlloc() ,
- CursorFree(POSITION P),
- Insert(int X,POSITION P),
- IsLast(POSITION P),
- POSITION Find(int X,LIST L),
- POSITION FindPrevious(int X,LIST L),
- void Delete(int X,LIST L),void MakeEmpty(LIST L).
- Then include this header file into the main function of the program curlist.c.
You can find the entire coding in my next post.
Thanks for reading… please leave your comment below…