## Introduction

This post will show you a List implemented by using dynamic storage.

Noted that we use the Node structure the same as which we have used in the previous containers. If you still have question about that, you can search **Node** in this station.

### Implementation

Here I give the definition of LinkedList.(LinkedList.hpp)

1 | template <class List_entry> |

Please pay attention that I have included an auxiliary function **set_position()** which will prove useful in our implementations of the methods.

#### LinkedList()

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

1 | template <class List_entry> |

#### size()

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

1 | template <class List_entry> |

#### empty()

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

1 | template <class List_entry> |

#### clear()

*precondition*: None.*postcondition*: All *List* items have been removed; the *List* 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 item of the List, beginning at position 0 and doing each in turn.

1 | template <class List_entry> |

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

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

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 items in the *List*, the function succeeds: The item at position is replaced by x; all other items remain unchanged. Else: The function fails with a diagnostic error code.

1 | template <class List_entry> |

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

*precondition*: None.*postcondition*: If 0 ≤ position < n, where n is the number of items in the *List*, the function succeeds: The item at position is removed from the *List*. The parameter x records a copy of the item 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 *List* is not full and 0 ≤ position ≤ n, where n is the number of items in the *List*, the function succeeds: x is inserted at position of the *List*. Else: the function fails with a diagnostic error code.

1 | template <class List_entry> |

#### ~LinkedList()

*precondition*: None.*postcondition*: Clear the *List* itself.

1 | template <class List_entry> |

#### LinkedList(const LinkedList< List_entry > ©)

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

1 | template <class List_entry> |

#### operator=(const LinkedList< List_entry > ©)

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

1 | template <class List_entry> |

#### set_position(int position)

*precondition*: position is a valid position in the *List*; 0 ≤ position < count.*postcondition*: Returns a pointer to the Node in position.

1 | template <class List_entry> |

Above is the definition and its implementations of a LinkedList. In this post, I’d like to make a comparation between a *contiguous* list and a *linked* list concerning to their time complexity.

The contiguous list:

**insert**and**remove**require time approximately proportional to**n**(**O(n)**).**List**,**clear**,**empty**,**full**,**size**,**replace**, and**retrieve**operate in constant time(**O(1)**).

The linked list:

**clear**,**insert**,**remove**,**retrieve**, and**replace**require time approximately proportional to**n**(**O(n)**).**List**,**empty**,**full**, and**size**operate in constant time(**O(1)**).

Noted that I havn’t included **traverse** in this discussion, since its time depends on the time used by its parameter **visit**, which we don’t know.

This is all the content of this post. Hope it can be useful to your. Thank you very much!