## Introduction

In the last post, I’ve introduced the linked list. But there is one problem that we have to traversing the list from its beginning until the expected node was found, which is time-wasting. In this post, I’ll give a new way to solve this problem by using a two links node.

### Implementation

By defining a **two links** node, it is handy for us to move in either direction through the linked list with equal ease. Here I’ll show you the definition of **Node**.

1 | template <class Node_entry> |

Now I’ll show you the definition of DoublyLinkedList.(DoublyLinkedList.hpp)

1 | template <class List_entry> |

In this implementtation, it is possible to move in either direction through the *List* while keeping only one pointer into the *List*. Therefore, in the declaration, we keep only a pointer to the current node of the *List*. We do not even need to keep pointers to the head or the tail of the *List*, since they, like any other nodes, can be found by tracing back or forth from any given node.

#### DoublyLinkedList()

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

1 | template <class List_entry> |

#### ~DoublyLinkedList();

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

1 | template <class List_entry> |

#### DoublyLinkedList(**const** DoublyLinkedList< List_entry > ©)

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

1 | template <class List_entry> |

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

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

1 | template <class List_entry> |

#### size()

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

1 | template <class List_entry> |

#### full()

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

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

#### set_position(int position)

*precondition*: position is a valid position in the *List*: 0 ≤ position < count.*postcondition*: The **current** Node pointer references the Node at position.

1 | template <class List_entry> |

Heroto, I’ll show all the content of List. At the end of the post, I’d like to summerize some featrues of the List implemented by contiguous storage and linked storage.**Contiguous storage** is generally preferable:

- when the entries are individually very small;
- when the size of the list is known when the program is written;
- when few insertions or deletions need to be made except at the end of the list;
- when random access is important and frequent.

**Linked storage** proves superior

- when the entries are large;
- when the size fo the list is not known in advance;
- when flexibility is needed in inserting, deleting, and rearranging the entries.

So it is advisable for you to have a grip on List and choose the most suitable version when you are writing your program. Thank you!