Created: 2023-09-11 13:53
Status: #concept
Subject: Programming
Tags: Data Structure Linked List C C Array struct

Cursor Implementation

They are typically used when the Programming Language doesn't support Pointers like BASIC and Fortran.

the list is a C Array of structs which contain the data and the link.
instead of link holding Memory Addresses, it will hold the array index to the next node.

Implementation

-1 denotes the last element which is equivalent to NULL in a Linked List.
typedef int List is the type of the list pointer which holds the index to the first element of the cursor list.
we manage a VirtualHeap which has the NodeType Nodes and the List Avail.

#define MAX 10

typedef int List;

typedef struct {
  char data; // the data held by the node
  int link;  // the next index of the list or -1
} NodeType;

typedef struct {
  NodeType Nodes[MAX]; // the memory of the virtual heap
  List Avail;          // points to the next available node to malloc
} VirtualHeap;

Initialization

void initVirtualHeap(VirtualHeap *VH) {
  int x;
  for (x = MAX - 1; x >= 0; x--) {
    VH->Nodes[x].link = x - 1; // set each link to CURRENT_INDEX - 1
  }
  // Nodes[0].link becomes -1, so the Avail can now point to the last Node
  VH->Avail = MAX - 1;
}

Assuming MAX == 4, this is the VirtualHeap VH:

Index	Element	Next
0	?	-1
1	?	0
2	?	1
3	?	2

with a VH->Avail = 3, which is MAX - 1.

Node Allocation `malloc()`

int allocSpace(VirtualHeap *VH) {
  int toReturn = -1;
  
  if (VH->Avail != -1) {
    toReturn = VH->Avail;
    // point to the next available link
    VH->Avail = VH->Nodes[Avail].link;
  }

  // the addres of the next available node is returned
  // otherwise, -1
  return toReturn;
}

Node Deallocation `free()`

void deallocSpace(VirtualHeap *VH, int indexToFree) {
  // link the freed node to the previous available
  VH->Nodes[indexToFree].link = VH->Avail; 
  // freed node becomes the next available node for allocation
  VH->Avail = indexToFree;
}

Display

void displayCursorList(VirtualHeap VH, List L) {
  List trav;
  for (trav = L; trav != -1; trav = VH.Nodes[trav].link) {
    printf("%c", VH.Nodes[trav].data);
  }
}

Insertion

void insertFirst(VirtualHeap *VH, List *A, char elem) {
  int newNodeIndex = allocSpace(VH); // we use the previously-defined function

  // we check if VH->Avail isn't -1 from allocSpace(VH)
  if (newNodeIndex != -1) {
    VH->Nodes[newNodeIndex].data = elem;
    VH->Nodes[newNodeIndex].link = *A;
    *C = newNodeIndex; // the list now points to the newNodeIndex
  }
}

Can we use Pointer-to-Pointer Node (PPN) functions on Cursor Lists?

Yes, here is the equivalent of insertFirst:

void insertFirst(List *A, char elem) {
  Node *newNode = malloc(sizeof(Node));

  if (newNode != NULL) {
    newNode->data = elem;
    newNode->link = *A;
    *A = newNode;
  }
}

References

Cursor Implementation of Linked Lists from Data Structures and Algorithm Analysis in C++, 2nd ed. by Mark Weiss