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

This article is about how C++ and python implement single linked lists. The editor thinks it is very practical, so share it with you as a reference and follow the editor to have a look.

I. the basic concept of linked list

A linked list is a linear set of data elements (Linear Collection) and its physical storage is discontinuous. So, what are the advantages of this design? What are the disadvantages?

The basic structure of the linked list:

A linked list is a collection of a series of "nodes", and a node (Node) is made up of a data field (data) and a pointer domain (next).

Functionally, data is responsible for storing data and next is responsible for storing the location of the next node. Of course, in more stringent terms, next stores the address of its immediate successor, which is defined in:

Classification of linked lists:

The common types of linked lists are: one-way linked list, two-way linked list, one-way cyclic linked list, two-way cyclic linked list. Later articles will introduce the structure and code implementation of various linked lists, as well as the corresponding linked list operations.

Basic operation of linked list:

The basic operations of linked lists include: insert, delete, find, merge, etc., in addition to: inversion, sorting, deep replication and so on.

Advantages of linked lists:

Insert and delete quickly

The storage space is unlimited, and you can apply for expansion dynamically without opening up the memory in advance.

Disadvantages of linked lists:

Linked lists require more storage space than arrays (pointers are needed).

Storage discontinuity results in long access time.

From the point of view of reverse access, one-way linked lists are difficult to reverse access, while expanding to two-way linked lists requires additional storage of reverse pointers.

Every node access needs to start with the header.

2. Single linked list

Basic structure:

The structure of a single linked list contains four concepts: head pointer, head node, ordinary Node, and tail node, which are described below:

The head pointer points to the head node, which is the representation of a single linked list and is essential.

The header node is the first node of a single linked list, and its data field content is generally invalid.

Ordinary Node is the node used for data storage and direct subsequent pointer storage.

The tail node is the last node in the linked list, and its pointer field next is empty, followed by no nodes.

Basic operation of single linked list:

The common operations for single linked list are: add, change, check, delete and so on.

Common operations are as follows:

(1) increase

There are generally three ways to add elements to a linked list: head insertion (add), tail insertion (append), and arbitrary position insertion (insert).

(2) change

Change the data of a node in the linked list.

(3) check

Search can be divided into two types: search by value and search by location. The former means to find the corresponding location according to the value, and the latter means to find the corresponding value by location.

(4) Delete

Deletion can be divided into two types: deletion by value and deletion by location. The former means to delete the corresponding node according to the value, while the latter means to delete the corresponding node according to the location.

Implementation description:

According to the information I have seen so far, I will generally implement the functions introduced below, which are put in the implementation of python and C++.

1.python implementation (1) Node Design

According to the definition of a single linked list, a node contains a data field data and a pointer field next:

But because the built-in function next () of next and python has the same name, the pointer field is represented by pointer.

The code is as follows:

Class Node: def _ init__ (self, data): "Args: data: data of node, any type" self.data = data self.pointer = None (2) Link list class: Single_Linked_List

The above Node class objects are the basic structure of the linked list, which can be used to implement header nodes, ordinary nodes and tail nodes.

Therefore, the linked list class only needs to provide a header pointer:

Class Single_Linked_List: def _ init__ (self, node=None): self.__head = node (3) determine whether the linked list is empty: is_empty () function

In fact, you only need to determine whether the header pointer points to a Node class object (or is equal to None) to determine whether a linked list is empty:

Def is_empty (self): "determine whether the linked list is empty"if self.__head = = None: return True else: return False (4) plug insertion: add () function

Node insertion in the chain header is a common insertion operation, which makes the "first inserted node at the end of the linked list". Plug-in requires pointing the head pointer to the new node and making the new node point to the original header node:

Def add (self, data): "Add dnode into head" # create a new node node = Node (data) # make the new node point to the original header node node.pointer = self.__head # make the header pointer point to the new node self.__head = node (5) tail interpolation: append () function

