# Halo

A magic place for coding

0%

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

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.

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

precondition: None.
postcondition: Clear the List itself.

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

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

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

#### size()

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

#### full()

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

#### empty()

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

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

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

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

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

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

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

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

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.