# Halo

A magic place for coding

0%

## Introduction

In the previous posts, I’ve talked about some kinds of abstract data structures, which are some different version of list. In this post, I’ll introduce the List.

### Definition

A List of elements of type T is a finite sequence of elements of T together with the following operations:

1. Construct the list, leaving it empty.
2. Determine whether the list is empty or not.
3. Determine whether the list if full or not.
4. Find the size of the list.
5. Clear the list to make it empty.
6. Insert an entry at a specified position of the list.
7. Remove an entry from a specified position in the list.
8. Retrieve the entry from a specified position in the list.
9. Replace the entry at a specified position in the list.
10. Traverse the list, performing a given operation on each entry.

### Implementation

First I’d like to give the definition of List.(List.hpp) Here I specify the size of list is 100 in brief.

#### List()

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

#### ~List()

precondition: None.
postcondition: Clear the List itself.

#### List(const List< List_entry > &copy)

precondition: None.
postcondition: The List is initialized as a copy of List copy.

#### operator=(const List< List_entry > &copy)

precondition: None.
postcondition: The List is reset as a copy of List copy.

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

#### empty()

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

#### size()

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

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

precondition: None.
postcondition: If the List is not full and 0 ≤ position ≤ n, where n is the number of entries in the List, 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 List. Else: The function fails with a diagnostic error code.

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

precondition: None.
postcondition: If 0 ≤ position < n, where n is the number of entries in the List, the function succeeds: The entry at position is removed from the List, 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.

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

precondition: None.
postcondition: If 0 ≤ position < n, where n is the number of entries in the List, the function succeeds: The entry at position is copied to x; all List entries remain unchanged. Else: The function fails with a diagnostic error code.

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

precondition: None.
postcondition: If 0 ≤ position < n, where n is the number of entries in the List, the function succeeds: The entry at position is replaced by x; all other entries remain unchanged. Else: The function fails with a diagnostic error code.

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

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

So far, I’ve show you the List. List is an important data structure, which is the base of Stack and Queue. Consequently, use List expertly will be helpful for further learing. Thank you!

Welcome to my other publishing channels