If you want the order of the linked list nodes to be the same as the insertion order, you need to use tail interpolation. Before inserting, you need to determine whether the linked list is empty, and if not, you can insert it (you can call the previously defined is_empty () function, but the following code does not).

In addition, you need to traverse the linked list to find the last node. Single-linked lists can only be accessed from the header, so each trailing must be traversed.

Def append (self Data): "" append node into tail "node = Node (data) # head node if self.__head = = None: self.__head = node # traverse else: current = self.__head while current.pointer! = None: current = current.pointer current when the header pointer is not empty Insert: insert () function at any location

The principle of the head insertion method and tail insertion method introduced above is relatively simple, but it can not fully meet the insertion requirements. If you know where the target is inserted, you can use the insert () function to insert nodes at any location.

It is important to note that several possible situations of the "position" parameter must be taken into account when implementing the insert () function. For example, there is no explicit type requirement in python, so check to see if "position" is an int type.

For the core node insertion function, we need to find the node corresponding to the target insertion location, and make this node point to the new node, and let the new node point to the latter node of the original location node. This process is similar to the process of adding an iron ring to an iron chain, ensuring that the new iron ring is connected with the original two iron rings.

Def insert (self, position, data): "" insert node anywhere Args: position: insert node location, int data: insert node value "if not isinstance (position, int): raise ValueError (" expect type is' int' " But got {} ".format (position.__class__)) # head insertion if position self.get_length (): self.append (data) else: current = self.__head current_position = 0 node = Node (data) # purpose: to calculate the insertion position while current_position

< position -1: current_position += 1 current = current.pointer # 首先：必须使得当前节点的pointer指针指向新建的node # 其次：必须保证新建的node的pointer指向当前节点的后一个节点 node.pointer = current.pointer current.pointer = node（7）计算链表长度：get_length()函数 对于调用者和类内部的其它函数来做，链表长度是一个非常有用的值。比如在插入函数insert()中，需要判断插入位置是不是大于链表长度。 计算链表长度的实现比较简单，只需要遍历链表的所有节点，并用计数器来统计节点的数目即可。 def get_length(self): """ 获取链表的长度""" # 没有任何node if self.__head == None: return 0 # 节点数统计 else: current = self.__head length = 0 while current != None: current = current.pointer length += 1 return length（8）遍历所有节点：traversal()函数 链表、树、图等结构都需要遍历操作，其中链表的遍历比较简单，只需要依次的访问所有节点即可。 def traversal(self): current = self.__head i = 0 # 循环结束的条件依旧是节点的pointer指向不为空 while current != None: print("Element {} is {} ".format(i, current.data)) current = current.pointer i += 1（9）搜索：search()函数 前面提到搜索有按值搜索和按位置搜索两种，它们的原理和实现都十分相似，所以仅以按值搜索为例。 需要注意的是，insert()函数需要判断链表是否为空，并且需要考虑到目标值不在链表中的情况，分别对应不同的返回值。 def search(self, data): """ 返回值为data的第一个节点""" if self.__head == None: return -1 else: current = self.__head current_position = 0 # 遍历节点 while current != None: # 目标值搜索成功 if current.data == data: return current_position # 目标值搜索不到则继续搜索 else: current_position += 1 current = current.pointer # 目标值不存在于链表中 return False（10）删除：delete()函数 上述的查找中以"按值查找"为例，这次删除中同样以"按值删除"为例，"按位置删除"的实现与之类似。 按值删除，即删除目标值对应的目标节点。在进行遍历时，需要记录当前节点和当前节点的前一个节点。因为，一旦查找大目标值所在的目标节点，需要令目标节点的前一个节点指向目标节点的下一个节点，即完成节点的删除。 def delete(self, data): """ 删除值为data的第一个节点""" if self.is_empty(): return None # 记录当前节点和前一个节点 current = self.__head piror = None while current != None: # 查找成功分为两种情况 if current.data == data: # 目标节点为头结点 if current == self.__head: self.__head = self.__head.pointer return True # 目标节点不是头结点 # 令目标节点的前一个节点指向目标节点的后一个节点 else: piror.pointer = current.pointer return True # 更新当前节点和前一个节点 else: piror = current current = current.pointer return False2.C++实现 前面的python实现中已经分析了各个函数的作用，以及对应的实现过程。虽然python和C++的语法不同，但是核心过程是类似的，所以下面不再重复对过程的叙述。 （1）节点设计 由于C++的指针必须指定类型，所以需要使用空指针NULL作为pointer的值。 class Node{public: int data; Node *pointer=NULL;};（2）链表类：SingleLinkedList 遵循声明和实现分类的策略，先对各个函数进行声明。 class SingleLinkedList {public: SingleLinkedList(); bool isEmpty(); int getLength(); void add(int data); void append(int data); void insert(int position, int data); void traversal(); int search(int data); void remove(int data);private: Node *head;};（3）判断链表是否为空：isEmpty()函数bool SingleLinkedList::isEmpty() { // 头结点不指向任何结点，为空 if (head->

