---
title: "Static vs dynamic list; getnode and freenode"
subject: "Data Structure and Algorithm"
chapter: 3
key: "semester_4/data_structure_and_algorithm:static-dynamic-list-getnode-freenode"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/static-dynamic-list-getnode-freenode
site: BCT Engineering
---

# Static vs dynamic list; getnode and freenode

Data Structure and Algorithm · Chapter 3: List

- Asked in: 2073 Bhadra, 2+2+2 marks
- Video: [Creating the Node of a Single Linked List](https://www.youtube.com/watch?v=DneLxrPmmsw) — Neso Academy
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/static-dynamic-list-getnode-freenode
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-3

## Question

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

## 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).

## Answer

#### Static vs dynamic list

| Static list (array) | Dynamic list (linked) |
|---|---|
| Fixed size at compile time | Size changes at run time |
| Elements in contiguous memory | Nodes anywhere, joined by pointers |
| Insert/delete requires shifting: O(n) | Pointers changed: O(1) |
| Fast random access | Sequential access |
| Memory may be wasted | Extra 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.

```text
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
```

```c
#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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. In a static list with getnode/freenode, what does avail point to?
   A. Last used node
   B. First node of the free list
   C. The array end
   D. NULL always
   Answer: B. avail heads the list of unused nodes. (Key point: Free list)

2. What does getnode do after checking overflow?
   A. p = avail; avail = node[avail].next; return p
   B. avail = p; return
   C. node[p].next = avail
   D. Allocates with malloc
   Answer: A. It takes the first free node and advances avail. (Key point: getnode steps)

3. How does freenode(p) return a node?
   A. avail = node[p].next
   B. node[p].next = avail; avail = p
   C. Deletes node p from the array
   D. Sets node[p] to -1 only
   Answer: B. p is put at the front of the free list. (Key point: freenode steps)

4. When does getnode report overflow?
   A. avail == 0
   B. avail == -1
   C. avail == MAXNODES
   D. p == -1
   Answer: B. -1 marks null so no free node is left. (Key point: Overflow)

5. Time of getnode and freenode?
   A. O(n)
   B. O(log n)
   C. O(1)
   D. O(n^2)
   Answer: C. Each updates a couple of indices only. (Key point: Complexity)

## Related in Data Structure and Algorithm

- [Static vs dynamic implementation of list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astatic-vs-dynamic-list-example) — Data Structure and Algorithm, chapter 3, asked 2×
- [Static vs dynamic implementation of stack](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astack-static-vs-dynamic) — Data Structure and Algorithm, chapter 2
- [Why choose static or dynamic list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Achoose-static-or-dynamic-list) — Data Structure and Algorithm, chapter 3
- [Array list; static or dynamic choice](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aarray-list-static-dynamic-reason) — Data Structure and Algorithm, chapter 3
- [Static and dynamic data structures; array list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astatic-dynamic-ds-array-list) — Data Structure and Algorithm, chapter 3
- [Array representation vs dynamic list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Aarray-vs-dynamic-list) — Data Structure and Algorithm, chapter 3

## Related in other subjects

- [Static vs dynamic mathematical model](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Astatic-vs-dynamic-math-model) — Simulation and Modeling, chapter 2, asked 3×
- [Static and dynamic performance parameters](https://www.bctengineer.com/question.md?key=semester_4%2Finstrumentation_i%3Astatic-dynamic-performance-parameters) — Instrumentation I, chapter 2
- [Static versus dynamic balancing](https://www.bctengineer.com/question.md?key=semester_7%2Ftheory_of_mechanism_and_machine_ii%3Astatic-dynamic-balancing-differentiate) — Theory of Mechanism and Machine II, chapter 5
- [Static and dynamic hazards and their elimination](https://www.bctengineer.com/question.md?key=semester_3%2Fdigital_logic%3Astatic-dynamic-hazards) — Digital Logic, chapter 3, asked 2×