Skip to main content

Static vs dynamic list; getnode and freenode

Short answer

Static list has fixed size in contiguous memory with shifting on insert/delete; dynamic list grows at run time using pointers. For a static linked list, getnode() removes the first node from the free list headed by avail and returns it, while freenode(p) puts node p back at the front of the free list; both take O(1).

Differentiate between a static and dynamic list structure and write an algorithm for getnode() and freenode() of static list structure.

Static vs dynamic list

Static list (array)Dynamic list (linked)
Fixed size at compile timeSize changes at run time
Elements in contiguous memoryNodes anywhere, joined by pointers
Insert/delete requires shifting: O(n)Pointers changed: O(1)
Fast random accessSequential access
Memory may be wastedExtra memory for pointers

getnode() and freenode() of a static list structure

A static list can still be linked: a fixed array of nodes node[MAXNODES] each with info and next (an array index, −1 meaning null). Unused nodes are kept in a free list headed by avail. getnode removes a node from the free list; freenode returns it.

Initialization
   for i = 0 to MAXNODES - 2:  node[i].next = i + 1
   node[MAXNODES - 1].next = -1
   avail = 0

getnode()
1. if avail == -1:  print "Overflow: no free node"; exit
2. p = avail                    /* take first free node */
3. avail = node[avail].next     /* free list now starts at the next node */
4. return p

freenode(p)
1. node[p].next = avail         /* put p in front of the free list */
2. avail = p

#define MAXNODES 100
struct nodetype { int info; int next; } node[MAXNODES];
int avail;

int getnode(void) {
    int p;
    if (avail == -1) { printf("Overflow\n"); exit(1); }
    p = avail;
    avail = node[avail].next;
    return p;
}
void freenode(int p) { node[p].next = avail; avail = p; }

Both take O(1) time and play the role of malloc and free for the array-based list.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 3 questions →