Pointer = = NULL) {return true;} else {return false;}} (4) insert: add () function void SingleLinkedList::add (int data) {/ / when the original list has only a header node, you can insert the new node directly (head- > pointer = = NULL) {head- > pointer = new Node; head- > pointer- > data = data } / / when the original list header node contains a successor node / / make the direct successor of the new node to the new node / and make the direct successor of the new node to the direct successor of the original else {/ temporary storage header node Node * temp = head- > pointer; head- > pointer = new Node; head- > pointer- > data = data Head- > pointer- > pointer = temp;}} (5) tail interpolation: append () function void SingleLinkedList::append (int data) {Node * current = head- > pointer; / / find the location of the last node in the list current / / current pointer domain is NULL while (current- > pointerleavnull) {current = current- > pointer } / / make the pointer field of current point to the new node, and insert current- > pointer = new Node; current- > pointer- > data = data;} (6) insert anywhere: insert () function void SingleLinkedList::insert (int position, int data) {/ / header if (position getLength ()) {append (data) } else {/ / the position of the header pointer is 0 int current_position = 0; Node * current = head; Node * prior = NULL; / / find the target node location current, and record its direct precursor node piror while (current_positionpointer; current_position++ } / / the direct precursor prior of the target location points to the new node / / the node of the new node pointing to the target location prior- > pointer = new Node; prior- > pointer- > data = data; prior- > pointer- > pointer = current;}}; (7) calculate the linked list length: getLength () function int SingleLinkedList::getLength () {int counter = 0; Node * current = head / / iterate through the linked list until the last element while (current- > pointerlinked null) {counter++; current = current- > pointer;} return counter;} (8) traverses all nodes: the traversal () function void SingleLinkedList::traversal () {Node * current; / / points to the direct successor of the header node current = head- > pointer; int counter = 1 / / iterate through the linked list and output the value of while (currentless null) {printf ("Element in% d is% d\ n", counter, current- > data); counter++; current = current- > pointer;}} (9) search: search () function int SingleLinkedList::search (int data) {int current_position = 1; Node * current = head- > pointer While (currentorientation null) {/ / search successfully returned the current location if (current- > data = = data) {return current_position;} / / continue to update the location Current = current- > pointer; current_position++;} / / search failed. Return-1 return-1;} (10) Delete: remove () function void SingleLinkedList::remove (int data) {Node * current = head- > pointer; Node * prior = head / / traversing the linked list while (currentless null) {/ / find the target location if (current- > data = = data) {/ / make the direct precursor of the target location point to the direct successor of the target node > pointer = current- > pointer; break;} / / update the current node and its precursor node prior = current Current = current- > pointer;}} Thank you for reading! This is the end of the article on "how to achieve a single linked list on C++ and python". I hope the above content can be of some help to you, so that you can learn more knowledge. if you think the article is good, you can share it for more people to see!

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.