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

This article introduces how to understand the single linked list in the data structure, the content is very detailed, interested friends can refer to, I hope it can be helpful to you.

Data structure-single linked list 1, single linked list introduction 1, single linked list introduction

Key points of single linked list design:

A, class template, access the successor node through the header node.

B. define the internal node type, which is used to describe the data domain and pointer domain of the node in the linked list.

C. Realize the key operation of linear table

2. Definition of nodes in a single linked list struct Node:public Object {T value;// data field Node* next;// pointer domain} 3. Internal structure of a single linked list

The header node does not store the actual data elements and is used to assist the positioning of data elements to facilitate insertion and deletion operations.

4. Definition of header node in single linked list

Mutable Node m_header

5. The basic structure of single-linked list class template class LinkedList:public List {protected: struct Node:public Object {T value;// data field Node* next;// pointer domain}; Node masked headers; int masked indexing public: LinkedList (); virtual ~ LinkedList (); bool insert (int index, const T & value); bool remove (int index); bool set (int index, const T & value); bool get (int index, T & value) const; int length () const Int find (const T & value) const; void clear ();}; II. Operation of single linked list 1. Insertion of single linked list

The process of inserting a data element at the target location is as follows:

A. start from the beginning node and provide the current pointer to locate the target location.

B. Apply a new Node node from the heap space

C. insert the new node into the target position and connect the logical relationship of the adjacent nodes.

Bool insert (int index, const T & value) {/ / determine whether the target location is legal bool ret = (0 value = value; / / take the next node of the current location as the next node to insert the node > next = current- > next; / / the next node to be inserted as the current node current- > next = node Else else {THROW_EXCEPTION (IndexOutOfBoudsException, "Parameter index is invalid...");} return ret;} 2. Delete operation of single linked list.

The process of deleting a data element at the target location:

A. start from the beginning node and locate the target position through the current pointer

B. use the toDel pointer to point to the node to be deleted

C. delete the node and connect the logical relationship between the adjacent nodes

Bool remove (int index) {/ / determine whether the target location is legal bool ret = (0 next;} / / use toDel to point to the node to be deleted Node* toDel = current- > next; / / point the next node of the current node to the next node of the node to be deleted current- > next = toDel- > next; / / Link list node length minus 1 delete toDel;// to release the heap space of the node to be deleted} else {THROW_EXCEPTION (IndexOutOfBoudsException, "Parameter inde is invalid...");} return ret;} 3. Set the value of the target node

The process of setting the value of the target node is as follows:

A. start from the beginning node and locate the target position through the current pointer

B. modify the value of the data field of the target node

Bool set (int index, const T & value) {/ / determine whether the target location is legal bool ret = (0 next;} / / modify the value of the data field of the target node current- > next- > value = value;} else {THROW_EXCEPTION (IndexOutOfBoudsException, "Parameter inde is invalid...");} return ret } 4. Get the value of the target node bool get (int index, T & value) const {/ / determine whether the target location is legal bool ret = (0 next;} / / obtain the value of the data domain of the target node value = current- > next- > value;} else {THROW_EXCEPTION (IndexOutOfBoudsException, "Parameter inde is invalid...") } return ret;} / / overloaded version T get (int index) const {T ret; get (index, ret); return ret;} 5, get the length of the single linked list int length () const {return m_length } 6. Single-linked list emptying operation void clear () {/ / traversing delete node while (m_header.next) {/ / the next node of the header node to be deleted is Node* toDel = massively header.next; / / pointing the next node of the header node to the next node of the deleted node m_header.next = toDel- > next Delete toDel;// release to delete node} m_length = 0; 3. Optimization of single linked list 1. Defect of header node in single linked list struct Node:public Object {T value;// data field Node* next;// pointer domain}; mutable Node m_header

Since a single linked list must first create a header node, the header node must call a specific type of constructor when it is created. If a specific type of constructor throws an exception, the construction of the single linked list object will fail. And pass the exception of the specific type of constructor.

Class Test {public: Test () {throw 0;}}; int main () {LinkedList l; return 0;}

Therefore, in order to ensure the robustness of the template class, the creation of the header node needs to be optimized, that is, the specific type of constructor is not called when creating a single-linked list object.

Mutable struct:public Object {char reserved [sizeof (T)]; / / Node* next;} m_header

The memory layout of the anonymous header node m_header created is exactly the same as that of the Node object, and the constructor of the specific type T is not called.

2. Code optimization of target location.

The target location is often located in the operation of a single linked list, so you can build a function independently of this part of the code.

Node* position (int index) const {/ / pointer points to header node Node* ret = reinterpret_cast (& m_header); / / traverses to the target location for (int I = 0; I

< index; i++) { ret = ret->

Next;} return ret;} 3, element lookup operation of linked list

Add a find operation to the List template class:

Virtual int find (const T & value) const = 0

The find implementation of the linear table SeqList template class of the sequential storage structure is as follows:

Int find (const T & value) const {int ret =-1; / traversing the linear table for (int I = 0; I

< m_length; i++) { //如果找到元素，退出循环 if(m_array[i] = value) { ret = i; break; } } return ret; } 链式存储结构的线性表的find操作如下： int find(const T& value)const { int ret = -1; //指向头结点 Node* node = m_header.next; int i = 0; while(node) { //找到元素，退出循环 if(node->

Value = = value) {ret = I; break;} else {node = node- > next; iTunes;}} return ret;} 4, time complexity analysis

In practical engineering development, time complexity is only a reference index of efficiency. For the built-in basic type, the efficiency of the linear table implemented by the sequential storage structure is basically the same as that of the linear table implemented by the linked storage structure. For custom class types, the linear table implemented by sequential storage structure is less efficient than that implemented by chain storage structure, because the linear table implemented by sequential storage structure has to design the replication of a large number of data elements. if the copy of the custom type is time-consuming, the efficiency will be very low.

The insertion and deletion operations of linear tables implemented by sequential storage structure involve a large number of object replication operations, while the insertion and deletion operations of linear tables realized by chain storage structure only involve the operation of pointers and do not involve the replication of data objects.

The data access of linear table realized by sequential storage structure supports random access and can locate data objects directly. The data access of linear table realized by chain storage structure must be accessed sequentially, the data object must be accessed from scratch, and can not be located directly.

Therefore, the linear table implemented by sequential storage structure is relatively simple for data types, does not involve deep copy, data elements are relatively fixed, and access operations are much more than insertions and deletions. The linear table realized by chain storage structure is suitable for situations where the types of data elements are complex, replication operations are time-consuming, data elements are unstable, frequent insert and delete operations are needed, and access operations are less.

5. Traversal of single linked list

Usually, the time complexity of traversing the linked list is O (n ^ 2).

For (int I = 0; I

< ll.length(); i++){ ll.get(i); } 通过使用游标的方法将遍历链表的时间复杂度优化为O（n）： A、在单链表的内部定义一个游标（Node* m_current） B、遍历开始前将游标指向位置为0的数据元素 C、获取游标指向的数据元素 D、通过结点中的next指针移动游标 提供一组遍历相关成员函数，以线性时间复杂度遍历链表： bool move(int pos, int step = 1) { bool ret = (0 value; } else { THROW_EXCEPTION(InvalidOperationException, "Invalid Operation..."); } } bool next() { int i = 0; while((i < m_step) && (!end())) { m_current = m_current->

Next; iTunes;} return (I = = m_step);}

The method of traversing the linked list using cursors:

For (ll.move (0);! ll.end (); ll.next ()) {cout next; ret = reverse (list- > next); guard- > next = list; list- > next = NULL;} return ret;}

Non-recursive implementation of single linked list flipping:

Node* reverse (Node* header) {Node* guard = NULL;// linked list Node* current = reinterpret_cast (header); / / current node Node* prev = NULL;// previous node while (current! = NULL) {Node* pNext = current- > next / / next node if (NULL = = pNext) / / if it is a single node linked list {guard = current;} current- > next = prev;//, the next node of the current node points to the previous node, prev = current;// moves the previous node to the current node position current = pNext / / move the current node back} return guard;} 4. Implementation of single linked list template class LinkedList:public List {protected: struct Node:public Object {T value;// data field Node* next;// pointer domain}; mutable struct:public Object {char reserved [sizeof (T)]; / / Node* next;} masked headers; int m_length Int masks step; Node* masks current; protected: Node* position (int index) const {/ / pointer points to header node Node* ret = reinterpret_cast (& m_header); / / traverses to target location for (int I = 0; I

< index; i++) { ret = ret->

Next;} return ret;} public: LinkedList () {m_header.next = NULL; m_length = 0; m_step = 1; m_current = NULL;} virtual ~ LinkedList () {clear ();} bool insert (int index, const T & value) {/ / determine whether the target location is legal bool ret = (0 next = current- > next) / / the next node to be inserted as the current node current- > next = node; node length plus 1} node {THROW_EXCEPTION (NoEnoughMemoryException, "No enough memmory...") } else {THROW_EXCEPTION (IndexOutOfBoudsException, "Parameter index is invalid...");} return ret;} bool insert (const T & value) {return insert (m_length, value);} bool remove (int index) {/ / determine whether the target location is legal bool ret = (0 next) / / point the next node of the current node to the next node of the node to be deleted, current- > next = toDel- > next; node length / link table node length minus 1 destroy (toDel); / / release the heap space of the node to be deleted} else {THROW_EXCEPTION (IndexOutOfBoudsException, "Parameter inde is invalid...");} return ret } bool set (int index, const T & value) {/ / determine whether the target location is legal bool ret = (0 next- > value = value;} else {THROW_EXCEPTION (IndexOutOfBoudsException, "Parameter inde is invalid...");} return ret } bool get (int index, T & value) const {/ / determine whether the target location is legal bool ret = (0 next- > value;} else {THROW_EXCEPTION (IndexOutOfBoudsException, "Parameter inde is invalid...");} return ret;} / / reloaded version T get (int index) const {T ret If (get (index, ret)) return ret;} int length () const {return headlines;} int find (const T & value) const {int ret =-1; / / points to the header node Node* node = massively header.next; int I = 0 While (node) {/ / find the element and exit the loop if (node- > value = = value) {ret = I; break;} else {node = node- > next; iTunes + }} return ret;} void clear () {/ / ergodic delete node while (m_header.next) {/ / the node to be deleted is the next node Node* toDel = m_header.next of the header node / / point the next node of the header node to the next node of the deleted node: m_header.next = toDel- > next; step; return ret; destroy (toDel); / / release the node to be deleted} node (int pos, int step = 1) {bool ret = (0 next; m_step = step;} return ret) } bool end () {return m_current = = NULL;} T current () {if (! end ()) {return current-> value;} else {THROW_EXCEPTION (InvalidOperationException, "Invalid Operation...");}} bool next () {int I = 0 While (I

< m_step) && (!end())) { m_current = m_current->

Next; iTunes;} return (I = = m_step);} virtual Node* createNode () {return new Node ();} virtual void destroy (Node* node) {delete node;}}; V. Defects of static single linked list 1 and single linked list

