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

This article mainly introduces the C++ one-way list template and iterator iterator class sample analysis, with certain reference value, interested friends can refer to, I hope you have a lot of gains after reading this article, let Xiaobian take you to understand.

Lists are used to construct many other data structures, such as stacks, queues, and their derivatives.

For non-linear linked lists, see related other data structures, such as binary trees, graphs, etc.

1. List introduction

There are three common types of linear lists

Single linked list: Each node contains address information pointing to its successor

Double-linked list: Each node has address information pointing to its predecessor and successor nodes

circular bidirectional linked list: on the basis of the bidirectional linked list, the predecessor information of the data node head is saved as the tail address of the data node, and the latter information of the data node tail is saved as the head address of the data node.

The keywords contained in the linked list are as follows:

List head: that is, the head pointer, each time you access the list, you can traverse each element of the list from this head pointer

header node: invalid data content, pointing to a data node

Data node: A node that stores data elements

Tail node: invalid data content, located at the tail of the data node, marking the last node

For linked lists, the list header must exist. The head node and tail node do not exist in some lists, but having the head node will have great advantages.

Benefits of having a head node:

When inserting and deleting each time, it is not necessary to determine whether it is the first node (for a linked list with no nodes, it is necessary to determine if it is the first node each time, and set the predecessor information as the linked list head, and set the successor information of the linked list head as the first node)

If it is a two-way circular list (implemented in the next chapter), we can easily get to the last data node through the predecessor node of the head node, so as to implement the append function to insert the tail node, without traversing the list to the end and then inserting the node every time.

1.1 Insert a node into a single linked list

As shown below:

After traversing from the head node and finding the pre pointer by the index number-1 to be inserted, the code looks like this:

Node* pre = getNode(i-1); //get previous Node* node = new Node(); // new node->data = value; //set data element node->next = pre->next; //link next of new node to next node pre->next = node; //Link the next of the previous node to the new node m_length += 1;1.2 Delete a node from a single-linked list

As shown below:

The code is as follows: 1. If you want to delete the current pointer, you need to delete the current pointer.

Node* pre = getNode(i-1);Node* current = pre->next; //get the node to delete pre->next = current->next; //link the next node of the current node to the next of the previous node delete current; // delete idle nodes m_length -= 1;1.3 Single linked list Clear all nodes flow

The code is as follows:

while(m_header.next) { Node* node = m_header.next; m_header.next = node->next; delete node; } m_length = 0;2. Implement a single-linked list

Functions to be implemented:

int length() : Gets the length of the linked list data

void clear() : Empty the list of all data

Node* getNode(int i): Gets the node at i

bool insert(int i, const T& value) : Insert a new data at index i

bool remove(int i) : Remove the data with index i in the linked list

T get(int i): Get the data at i

bool set(int i, const T& value): Set the data at i

void append(const T &value): appends a new data to the end of the list

void prepend(const T &value) : Insert new data at the head of the list

void clear() : Empty the list

LinkedList& operator

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.