Basic Implementation and Explanation of Double Link List (C++ Description)

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

Posted on Tue, 08 Oct 2019 21:34:32 -0700 by craigengbrecht