When using a single linked list for a long time to add and delete data elements frequently, the heap space will produce a lot of memory fragments, which will cause the system to run slowly.

2. Design of static single linked list.

The key points for the implementation of static single linked list:

A. realize static single linked list through class template

B. define a fixed size space in the class

C, rewrite create and destroy functions to change the way memory is allocated and freed

Overload the operator new operator in the Node class to create an object on the specified memory.

3. Implementation of static single linked list template class StaticLinkedList:public LinkedList {protected: typedef typename LinkedList::Node Node; struct SNode:public Node {/ / overloaded new operator void* operator new (unsigned int size, void* loc) {return loc;}}; unsigned char m _ space [N * sizeof (Node)] / / Sequential storage bool m_used [N]; / / Space availability ID public: StaticLinkedList () {for (int I = 0; I)

< N; i++) { m_used[i] = false; } } Node* createNode() { SNode* ret = NULL; for(int i = 0; i < N; i++) { if(!m_used[i]) { ret = reinterpret_cast(m_space) + i; ret = new(ret) SNode(); m_used[i] = true; break; } } return ret; } void destroy(Node* node) { SNode* space = reinterpret_cast(m_space); SNode* pn = dynamic_cast(node); for(int i = 0; i < N; i++) { if(pn == space + i) { m_used[i] = false; pn->

~ SNode ();} int capacty () {return N;}}

The static single linked list has all the operations of the single linked list, and creates node objects in the reserved sequential storage space, which is suitable for situations where the most fixed number of big data elements requires frequent addition and deletion of data elements.

How to understand the single linked list in the data structure is shared here. I hope the above content can be helpful to you and 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.