# Implementation - List and Nodes

A linked list is a container class.  As such, our implementation of a linked list will involve creating a template class.  That is the operations on a linked list is unrelated to the data being stored.   Our implementation will be a partial implementation of a doubly linked list with iterators and const\_iterators.   This section should be read as a guide to implementation.  It will start with ideas and diagrams then move on to show the implementation of the idea.

## Linked List

A linked list object (we will call ours DList as it will be a doubly linked list), must store at least one pointer to the first node within the linked list.  However, to speed up the implementation of certain functions, it is advantageous to store a pointer to the last node also.

<img src="https://3939692842-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LFrWzEqLSRHjU6HG9dw%2F-LL5MMY8nw67wXDhuFsd%2F-LL5gIFQVg5lyO1IkAI_%2Flldeclartion.png?alt=media&#x26;token=c5e7130d-6a43-4fe3-ab40-589e448fe82e" alt="" data-size="original">&#x20;

```cpp
template <typename T>
class DList{

    Node* front_;
    Node* back_;
...
};
```

## Nodes

A node is the object that stores the data.  An instance of a linked list does not hold any nodes itself.  It instead points to a set of nodes that are linked together.  Each node object contains a piece of data and two pointers.

<div align="left"><img src="https://3939692842-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LFrWzEqLSRHjU6HG9dw%2F-LL5MMY8nw67wXDhuFsd%2F-LL5gUZ9rkMITO_axlyX%2Fnodedeclaration.png?alt=media&#x26;token=bd1eaf20-e59d-47fa-98f7-e7178326cd26" alt=""></div>

The idea of nodes are not unique to linked lists.  Other container classes such as trees can also have nodes.  As the lists may actually be used in conjunction with other container classes, we will want to hide our nodes.  This is not just hiding the data within the node but rather hide the idea that nodes even exist at all.  To do this, we will declare the node within the DList class itself (in the private section).  As the Node is private to only DList, we will not need to make the Node a class.  A struct will be fine and provide simpler access.  This private declaration of the Node struct will also mean that outside of the DList class, there is no knowledge of the Node which is what we want.  Aside from declaring data members, it is also a good idea to provide a constructor with defaults to simplify the creation of Nodes. &#x20;

```cpp
template <typename T>
class DList{
    struct Node{
        T data_;
        Node* prev_;
        Node* next_;
        Node(const T& data=T{}, Node* prev=nullptr, Node* next=nullptr){
            data_=data;
            prev_=prev;
            next_=next;
        }
    };
    Node* front_;
    Node* back_;
...
};
```

{% hint style="info" %}
Above, you see the use of _**nullptr**_  which is short for null pointer.  The _**nullptr**_ is a value to indicate that the pointer points to nothing.  Any pointer should always either point to some object of its data type or to _**nullptr**_.  Checking to see if a pointer is _**nullptr**_ means you are checking to see if it points to nothing.  _**nullptr**_ is considered to be false equivalent.  That is if a pointer is set to _**nullptr**_ and you check that pointer, it will return false.

```cpp
ptr=nullptr;
if(ptr){
   cout << "pointer points at something" << endl;
}
else{
   cout << "pointer points at nothing (nullptr)" << endl;
}
```
{% endhint %}

## Linked List Constructor

The constructor of the linked list should set up the linked list object in a manner that indicates that there are no nodes within the linked list.  This is fairly simple to implement and only requires that we initialize front\_ and back\_ to _**nullptr**_

<div align="left"><img src="https://3939692842-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LFrWzEqLSRHjU6HG9dw%2F-LL5MMY8nw67wXDhuFsd%2F-LL5gc8QvYvNad2n4ARm%2Fllempty.png?alt=media&#x26;token=1ee48c09-0572-49e3-bc20-7f409b608ce0" alt=""></div>

```cpp
template <typename T>
class DList{
...
public:
    DList(){
        front_=nullptr;
        back_=nullptr;
    }
...
}
```

