# Basic Implementation and Explanation of Double Link List (C++ Description) ## The Significance of Double-linked List

Compared with the sequential list, the single linked list does solve some important problems in some scenarios. For example, when a large number of elements need to be inserted or deleted, it does not need to move many elements like the sequential list. It only needs to modify the direction of the pointer. Its time complexity is O(1), but it has the premise that all these are based on the determination of the nodes, pure. In the case of deletion and insertion, if we haven't determined the location of the node, there will be some problems with the single linked list, for example, let's take a look at deleting this operation.

### Delete operation

To delete the second node a1, you only need to point the pointer of the primary node to the address of the third node. But the problem is how to get the precursor of the node to be deleted, which is the primary node in our graph. We give two methods.

• A: While locating the node to be deleted, always save the precursor of the current node conveniently
• B: After deleting a node, go back to the single list header and locate it in its specified precursor

However, no matter which method we choose, the total number of pointer movements will be 2n times, and the double linked list has made a good deal of this type of problem. The reason why there is a problem in single linked list is that each node has only one pointer field next pointing to the successor and can only move backward to find. Once we want to query the former node, it becomes very troublesome. So double linked list adds a pointer field prior pointing to the precursor in front of each node, so that we can directly locate to our previous node, which is also true. It's a double linked list.

Note: In order to unify the operation and avoid special cases, we often set a "tail head node" at the tail, whose next pointer field is empty.

## Abstract data type definition of linear table

Before we give the definition of double linked list, we need to introduce the abstract data type definition of our linear table.

``````#ifndef _LIST_H_
#define _LIST_H_
#include<iostream>
using namespace std;

class outOfRange{};
template<class T>
class List {
public:
// Clear Linear Table
virtual void clear()=0;
// Null, table null returns true, non-null returns false
virtual bool empty()const=0;
// Finding the Length of Linear Tables
virtual int size()const=0;
// In a linear table, insert the element value at the position of I [0.n].
virtual void insert(int i,const T &value)=0;
// In the linearity table, delete elements at positions with I [0.n-1]
virtual void remove(int i)=0;
// In a linear table, the order in which elements with a value appear for the first time
virtual int search(const T&value)const=0;
// In the linearity table, find the element in order i and return its value
virtual T visit(int i)const=0;
// Ergodic linear table
virtual void traverse()const=0;
// Inverse Linear Table
virtual void inverse()=0;
virtual ~List(){};
};

/*Custom exception handling class*/

class outOfRange :public exception {  //Validity of the scope for inspection
public:
const char* what() const throw() {
return "ERROR! OUT OF RANGE.\n";
}
};

class badSize :public exception {   //Used to check the validity of length
public:
const char* what() const throw() {
}
};

#endif
``````

## Definition of double linked list type

``````#ifndef _SEQLIST_H_
#define _SEQLIST_H_
#include "List.h"
#include<iostream>
using namespace std;

template<class elemType>
//elemType is a double linked list storage element type
private:
//Node Type Definition
struct Node {
//Data Domain of Node
elemType data;
//Two pointer fields of a node
Node *prior, *next;
//Two constructors
Node(const elemType &value, Node *p = NULL, Node *n = NULL) {
data = value;
prior = p;
next = n;
}

Node():next(NULL), prior(NULL) {}
~Node(){}
};

//Tail pointer of single linked list
Node *tail;
//Current length of single linked list
int curLength;
//Returns a pointer to a node in order i
Node *getPosition(int i)const;

public:
//Clean up the single linked list and make it empty
void clear();
bool empty()const {return head -> next == NULL;}
//Returns the current actual length of a single linked list
int size()const {return curLength;}
//Inserting value at bit i increases the node table length by 1
void insert(int i, const elemType &value);
//Delete the value of the node with the order i and reduce the table length by 1
void remove(int i);
//Find the location of the first occurrence of a node whose value is value
int search(const elemType &value)const;
//Find the precursor order of the node whose value is value
int prior(const elemType&value)const;
//Access to the value of the node in order i, 0 located at the primary node
elemType visit(int i)const;
void traverse()const;
void inverse();
};
``````

## Realization of Basic Operation of Double Link List

### (1) Construction and destructive function

``````template <class elemType>
//Head and tail nodes point to the head and tail ends respectively.
tail = new Node;
}

template <class elemType>
Node *p = head -> next, *tmp;
tail -> prior = tail;

while(p != tail) {
tmp = p -> next;
delete p;
p = tmp;
}
curLength = 0;
}
``````

### (2) Find the address of the node with the order i

``````template <class elemType>
int count = 0;
if(i < -1 || i > curLength)
return NULL;
while(count <= -1) {
p = p -> next;
count++;
}
return p;
}
``````

### (3) Find the order of nodes whose value is value

``````template <class elemType>
int doubleLinkList<elemType>::search(const elemType &value) const {
Node *p = head -> next;
int i = 0;
while(p != tail && p -> data != value) {
p = p -> next;
i++;
}
if(p == tail)
return -1;
else
return i;
}
``````

### (4) Insert elements

``````template <class elemType>
void doubleLinkList<elemType>::insert(int i, const elemType &value) {
Node *p, * tmp;
if(i < 0 || i > curLength)
throw outOfRange();
p = getPosition(i);
tmp = new Node(value, p -> prior, p);
//The successor of p's original precursor points to tmp
p -> prior -> next = tmp;
//Modify the precursor of p to tmp
p -> prior = tmp;
++curLength;
}
``````

### (5) Delete nodes with the order i

``````template <class elemType>
Node *p;
if(i < 0 || i > curLength)
throw outOfRange();
p = getPosition(i);
p -> prior -> next = p -> next;
p -> next -> prior = p -> prior;
delete p;
--curLength;
}
``````

### (6) The value of accessing nodes in order i

``````template <class elemType>
//visit is not tender and directly uses getPosition to determine whether the scope is legitimate, because the scope is [-1,curLength]
if(i < 0 || i > curLength -1)
throw outOfRange();
//After legalization
Node *p = getPosition(i);
return p -> data;
}
``````

### (7) Traversing double linked list

``````template <class elemType>
Node *p = head -> next;
cout << "traverse: ";
while(p != tail) {
cout << p -> data << " ";
p = p -> next;
}
cout << endl;
}

``````

### (8) Traversing double linked list

``````template <class elemType>
Node *tmp, *p = head -> next;
//Constituting a double empty list
while(p != tail) {
tmp = p -> next;
p -> next = head -> next;
head -> next -> prior = p;
p = tmp;
}
}
``````

## Ending: 