Shulou(Shulou.com)06/01 Report--

Most people do not understand the knowledge points of this "C++ how to achieve two-way linked list" article, so the editor summarizes the following contents for you, with detailed contents and clear steps, which can be used for reference. I hope you can get something after reading this article. Let's take a look at this "C++ how to achieve two-way linked list" article.

Foreword:

The previous article analyzes the one-way linked list, and gives the implementation of python and C++: single linked list from principle to implementation, python and C++ two versions

The bi-directional linked list introduced in this paper is an improvement on the unidirectional linked list, with each node pointing to its direct precursor and direct successor nodes. Therefore, all nodes can be accessed from anywhere in the two-way linked list.

Advantages and disadvantages of two-way linked list

Disadvantages of two-way linked lists:

From the structure of the node, we can see that the storage space of the two-way linked list is larger than that of the one-way linked list. At the same time, for operations such as insert and delete, the node operation of the two-way linked list is more complex, involving the front and back nodes of the node.

Nodes of the two-way linked list:

For a two-way linked list, each node points to "direct precursor" and "direct successor", so the node class needs to contain two pointer fields. Pointers to direct precursors are represented by pre, and pointers to successors are represented by next.

II. Implementation Analysis of C++ (1) Node Class

The nodes of the two-way linked list contain two pointer domains, namely, the direct precursor pre and the direct successor next. The node class uses a template implementation so that the data it stores is no longer dependent on a particular type.

Templateclass Node {public: Node () {} Node * pre; Node * next; / / because the data attribute is private / / data is processed with get and set (T data) {this- > data = data;} T getData () {return this- > data;} private: t data;}; (2) linked list class analysis

The linked list class should contain basic operations such as add, modify, delete, query, etc., because the implementation of its various functions is very similar.

So here are the typical functions that need to be implemented:

Constructor:

IsEmpty () determines whether it is empty or not

Size () returns the linked list length

Insert () head insert, tail insert, middle insert node

Delete () Delete Node

GetNode () get node

Traversal () traverses the linked list

The linked list class is defined as follows:

Templateclass DoubleLinkedList {public: DoubleLinkedList (); bool isEmpty (); Node

* getNode (int index); int size (); void insert (int data, int index); void traversal (); void remove (int index); private: Node

* head;}; (3) list class constructor

During initialization, you need to create a header node as a header pointer:

TemplateDoubleLinkedList

:: DoubleLinkedList () {/ / create header node head = new Node

(); head- > pre = NULL; head- > next = NULL; head- > setData;} (4) isEmpty () to determine whether it is empty or not

For a two-way linked list, you only need to determine whether the header pointer points to another Node node:

Templatebool DoubleLinkedList

:: isEmpty () {if (head- > next = = NULL) {return true;} else {return false;}} (5) size () get the list length

When getting the length of the linked list, it is necessary to determine whether the linked list is empty, so as to determine whether to calculate the length of the linked list by traversing.

Since the circular linked list is not used, the end condition of the loop is to determine whether it points to an empty node:

Templateint DoubleLinkedList

:: size () {if (isEmpty ()) {return 0;} else {int count = 0; Node

* current = head- > next; / / Loop end condition while (currenttermination null) {current = current- > next; count++;} return count;}} (6) getNode () get the node

In the operations such as insertion and deletion, node acquisition operations need to be carried out frequently.

Therefore, it should be encapsulated as a separate function for node acquisition, as follows:

TemplateNode

* DoubleLinkedList

:: getNode (int index) {Node

* current = head; int currentCount = 0; / / Loop end condition while (currentCountnext; currentCount++;} return current;} (7) insert () insert node

The insertion node still includes head insertion, tail insertion and arbitrary insertion. The biggest difference between the insert operation and the one-way linked list is that the pointer movement of the node is more complex, and it is necessary to establish a connection between the two nodes before and after the insertion position and the new node.

Templatevoid DoubleLinkedList

:: insert (int data, int index) {Node

* node = new Node

(); node- > setData (data); / / 1. If the list is empty, if (isEmpty ()) {head- > next = node; node- > pre = head; return;} / / 2, headline if (index = = 0) {node- > next = head- > next; head- > next- > pre = node; node- > pre = head; head- > next = node } / / 3. Else if (index > = this- > size ()-1) {/ / printf ("index% d, size% d\ n", index, this- > size ()); Node

* temp = this- > getNode (this- > size ()-1); temp- > next = node; node- > pre = temp;} / / 4, insert else {Node anywhere

* pre = this- > getNode (index); Node

* next = pre- > next; node- > next = pre- > next; node- > pre = pre; pre- > next = node; node- > next- > pre = node;}} (8), remove () Delete the node

The getNode () function to get the node has been defined earlier, so the remove () function only needs to move the pointer.

Connect the direct precursor of the node you want to delete to the immediate successor:

Templatevoid DoubleLinkedList

:: remove (int index) {/ / ensure that the index is meaningful if ((index)

Size ()-1)) & & (index > 0)) {Node

* node = this- > getNode (index); Node

* pre = node- > pre; Node

* next = node- > next; pre- > next = next; next- > pre = pre;}} (9) traversal () traverses the list function

Although you can traverse the entire linked list from any node of the two-way linked list, the following implementation still starts at the header node, and the end of the loop still points to a null pointer:

Templatevoid DoubleLinkedList

:: traversal () {if (! isEmpty ()) {Node

* current = head; while (current) {cout getData () next;} above is the content of this article on "how to achieve a two-way linked list on C++". I believe you all have some understanding. I hope the content shared by the editor will be helpful to you. If you want to know more about it, please follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.