## Introduction

In some old computer languages, pointers or other facilities for dynamic storage allocation are not provided. Lists are often implemented by using an array-based storage. This way to store data sometimes better than the dynamic one. This post will show how to implement linked lists using only integer variables and arrays.

### Implementation

First we have to define a **Node** structure, which has an **entry** to store the data itself and a **index** to point to the next node. This structure simulate the pointer in some way. Now I give the definition of **Node**.

1 | typedef int index; |

Noted that **index** is actually an int type variable, which is the next index of the present entry.

The general definition of a *StaticList* is similiar to the linked one. But a *StaticList* process more auxiliary functions to help handle entries.

Here I’ll give the code.(StaticList.hpp)

1 | template <class List_entry> |

The functions **new_node** and **delete_node** play the roles of the C++ operators **new** and **delete**. Thus, **new_node** returns a previously unallocated index from *workplace*.

The **set_position** operation is used to locate the index of *workplace* that stores the element of out list with a given position number.

The **current_position** operation uses an index in *workplace* as its parameter, it calculates the position of any list entry stored there.

#### StaticList()

*precondition*: None.*postcondition*: The *StaticList* has been created and is initialized to be empty.

1 | template <class List_entry> |

#### size()

*precondition*: None.*postcondition*: The function returns the number of entries in the *StaticList*.

1 | template <class List_entry> |

#### full()

*precondition*: None.*postcondition*: The function returns **true** or **false** according to whether the *StaticList* is full or not.

1 | template <class List_entry> |

#### empty()

*precondition*: None.*postcondition*: The function returns **true** or **false** according to whether the *StaticList* is empty or not.

1 | template <class List_entry> |

#### clear()

*precondition*: None.*postcondition*: All *List* entries have been removed; the *StaticList* is empty.

1 | template <class List_entry> |

#### traverse(void (*visit)(List_entry &))

*precondition*: None.*postcondition*: The action specified by function *visit has been performed on every entry of the *StaticList*, beginning at position 0 and doing each in turn.

1 | template <class List_entry> |

#### retrieve(int position, List_entry &x)

*precondition*: None.*postcondition*: If the *StaticList* is not full and 0 < position < n; where n is the number of entries in the *StaticList*, the function succeeds: The entry in position is copied to x. Otherwise the function fails with an error code of Range_over.

1 | template <class List_entry> |

#### replace(int position, **const** List_entry &x)

*precondition*: None.*postcondition*: If 0 < position < n; where n is the number of entries in the *StaticList*, the function succeeds: The entry in position is replaced by x, all other entries remain unchanged. Otherwise the function fails with an error code of Range_over.

1 | template <class List_entry> |

#### remove(int position, List_entry &x)

*precondition*: None.*postcondition*: If 0 ≤ position < n, where n is the number of entries in the *StaticList*, the function succeeds: The entry at position is removed from the *StaticList*, and all later entries have their position numbers decreased by 1. The parameter x records a copy of the entry formerly at position. Else: The function fails with a diagnostic error code.

1 | template <class List_entry> |

#### insert(int position, **const** List_entry &x)

*precondition*: None.*postcondition*: If the *StaticList* is not full and 0 ≤ position ≤ n, where n is the number of entries in the *StaticList*, the function succeeds: Any entry formerly at position and all later entries have their position numbers increased by 1, and x is inserted at position in the *StaticList*. Else: The function fails with a diagnostic error code.

1 | template <class List_entry> |

#### new_node()

*precondition*: None.*postcondition*: The index of the first available Node in workplace is returned; the data members available, last_used, and workplace are updated as necessary. If the workplace is already full, -1 is returned.

1 | template <class List_entry> |

#### delete_node(index n)

*precondition*: The *StaticList* has a Node stored at index old_index.*postcondition*: The *StaticList* index old_index is pushed onto the linked stack of available space; available, last_used, and workplace are updated as necessary.

1 | template <class List_entry> |

#### current_position(index n)

*precondition*: None.*postcondition*: Returns the position number of the node stored at index n, or -1 if there no such node.

1 | template <class List_entry> |

#### set_position(int position)

*precondition*: *position* is a valid position in the *StaticList*; 0 ≤ position < count.*postcondition*: Returns the index of the node at *position* in the *StaticList*.

1 | template <class List_entry> |

So far, I’ve introduce the **StaticList** and its implementation. Thank you!