# Double linked list

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

#### Single linked list:

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.

#### Double linked list:

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{}; class badSize{}; 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() { return "ERROR! BAD SIZE.\n"; } }; #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 class doubleLinkList:public List<elemType> { 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(){} }; //Header pointer of single linked list Node *head; //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: doubleLinkList(); ~doubleLinkList(); //Clean up the single linked list and make it empty void clear(); //Single linked list with leading node 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; //Traversing single linked list void traverse()const; //Inverse single linked list void inverse(); //Merged single linked list };`

## Realization of Basic Operation of Double Link List

### (1) Construction and destructive function

`template <class elemType> doubleLinkList<elemType>::doubleLinkList() { //Head and tail nodes point to the head and tail ends respectively. head = new Node; tail = new Node; head -> next = tail; tail -> prior = head; } template <class elemType> doubleLinkList<elemType>::~doubleLinkList() { Node *p = head -> next, *tmp; //The successor of the head node is the tail head node. head -> next = tail; //The precursor of the tail head node is the head node. 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> typename doubleLinkList<elemType>::Node *doubleLinkList<elemType>::getPosition(int i) const { Node *p = head; 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> void doubleLinkList<elemType>::remove(int i) { 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> elemType doubleLinkList<elemType>::visit(int i) const { //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> void doubleLinkList<elemType>::traverse() const { 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> void doubleLinkList<elemType>::inverse() { Node *tmp, *p = head -> next; //Constituting a double empty list head -> next = tail; tail -> prior = head; while(p != tail) { tmp = p -> next; p -> next = head -> next; p -> prior = head; head -> next -> prior = p; head -> next = p; p = tmp; } }`

## Ending:

If there are any deficiencies or errors in the article, please leave a message to share your ideas, and thank your friends for their support!

If you can help me, then pay attention to me! If you prefer the way of reading Wechat articles, you can pay attention to my public number.

We don't know each other here, but we are all working hard for our dreams.

A Public Number Sticking to Pushing Articles on Originally Developed Technologies: More than 20 Years Ideal